Giallombardo, G., Moccia, L., Salani, M., and Vacca, I. (2009)

Models and Heuristics for the Tactical Berth Allocation Problem with Quay-Crane Assignment and Transshipment Costs

European Transport Conference, Leeuwenhorst conference centre, The Netherlands

In the context of international sea-freight container transport, we study an integrated decision problem arising in container terminal management. We consider the integration of the Berth Allocation Problem (BAP), which consists of assigning and scheduling incoming ships to berthing positions, and the Quay Crane Assignment Problem (QCAP), which assigns to incoming ships a certain QC profile (i.e. number of quay cranes per working shift). BAP and QCAP are strictly correlated, since the QC profile assigned to the incoming ships affects their handling time and has thus an impact on the berth allocation. In particular, we solve this problem at the tactical decision level, with the intent of supporting the terminal in its negotiation process with shipping lines, as the number of quay cranes is usually bounded by contracts which are discussed months in advance. With our analytical tools, we aim to allow terminal managers to assign the right value to the QC profiles proposed to shipping lines, taking into account the impact on the terminal productivity. In addition to profile evaluation, the combined solution of BAP and QCAP optimizes the utilization of terminal resources. In this work, two mixed integer formulations are presented with a quadratic and a linearized objective function, respectively. The objective function aims, on the one hand, to maximize the total value of chosen QC profiles and, on the other hand, to minimize the housekeeping costs caused by transshipment flows between ships. Both models have been validated on instances based on real data provided by MCT, a transshipment container terminal in the south of Italy. Computation confirms that the problem is hardly solvable via exact methods, hence we introduce heuristic methods, in order to find good feasible solutions in a reasonable amount of time. The proposed heuristic algorithm is based on tabu search and decomposition: each iteration consists in two phases, one aimed at finding a feasible profile assignment, the other at finding a feasible solution of the restricted problem obtained by fixing profile variables. Computational results are presented and discussed.