變動需求下貨櫃船排艙最佳化之研究

Optimization of Container Ship Stowage Plans with Variable Demand

10.6402/TPJ.200509.0355

顏上堯(Shang-Yao Yan)；杜宇平(Yu-Ping Tu)；張耿宗(Keng-Chung Chang)

貨櫃 ； 排艙 ； 變動需求 ； 零壹整數規劃問題 ； Container ； Stowage planning ； Variable demand ； 0-1 integer program

運輸計劃季刊

34卷3期（2005 / 09 / 30）

355 - 389

繁體中文

船舶的大型化為目前貨櫃運輸的趨勢，亦使得傳統人工經驗的排艙困難度大幅增加。過去的學術研究皆假設航線上各港口的出口貨櫃需求量為固定，簡化了實際的變動需求，因此本研究針對變動需求下貨櫃船排艙規劃問題，發展一排艙架構，其核心為一個二階段求解程序，內含二個零壹整數規劃模式，以幫助海運業者有效進行其排艙規劃。在第一階段中，本研究將貨櫃船的艙位分區，且將性質相近的貨櫃編為同組，以翻櫃成本最小化為目標，考量船舶平衡、壓櫃及其他相關營運的限制條件，構建一貨櫃組艙區指派模式。在第二階段中，本研究構建一艙位指派模式，依據第一階段的指派結果對每一艙區內的貨櫃進行指派。本研究利用數學規劃軟體發展一演算法進行求解。為測試本研究模式及演算法的實用績效，本研究參考一國籍海運業者的營運資料進行測試，其模式結果與演算效率均頗佳，顯示本研究模式與演算法應可為實務業者之參考。

Recently, container ship capacity has been increased and thus significantly aggravates the difficulty in stowage planning which is usually performed manually in practice. In addition, former studies usually assumed container demand to be constant, that simplifies demand variations in actual operations. Therefore, to solve the problem of container ship stowage plan to meet various Its demand, in this study we developed a stowage planning framework that contained two 0-1 integer programs embodied in a two-stage process to help naval carriers effectively perform their stowage plans. In the first stage, by assigning container groups with the same OD into the blocks, we developed a contain-block assignment model to minimize the number of container shifting, subject to the ship stability constraint, the container overstow constraint, and the other related operating constraints. In the second stage, a container-slot assignment model was established to assign each container into a slot according to the solution from the fist stage. We used mathematical programming software to develop a solution algorithm. To evaluate the models and the solution algorithm in practice, we conducted case study referring to the data obtained from a Taiwan ocean container liner. The results were positive, showing that models and the solution algorithm could be useful carriers in practice.

1. Ambrosino, D.,Sciomachen(1998).Maritime Engineering and Ports.Boston:WIT Press.
2. Ambrosino, D.,Sciomachen, A.,Tanfani, E.(2004).Stowing a Conatainership: The Master Bay Plan Problem.Transportation Research,2(38A),81-99.
3. Avriel, M.,Penn, M.(1993).Exact and Approximate Solutions of the Container Ship Stowage Problem.Computers and Industrial Engineering,25,271-274.
4. Avriel, M.,Penn, M.,Shpirer, N.(2000).Container Ship Stowage Problem: Complexity and Connection to the Coloring of Circle Graphs.Discrete Applied Mathematics,103,271-279.
5. Avriel, M.,Penn, M.,Shpirer, N.,Witteboon, S.(1998).Stowage Planning for Container Ships to Reduce the Number of Shifts.Annals of Operations Research,76,55-71.
6. Birge, J. R.,Louveaux, F. V.(1997).Introduction to Stochastic Programming.New York:Springer-Verlag.
7. Dubrovsky, O.,Levitin, G.,Penn, M.(2002).A Genetic Algorithm with a Compact Solution Encoding for the Container Ship Stowage Problem.Journal of Heuristics,6(8),585-599.
8. ILOG, Inc.(2001).Using the CPLEX Callable Library.
9. Imai, A.,Nishimura, E.,Papadimitriu, S.,Sasaki, K.(2002).The Containership Loading Problem.International Journal of Maritime Economics,4,126-148.
10. Kang, J. G.,Kim, Y. D.(2002).Stowage Planning in Maritime Container Transportation.Journal of Operational Research Society,53,415-426.
11. Laporte, G.,Louveaux, F. V.,Hamme, L. V.(1994).Exact Solution to a Location Problem with Stochastic Demands.Transportation Science,2(28),95-103.
12. Madansky, A.(1960).Inequalities for Stochastic Linear Programming Problems.Management Science,6,197-204.
13. Martin, G. L.,Randhawa, S. U.,McDowell, E. D.(1988).Computerized Container Ship Load Planning: A Methodology and Evaluation.Computers and Industrial Engineering,14,429-440.
14. Powell, W. B.,Sheffi, Y.,Nickerson, K.,Butterbaugh, K.,Atherton, S.(1988).Maximizing Profits for Truckload Motor Carriers: A New Framework for Pricing and Operations.Interface,18,21-41.
15. Shield, J. J.(1984).Container Stowage: A Computer-Aided Preplanning System.Marine Technology,4(21),370-383.
16. Wets, R. J-B(2000).Stochastic Programming Models: Wait-and-See versus Here-and-Now.National Science Foundation.
17. Wilson, I. D.,Roach, P. A.(2000).Container Stowage Planning － A Methodology for Generating Computerized Solutions.Journal of Operational Research Society,11(51),1248-1255.
18. Wilson, I. D.,Roach, P. A.(1999).Principles of Combinatorial Optimization Applied to Container- Ship Stowage Planning.Journal of Heuristics,4(5),403-418.
19. Wilson, I. D.,Roach, P. A.,Ware, J. A.(2001).Container Stowage Pre-Planning: Using Search to Generate Solutions, a Case Study.Knowledge Based Systems,14,137-145.
20. Yan, S.(1991).Intermodal Pricing and Operations Using Network Flow Techniques.Cambridge, USA:Massachusetts Institute of Technology.
21. Yan, S.,Bernstein, D.,Sheffi, Y.(1995).Intermodal Pricing Using Network Flow Techniques.Transportation Research,29B,171-180.
22. Yan, S.,Lin, C. G.(1997).Airline Scheduling for the Temporary Closure of Airports.Transportation Science,1(31),72-82.
23. Yan, S.,Shieh, C. W.,Chen, M.(2002).A Simulation Framework for Evaluating Airport Gate Assignments.Transportation Research,36A,885-898.
24. Yan, S.,Young, H. F.(1996).A Decision Support Framework for Multi-Fleet Routing and Multi-Stop Flight Scheduling.Transportation Research,5(30A),379-398.
25. 李選士、林志成(1999)。以基因演算法為基礎之排艙自動化。航運季刊，8(2)，21-45。
26. 周建張(1993)。知識庫系統應用於貨櫃船自動化排艙之研究。航運季刊，2(4)，11-24。
27. 張耿宗(2003)。變動需求下貨櫃船排艙最佳化之研究。國立中央大學。
28. 陳春益、溫哲欽(2002)。中華民國第七屆運輸網路研討會論文集。

1. 楊大輝、黃詩佳、陳珍珍(2014)。隨機實體配送網路設計模型及求解演算法。運輸學刊，26(2)，231-256。
2. 楊大輝、李綺容(2007)。需求變動下之航空貨運網路規劃。運輸學刊，19(2)，169-189。