A 3-stage approach to the berth allocation and quay crane specific problem in container terminals using cutting planes

The berth allocation and quay crane assignment problems are two key problems in container terminals, both maritime and inland. An improved planning with respect to the turnaround time can greatly improve the attractiveness of a terminal to ships. This report considers the berth allocation and quay crane specific problem (BACASP) for inland container terminals. We present a novel 3-stage mixed integer linear programming approach to the BACASP, with a partial integration of the first with the second stage. Time-variant and time-invariant models to the quay crane assignment are considered and solved both exactly and approximately using a rolling horizon strategy. At the heart of the first stage is a type of two-dimensional Knapsack problem. In order to improve performance, novel cutting planes for the two-dimensional geometric knapsack problem (2D-Knapsack) are presented and applied to the BACASP. For 2D-Knapsack, the cutting planes reduce the gap between the dual bound and the optimal solution by 50\% on average. Numerical experiments show that our 3-stage approach obtains a good solution for the time-variant BACASP and an optimal solution to the time-invariant BACASP within 10 minutes in inland terminals with up to 30 vessels arriving per day.