定期貨櫃船舶航線規劃模式與求解演算法之研究

A Model and Solution Algorithm for Container Liner Ship Routing

10.6402/TPJ.200303.0047

顏上堯(Shang-Yao Yan)；藍世宗(S. T. Lan)

航線規劃 ； 櫃流量 ； 節省法 ； 門檻值接受法 ； 大洪水法 ； Vessel routing ； Container flow ； Savings ； Threshold accepting algorithm ； Great deluge algorithm

運輸計劃季刊

32卷1期（2003 / 03 / 30）

47 - 73

繁體中文

航線規劃對航運業者而言甚為重要，影響業者的成本支出與攬貨績效，但隨著經營規模的擴大，以往國內業者使用的人工經驗規劃方式，將難以有效規劃出最佳利潤的航線。本研究從航運業者立場，在不預設船舶容量及數量下，依據已知或預測的市場櫃流量，同時考量週班及最低服務水準之限制，構建一數學規劃模式。由於此模式為一NP-Hard性質之非線性混合整數規劃問題，故本研究綜合Clarke和Wright的節省法、節點增減及交換方法、門檻值接受法及大洪水法等，發展二啓發式解法，求取近似最佳解。最後本研究以一國內海運業者之規劃案為例，測試模式與演算法的績效。

Ship routing is essential to a liner carrier operation. In the past, carriers in Taiwan usually plan their routing manually, which was inefficient to their operations. This research attempts to develop a model and solution algorithm that could help liner carriers in container sh4p routing so that their operations can be improved. The model, on the basis of carrier perspective considering planning practices without capacity constraint, is formulated as an integer linear program that is characterized as an NP-Hard problem. Two heuristic methods, based on the Clarke-Wright Savings method, the node exchanging technique, the threshold accepting algorithm and the great deluge algorithm, are developed to solve for near-optimal solutions. In order to evaluate the model and solution algorithm in practice, a case study concerning the operation of a major Taiwan liner carrier is performed.

1. 盧華安 Lu, Hua-An徐育彰 Hsu, Yu-Chang(2001)。定期貨櫃航線選擇與船隊部署之研究。運輸計劃季刊 Transportation Planning Journal，30(3)
   連結：
2. Bodin, L. D.(1990).Twenty Years of Routing and Scheduling.Operations Research,38
3. Bodin, L. D.Golden, B.(1981).Classification in Vehicle Routing and Scheduling.Networks,11
4. Bott, K.Ballou, R. H.(1986).Research Perspectives in Vehicle Routing and Scheduling.Transportation Research,20
5. Bradley, S. P.Hax, A. C.Magnanti, T. L.(1977).Applied Mathematical Programming.Reading, Massachusetts:Addison-Wesley.
6. Cho, S. C.Perakis, A. N.(1996).Optimal Liner Fleet Routing Strategies.Maritime Policy and Management,23
7. Clarke, G.Wright, J. W.(1964).Scheduling of Vehicles from a Central Depot to a Number of Delivery Points.Operations Research,11
8. Dueck, G.(1993).New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel.Journal of Computational Physics,104
9. Dueck, G.Scheuer, T.(1990).Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing.Journal of Computational Physics,90
10. Fisher, M. L.Jaikumar, R.(1981).A Generalized Assignment Heuristic for Vehicle Routing.Networks,11
11. Garey, M. R.Johnson, D. S.(1979).Computers and Intractability: A Guide to the Theory of NP-completeness.San Francisco:W. H. Freeman ＆ Company.
12. Gillett, E. B.Johnson, G. J.(1976).Multi-terminal Vehicle-dispatch algorithm.OMEGA,4
13. Golden, B. L.Ball, M.(1983).Routing and Scheduling of Vehicle and Crew: The State of Art.Computer and Operations Research,10
14. Kirkpatrick, S.Gelatt, C. D.Vecchi, M. P.(1983).Optimization by Simulated Annealing.Science,220
15. Lane, D. E.Heaver, T. D.Uyeno, D.(1987).Planning and Scheduling for Efficiency in Liner Shipping.Maritime Policy and Management,14
16. Perakis, A. N.Jaramillo, D. I.(1991).Fleet Development Optimization for Liner Shipping, Part 1: Background, Problem Formulation and Solution Approaches.Maritime Policy and Management,18
17. Powell, B.Perakis, A. N.(1997).Fleet Development Optimization for Liner Shipping: An Integer Programming Model.Maritime Policy and Management,24
18. Rana, K.Vickson, R. G.(1988).A Model and Solution Algorithm for Optimal Routing of a Time-chartered Containership.Transportation Science,22
19. Rana, K.Vickson, R. G.(1991).Routing Container Ships Using Lagrangian Relaxation and Decomposition.Transportation Science,25
20. Robuste, F.Dagganzo, C. F.Souleyrette, R.(1990).Implementing Vehicle Routing Models.Transportation Science,24
21. Ronen, D.(1993).Ship Scheduling: The Last Decade.European Journal of Operational Research,71
22. Savelsbergh, M. W. P.(1995).The General Pickup and Delivery Problem.Transportation Science,29
23. Yan, S.Luo, S. C.(1998).Probabilistic Local Search for Concave Cost Transportation Network Problems.European Journal of Operational Research,117
24. 李育欣(1990)。完全性路網TSP問題啟發式解法之研究－兼論類神經網路解法之應用。國立交通大學交通運輸研究所。
25. 林正章 Lin, Cheng-Chang劉志遠 Liou, Jyh-Yeuan(1999)。路線貨運業貨物整體運輸網路設計之研究。運輸計劃季刊 Transportation Planning Journal，28(4)
26. 張永昌 Chang, Yung-chang陳春益 Chen, Chuen-Yih(1994)。中華民國運輸學會第九屆論文研討會論文集。
27. 張淳智 Chang, Cheng-Chih王文貞(1998)。中華民國運輸學會第十屆論文研討會論文集。
28. 許志成(1998)。定期貨櫃船舶排程計劃研究。國立中央大學土木研究所。
29. 郭塗城朱經武 Chu, Ching-Wu(2000)。中華民國第五屆運輸網路研討會論文集。
30. 陳弘輝(1999)。定期貨櫃船繞航模式之比較。國立台灣海洋大學航運管理研究所。
31. 陳春益 Chen, Chuen-Yih林正章 Lin, Cheng-Chang高玉明 Gau, Yuh-Ming(1997)。路線貨運業貨物排程模式之研究。運輸計劃季刊 Transportation Planning Journal，26(2)
32. 彭信坤 Peng, Shin-Kun(1982)。貨櫃船隊船型配置及航線選擇方案之研究。國立成功大學交通管理科學研究所。
33. 黃望修(1990)。貨櫃運輸船隊長程航次逐港灣靠與穿梭地區中心灣靠營運方式之財務效益比較分析。國立交通大學管理科學研究所。
34. 董孝行(1986)。貨櫃船最適船型之研究。運輸計劃季刊 Transportation Planning Journal，15(3)
35. 劉中平(1999)。定期貨櫃船之船隊部署。國立台灣海洋大學航運技術研究所。
36. 盧華安 Lu, Hua-An(2000)。中華民國第五屆運輸網路研討會論文集。
37. 韓復華 Han, Fu-Hwa林修竹(1999)。中華民國第四屆運輸網路研討會論文集。
38. 韓復華 Han, Fu-Hwa楊智凱 Yang, Chih-Kai(1996)。門檻接受法在TSP問題上之應用。運輸計劃季刊 Transportation Planning Journal，25(2)
39. 韓復華 Han, Fu-Hwa楊智凱 Yang, Chih-Kai卓裕仁 Cho, Yuh-Jen(1997)。應用門檻接受法求解車輛路線問題之研究。運輸計劃季刊 Transportation Planning Journal，26(2)
40. 藍世宗 Lan, S. T.(2001)。定期貨櫃船舶航線規劃之研究。國立中央大學土木工程學系。