A dynamic programming-based matheuristic for the dynamic berth allocation problem

Tatsushi Nishi* (Corresponding Author), Tatsuya Okura, Eduardo Lalla-Ruiz, Stefan Voß

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

20 Citations (Scopus)


The increasing maritime traffic forces terminal operators to efficiently reduce the container ships’ service time in order to maintain or increase their market share. This situation gives rise to the well-known berth allocation problem. Its goal is to determine the allocation and the berthing time of container ships arriving to the port with the aim of minimizing the total service time. For tackling this problem, we propose a dynamic programming-based matheuristic that allows to derive lower and upper bounds, and therefore, evaluate the optimality of the provided solutions. Its behavior is assessed on realistic problem instances from the related literature as well as on a new set of larger instances with 150 ships and 15 berths. The results indicate that our proposed approach shows a competitive performance.

Original languageEnglish
Pages (from-to)1-20
Number of pages20
JournalAnnals of operations research
Early online date20 Nov 2017
Publication statusPublished - 1 Mar 2020
Externally publishedYes


  • Dynamic berth allocation problem
  • Dynasearch
  • Lagrangian decomposition
  • Matheuristic
  • n/a OA procedure


Dive into the research topics of 'A dynamic programming-based matheuristic for the dynamic berth allocation problem'. Together they form a unique fingerprint.

Cite this