کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
479776 | 1446031 | 2014 | 12 صفحه PDF | دانلود رایگان |
• Complete and concise mathematical model for the ship placement problem.
• Exact decomposition method.
• Fast, near-optimal heuristics.
• High quality results on real-life instances.
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.
Journal: European Journal of Operational Research - Volume 235, Issue 2, 1 June 2014, Pages 387–398