臺灣博碩士論文加值系統

航空公司裝載設備(Unit load device, ULD)，即一般所稱的貨盤或貨櫃，為航空公司每日營運不可或缺的裝載用具。航空公司每日皆會進行各場站盤櫃之調度與數量管理，以有效率使用盤櫃與數量，避免場站盤櫃短缺或閒置的情形。然而，在現實營運中由於每日航班數、機型以及行李與貨物數量的不同，造成每日間盤櫃的需求具日變動的情形。因此，本研究考量實際營運時盤櫃每日間變動需求，發展一短期盤櫃調度與規模模式，期望能幫助業者有效率地規劃盤櫃調度與規模問題。

本研究利用數學規劃方法，結合時空網路技巧定式問題。考量盤櫃變動需求，構建一變動需求ULD調度與規模模式。其中，在此模式中考量實務上須滿足場站庫存需求之服務水準，並運用機會限制規劃的技巧來定式此服務水準限制。另外，為有效求解模式，本研究結合分解式演算法與基因演算法，發展一啟發式演算法。其中，透過子問題分解原問題，並利用交配、突變與菁因政策挑選滿足各場站庫存服務水準下之違反天數，以反覆求解各子問題。最後，我們以國內一航空公司資料為例進行測試分析，並根據研究的結果，提出結論與建議。

The unit load device (ULD) or the so-called pallet or container is essential for an airline’s daily operations. The airline plans the ULD dispatching and scale in each station to efficiently use the ULD and to avoid the occurrences of a shortage and idleness of the ULD. However, in actual operations, because the numbers of flights, fleet types, and baggage and cargo amounts are different in each day, the ULD demands are variable between each day. Therefore, in this research, we consider variable occurred in actual operations to develop a short-term ULD dispatching and scale model. It is expected that the model can help the airline to efficiently plan the daily ULD dispatching and scale problem.

We use the mathematical programming method combined with the time-space network technique to formulate the problem. We consider variable demands to develop a ULD dispatching and scale model. In particular, the level of service of the ULD stock in each station will also be considered in the model by applying the chance constrained programming technique. To efficiently and effectively solve the model, we also combine decomposition method and genetic algorithm to develop a heuristic method. We apply the crossover, mutation, and elitist of the genetic algorithm to find the violation days for the given the level of service of the ULD stock in each station. The sub-problems are repeated solved by decomposing the original problem. Finally, we perform a case study using the real operating data from a Taiwan airline. The test results show the good performance of the model and solution algorithm.

目 錄
誌謝 I
摘 要 II
Abstract III
目 錄 IV
圖 目 錄 VI
表 目 錄 VII
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍 3
1.4 研究流程 4
第二章 文獻回顧 5
2.1 航空公司ULD短期調度與規模 5
2.2 海運貨櫃調度與艙位分配 6
2.3 分解式演算法相關文獻 8
2.4 基因演算法(Genetic Algorithms, GA)相關文獻 9
2.5 本章小結 11
第三章 模式構建 12
3.1 問題描述 12
3.2 變動需求ULD模式假設與已知條件 14
3.3 ULD時空網路設計 15
3.4 變動需求ULD調度與規模定式 19
3.5 本章小結 23
第四章 啟發式求解演算法設計 24
4.1演算法架構 24
4.2 啟發式演算法證明 27
4.3 啟發式求解演算法流程與步驟 29
4.4 小結 31
第五章 實證案例測試 32
5.1 航空公司營運資料分析 32
5.1.1 航班資訊 32
5.1.2 各機型載運ULD相關資料 33
5.1.3 各型ULD裝拆打盤作業時間 35
5.1.4 各場站各類型ULD庫存需求量 35
5.2 模式發展 37
5.2.1 問題規模 37
5.2.2 模式輸入資料 38
5.3 電腦演算環境及設定 38
5.3.1 電腦演算環境 38
5.3.2 相關程式設定 38
5.4 模式輸出資料 40
5.5 測試結果與分析 40
5.5.1 Gurobi測試結果 40
5.5.2啟發式求解演算法測試結果 45
5.6 敏感度分析 50
5.6.1庫存服務水準敏感度(即 ) 50
5.6.2庫存需求敏感度(即 ) 51
5.7 方案分析 53
5.7.1方案一:以台北站母站為測試對象 53
5.7.2方案二:前七個場站為測試對象 54
5.7.3方案三:以航班數量多寡為測試對象 56
5.8 小節 58
第六章 結論與建議 59
6.1 結論 59
6.2 建議 60
參考文獻 62

1. 丁士展、陳穩立、趙郭晉(2014)，定期航運航線貨櫃存量與空櫃調度之研究，第十屆台灣作業研究學會年會暨學術研討會，國立臺灣海洋大學。
2. 車沛俞 (2005)，單一定期航線最適艙位分配之研究，國立臺灣海洋大學航運管理學系碩士論文。
3. 林鄉鎮、魏健宏，「應用類神經網路與遺傳演算法構建小汽車跟車模式之研究」，運輸計畫季刊，第二十八卷，第三期，頁353-378，1999。
4. 洪穎怡，「應用基因演算法規劃具間歇性負載工廠之變壓器容量」，碩士論文，中原大學電機工程 學系，2002。
5. 韋祿甄，「變動抽樣間隔EWMA 管制圖之經濟性設計」，碩士論文，國立雲林科技大學工業工程與管理研究所，2004。
6. 陳建榮，「含凹行節線成本最小成本網路流動問題之全域搜尋演算法研究」，碩士論文，國立中央大學土木工程研究所，2002。
7. 陳喬綺 (2012)，亞洲主要港口冷櫃調度問題之研究，國立臺灣海洋大學航運管理學系碩士論文。
8. 陳惠筑，「公路汽車客運多場站人員與車輛排班問題」，碩士論文，中華大學運輸科技與物流管理研究所，2006。
9. 游彗絹 (2009)，大陸華東地區空櫃調度問題之研究，國立臺灣海洋大學航運管理學系碩士論文。
10. 盧華安、陳倩怡、卓建宏、陳明宏(2009)，國際航空貨運盤櫃設備最適規模及調度限制之研究，運輸學刊，第二十一卷第四期，頁385-412。
11. 穆文弘 (2013)，船期變動下艙位重分配最適化模式之研究，國立臺灣海洋大學航運管理學系碩士論文。
12. 賴清榮 (2005)，聯營合約限制下定期航線最適艙位分配之研究，國立臺灣海洋大學航運管理學系碩士論文。
13. 謝國倫，「基因演算法應用於捷運轉乘公車區位路徑問題之研究」，碩士論文，淡江大學運輸管理研究所，台北，1998。
14. 藍武王、邱裕鈞，「線性軸輻路網接駁／轉運區位、路線與排班之規劃─遺傳演算法之應用」，第二十九卷，第三期，頁465-493，2000。
15. Ali, H., Oh, S.C. (1996), “Formulation and solution of a multi-commodity, multi-modal network flow model for disasterrelief operations,” Transportation Research A, 30, 3, pp. 231-250.
16. Anne, M., Cordeau, J. F., Fran.cois, S. (2005), “A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem,” Computers & Operations Research, 32, 6, pp. 1451-1476.
17. Bin, W. A. N. G., & Guochun, T. A. N. G. (2010). Stochastic optimization model for container shipping of sea carriage. Journal of Transportation Systems Engineering and Information Technology, 10(3), 58-63.
18. Cheng, C. P., Liu, C. W. and Liu, C. C., “Unit commitment by lagrange relaxation and genetic algorithms,” IEEE Transactions on Power Systems, Vol. 15, No. 2, 2000.
19. Feng, C. M., & Chang, C. H. (2008). Empty container reposition planning for intra-Asia liner shipping. Maritime Policy & Management, 35(5), 469-489.
20. Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Reading MA, 1989.
21. Jeffrey, A. J., and Christopher, R. H., “On the Use of Non-stationary Penalty Functions to Solve Nonlinear Constrained Optimization Problems with GA’s,” Department of Industrial Engineering North Carolina State University, NC 27695-7906, 1994.
22. Lu, H. A., & Chen, C. Y. (2011). A time–space network model for unit load device stock planning in international airline services. Journal of Air Transport Management, 17(2), 94-100.
23. Lu, H. A., & Chen, C. Y. (2012). Safety stock estimation of unit load devices for international airline operations. Journal of Marine Science and Technology, 20(4), 431-440.
24. Mathias, K. E., and Whitley, L. D., “Initial performance comparisons for the delta coding algorithm,” The First IEEE Conference on Evolutionary Computation, Orlando, Florida, 1994.
25. Meng, Q., & Wang, S. (2011). Liner shipping service network design with empty container repositioning. Transportation Research Part E: Logistics and Transportation Review, 47(5), 695-708.
26. Perl, J., Daskin, M.S. (1985), “A warehouse location problem,” Transportation Research Part B, 19, 5, pp. 381-396.
27. Reeves, C., “Genetic algorithms for the operations researcher”, INFORMS Journal on Computing, Vol. 9, No. 3, pp. 231-250, 1997.
28. Rudolph, G., “Convergence properties of canonical genetic algorithms,” IEEE Trans. Neural Networks, Vol. 5, pp. 96-101, 1994.
29. Seiichi, K., Maggie, K. and Wayne, W. D., “Genetic simulated annealing and application to non-slicing floor plan design,” Baskin Center for Computer Engineering & Information Sciences University of California, Santa Cruz, CA 95064, 1995.
30. Simpson, R.W. (1969), “A review of scheduling and routing model for airline scheduling,” IX AGIFORS Symposium, Broadway, England.
31. Song, D. P., Li, D., & Drake, P. (2015). Multi-objective optimization for planning liner shipping service with uncertain port times. Transportation Research Part E: Logistics and Transportation Review, 84, 1-22.
32. Srinivas, M. and Patnaik, L. M., “Adaptive probabilities of crossover and mutation in genetic algorithms,” IEEE Trans Syst., Man, and Cybern, Vol. 24, pp.656-667, 1994.
33. Tang, C.H. (2011), “A scenario decomposition-genetic algorithm method for solving stochastic air cargo container loading problems,” Transportation Research Part E, 47, 4, pp. 520-531.
34. Thierens, D., and Goldberg, D., “Elitist recombination: an integrated selection recombination GA,” The First IEEE Conference on Evolutionary Computation, Orlando, Florida, 1994.
35. William, L.C., Tito, H.D.M. (2007), “Some decomposition methods for revenue management,” Transportation Science, 41, 3, pp. 332-353.
36. Wu, T.H., Chinyao, L., Bai, J.W. (2002), “Heuristic solutions to multi-depot location-routing problems,” Computers & Operations Research, 29, 10, pp. 1393-1415.