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 language | English |
|---|---|
| Pages (from-to) | 387-398 |
| Number of pages | 12 |
| Journal | European Journal of Operational Research |
| Volume | 235 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - 1 Jun 2014 |
| Externally published | Yes |
Funding
Research funded by a Ph.D. grant of the Institute for the Promotion of Innovation through Science and Technology in Flanders (IWT-Vlaanderen). We would like to thank the Scheepvaartmanagement of the Port of Antwerp for sharing their experience and real-life data on the ship placement problem. The real-life data provided by IT-Bizz and nv De Scheepvaart was also greatly appreciated.
Keywords
- Decomposition
- Heuristics
- Lock scheduling
- Packing
- Ship placement problem