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

A Model and Solution Algorithm for Container Liner Ship Routing

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

《運輸計劃季刊》 32卷1期 (2003/03) Pp. 47-73

https://doi.org/10.6402/TPJ.200303.0047

摘要

航線規劃對航運業者而言甚為重要，影響業者的成本支出與攬貨績效，但隨著經營規模的擴大，以往國內業者使用的人工經驗規劃方式，將難以有效規劃出最佳利潤的航線。本研究從航運業者立場，在不預設船舶容量及數量下，依據已知或預測的市場櫃流量，同時考量週班及最低服務水準之限制，構建一數學規劃模式。由於此模式為一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.

並列關鍵字

Vessel routing ； Container flow ； Savings ； Threshold accepting algorithm ； Great deluge algorithm

參考文獻

彭信坤 Peng, Shin-Kun(1982)。貨櫃船隊船型配置及航線選擇方案之研究。國立成功大學交通管理科學研究所。

黃望修(1990)。貨櫃運輸船隊長程航次逐港灣靠與穿梭地區中心灣靠營運方式之財務效益比較分析。國立交通大學管理科學研究所。

許志成(1998)。定期貨櫃船舶排程計劃研究。國立中央大學土木研究所。

陳弘輝(1999)。定期貨櫃船繞航模式之比較。國立台灣海洋大學航運管理研究所。

劉中平(1999)。定期貨櫃船之船隊部署。國立台灣海洋大學航運技術研究所。