New lower bound and exact method for the continuous berth allocation problem

Abstract

We study a continuous berth allocation problem, where incoming vessels need to be assigned a mooring time as well as a berth location on a quay. It is a crucial element in port planning to achieve quick turnaround time for vessels. To solve this problem, many solution methods have been developed in the literature. However, gaps between the best-known lower and upper bounds on its optimal solutions are far from close. In this paper, we propose new and more effective solution methods for this important problem. By introducing a novel relaxation of the problem, we have derived a new lower bound that can be computed efficiently in quadratic time. By incorporating this new lower bound with some new heuristic and pruning techniques, we have developed a new exact method, based on a branch-and-bound approach. To demonstrate general applicability of the proposed methods, we have extended them to a more complicated problem, where decisions on berth allocations are restricted by a quay crane constraint. Extensive computational results have shown that, compared with previous state-of-the-art methods, our new methods have significantly reduced gaps between the lower and upper bounds and have solved more and larger instances to optimality in significantly less time. We have also performed sensitivity tests to demonstrate how robust the new solutions are against uncertainties in particular input parameters.