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

Tatsushi Nishi, Tatsuya Okura, Eduardo Lalla-Ruiz, Stefan Voß

Research output: Contribution to journalArticlepeer-review

17 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)391-410
Number of pages20
JournalAnnals of Operations Research
Issue number1-2
Publication statusPublished - Mar 1 2020
Externally publishedYes


  • Dynamic berth allocation problem
  • Dynasearch
  • Lagrangian decomposition
  • Matheuristic

ASJC Scopus subject areas

  • Decision Sciences(all)
  • Management Science and Operations Research


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