New Lower Bound and Exact Method for the Continuous Berth Allocation Problem
针对连续泊位分配问题，提出一种新松弛方法导出可在二次时间内计算的下界，并结合启发式与剪枝技术开发了基于分支定界的精确算法，显著缩小了上下界差距，求解了更多大规模实例。
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. The online appendix is available at https://doi.org/10.1287/opre.2017.1687 .