IMIS | Flanders Marine Institute

Flanders Marine Institute

Platform for marine research


Publications | Institutes | Persons | Datasets | Projects | Maps
[ report an error in this record ]basket (0): add | show Printer-friendly version

Exact and heuristic methods for placing ships in locks
Verstichel, J.; De Causmaecker, P.; Spieksma, F.; Vanden Berghe, G. (2014). Exact and heuristic methods for placing ships in locks. Eur. J. Oper. Res. 235(2): 387-398.
In: European Journal of Operational Research. Elsevier: Amsterdam. ISSN 0377-2217, more
Peer reviewed article  

Available in  Authors 

Author keywords
    Ship placement problem; Packing; Heuristics; Lock scheduling;Decomposition

Authors  Top 
  • Verstichel, J., more
  • De Causmaecker, P., more
  • Spieksma, F., more
  • Vanden Berghe, G., more

    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.

All data in IMIS is subject to the VLIZ privacy policy Top | Authors