Modelling Ship's Routing Bounded by the Cycle Time for Marine Liner

考慮循環週期時間限制之定期船排程模式

盧華安(Hua-An Lu)

《Journal of Marine Science and Technology》 10卷1期 (2002/06) Pp. 61-67

https://doi.org/10.6119/JMST.200206_10(1).0009

摘要

本文討論定期船受循環週期時間限制時，如何進行航線排程最佳規劃之模式構建。透過航商實務流程之探討對航線設計核心問題之分析，本文討論之問題除規劃階段之產業特性外，近似旅行推銷員問題。在滿足循環週期時間與部署船舶數量之關係下，本研究建議一航線排程之混合整數規劃模式，其中加入了若干防止發生分割途程之限制式。在求解部分則仍分成兩個階段進行分枝限界法之求解，第一階段選取目標下限值所拜訪之候選港口，以供第二階段求解使用。經測試所得之排程結果，除可獲得適當之排程計畫外，亦比直接進行求解之方式，有較穩定的求解時間。

並列摘要

This paper addresses the problem of determining an optimal routing that bounded by the cycle time for marine liner. Through exploring the practical planning procedure of shipping company and analyzing the core of route design, this problem is realized as similar as the traveling salesman problem (TSP), but, with some specially industrial properties. A mixed integer programming model is proposed to optimize ship’s routing under satisfying the relationships between the cycle time and deployed vessels with given service frequency in a week. Some constraints, besides, are organized to avoid the routing sequence has separated tours. Intuitively, we also divide the solving procedure into two parts. The first chooses some visited ports from relaxed problem as routing candidates for determining the final routing in the next, both through implemented by the branch-and-bound algorithm. Test results show that our procedure can obtain the suitable route service plan within the stable consumed CPU times of calculation.

並列關鍵字

Ship's routing ； cycle time ； branch-and-bound algorithm