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

Zhou Xu, Chung Yee Lee

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)778-798
Number of pages21
JournalOperations Research
Volume66
Issue number3
DOIs
Publication statusPublished - 1 May 2018

Keywords

  • Branch and bound
  • Continuous berth allocation
  • Exact method
  • Lower bound

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research

Cite this