Approximate dynamic programming for liner shipping network design

Sangmin Lee*, Trine Krogh Boomsma, Klaus Kähler Holst

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

The global containerised trade heavily relies on liner shipping services, facilitating the worldwide movement of large cargo volumes along fixed routes and schedules. The profitability of shipping companies hinges on how efficiently they design their shipping network; a complex optimization problem known as the liner shipping network design problem (LSNDP). In recent years, approximate dynamic programming (ADP), also known as reinforcement learning, has emerged as a promising approach for large-scale optimisation. This paper introduces a novel Markov decision process for the LSNDP and investigates the potential of ADP. We show that ADP methods based on value iteration produce optimal solutions to small instances, but their scalability is hindered by high memory demands. An ADP method based on a deep neural network requires less memory and successfully obtains feasible solutions. The quality of solutions, however, declines for larger instances, possibly due to the discrete nature of high-dimensional state and action spaces.

Original languageEnglish
JournalAnnals of Operations Research
ISSN0254-5330
DOIs
Publication statusE-pub ahead of print - 2024

Bibliographical note

Publisher Copyright:
© The Author(s) 2024.

Keywords

  • Approximate dynamic programming
  • Combinatorial optimisation
  • Deep reinforcement learning
  • Liner shipping network design

Cite this