Exact and heuristic methods for placing ships in locks

J. Verstichel, P. De Causmaecker, F.C.R. Spieksma, G. Vanden Berghe

Research output: Contribution to journalArticleAcademicpeer-review

34 Citations (Scopus)

Abstract

The ship placement problem constitutes a daily challenge for planners in tide river harbours. In essence, it entails positioning a set of ships into as few lock chambers as possible while satisfying a number of general and specific placement constraints. These constraints make the ship placement problem different from traditional 2D bin packing. A mathematical formulation for the problem is presented. In addition, a decomposition model is developed which allows for computing optimal solutions in a reasonable time. A multi-order best fit heuristic for the ship placement problem is introduced, and its performance is compared with that of the left-right-left-back heuristic. Experiments on simulated and real-life instances show that the multi-order best fit heuristic beats the other heuristics by a landslide, while maintaining comparable calculation times. Finally, the new heuristic's optimality gap is small, while it clearly outperforms the exact approach with respect to calculation time.

Original languageEnglish
Pages (from-to)387-398
Number of pages12
JournalEuropean Journal of Operational Research
Volume235
Issue number2
DOIs
Publication statusPublished - 1 Jun 2014
Externally publishedYes

Keywords

  • Decomposition
  • Heuristics
  • Lock scheduling
  • Packing
  • Ship placement problem

Fingerprint

Dive into the research topics of 'Exact and heuristic methods for placing ships in locks'. Together they form a unique fingerprint.

Cite this