臺灣博碩士論文加值系統

航空貨運業在過去的數十年中蓬勃發展，最近相關的運量預測也顯示未來二十年的成長亦相當樂觀。同時，台灣的經濟發展相當依賴以出口為導向之高科技製造業，一個高效率之航空貨運業將非常有助於台灣產品競爭力之提升。然而，國際航空貨運業是一個作業密集的產業，其中航空貨運承攬業所扮演之角色，一方面是貨主的服務供應者，另一方面也同時是航空公司的消費需求者，於整個國際航空貨運業的流程中扮演著極重要的角色。
航空貨運計價方式較一般運輸業來得複雜，不僅有向貨主收取費用的訂價，還必須考慮交付航空公司的不同收費方式，甚至當進行出口貨物戶對戶的運送類型時，還需將陸運花費納入考量。在此研究中，航空公司會提供不同種類、重量與體積限制的盤櫃，而其有相對應的收費方式，包含使用盤櫃的固定成本以及根據盤櫃內貨物重量計價的變動成本，因此本研究以航空承攬運送業者為角度，發展了混合整數規劃 (Mixed Integer Programming – MIP) 的模式，提供散貨貨物併裝與路徑之決策模式，幫助航空承攬業者決定如何租賃盤櫃以及如何將貨物併裝在這些盤櫃內，目標為最小化其所須支付之空運及陸運費用。
然而，受限於運算的複雜度，MIP 模型對於較大規模的問題並無法在短時間內找到合理的解答，為了可以運用在實務當中，必須在有限時間內求出理想的可行解，所以本研究以拉式鬆弛法為基礎發展出一遞迴性的啟發式求解演算法。數值測試的結果發現，對於小型問題，在MIP 模型可在合理時間內提供最佳解的情況下，演算法所得的近似解接近最佳值，另外，對於中大型問題，雖然MIP 模型無法提供最佳解供比對，但演算法均可在有限的時間內求得合理之近似解，並提供參考價值之解答。

Air cargo business has been booming for the past decades, and recent forecast also shows that the growth rate is promising for next twenty years. Meanwhile, Taiwan’s economic development highly depends on high-tech manufacturing industry, an efficient air cargo business would be very helpful to promote the competition of Taiwan’s products. The airfreight forwarders play a very important role in international air cargo business. They are air service providers for shippers and the consumers for air airlines.
In this problem, the air carriers can provide different types of air containers with different weight and volume limits. The problem is further complicated by the cost charged by the air carriers: this is based on a fixed cost for using the container and a variable cost that depends on the weight that the container will hold. This study developed a mixed integer programming model which is from airfreight forwarder’s perspective, to provide decision-making of cargo consolidation and path decision to help airfreight forwarder make decisions about how to rent air containers from air carriers and how to load air cargos into these containers optimally. The objective is to minimize its transport costs.
As it is hard to solve large scale problems in reasonable time. To be able to use it in practice, we use Lagrangean Relaxation to develop a recursive heuristic for finding an ideal feasible solution in a limited time. Based on the performed experiments, the heuristic generates the solution very close to the optimal derived from the MIP model for the small scale problems. For larger scale problems though MIP model can’t provide optimal solution for comparison, the heuristic still terminates within a limited time and generates a reasonable solution.

摘要 i
ABSTRACT ii
誌謝 iii
目綠 iv
表目錄 vi
圖目錄 vii
一、緒 論 1
1.1 研究背景與動機 1
1.2 研究範圍與目的 6
1.3 研究方法與流程 8
二、問題背景與文獻回顧 10
2.1 航空業承包盤櫃之介紹 10
2.2 航空盤櫃計價特性 11
2.3 航空承攬業相關文獻回顧 17
2.4 貨物併裝問題相關文獻 20
2.5 複合式貨物運輸相關文獻 23
三、數學模式及求解方法 25
3.1 數學規劃模式 25
3.2 拉式鬆弛法求解數學模式 29
3.3 拉式鬆弛模型及求解 31
3.4以拉氏演算法求解可行解 35
3.5 次梯度法調整拉氏乘數值 39
3.6 演算法流程 42
四、數值測試 43
4.1 測試題目設計 43
4.2 數值測試結果 47
4.2.1 40貨物小型例題測試 47
4.2.2 60貨物中型例題測試 49
4.2.3 80貨物大型例題測試 50
五、結論與建議 52
參考文獻 54

1. Boardman, B.S., Malstrom, E.M., Butler, D.P., Cole, M.H.,1997, “Computer assisted routing of intermodal shipment” Computers and Industry Engineering, vol. 33(1–2), pp. 311–314.
2. Barnhart, C., Ratliff, H., 1993, “Modelling intermodal routing” Journal of Business Logistics 14, 205–223.
3. Bortfeldt, A., Wäscher, G., 2013, “Constraints in container loading – A state-of-the-art review” European Journal of Operational Research, 229 (1), pp. 1–20.
4. Caris, A., C. Macharis, G. Janssens., 2008, “Planning Problems in Intermodal Freight Transport: Accomplishments and Prospects” Transportation Planning and Technology, Vol. 31, No. 3, pp. 277–302.
5. Crainic, T.G., Perboli, G., Rei, W., Tadei, R., 2011, “Efficient lower bounds and heuristics for the variable cost and size bin packing problem” Computers & Operations Research 38,1474–1482.
6. Erera, A. L., Morales, J. C., and Savelsbergh, M., 2005, “Global intermodal tank container management for the chemical industry” Transportation Research Part E, 41(6), 551-566.
7. Friesen, DK., Langston, MA., 1986, “Variable sized bin packing. ” SIAM Journal on Computing 15:222–30.
8. Fisher, M.L., 1981, “The Lagrangian relaxation method for solving integer programming problems” Management Science 27 (1), 1–18.
9. Feng, B., Li, Y., Shen, Z.M., 2015, “Air cargo operations: Literature review and comparison with practices” Transportation Research Part C 56, 263–280.
10. Felix T.S., Chan, Rajat Bhagwat, N., Kumar, M.K., Tiwari, Philip Lam, 2006, “Development of a decision support system for air-cargo pallets loading problem: A case study” Expert Systems with Applications 31, 472–485.
11. Felix T.S. Chan, N. Kumar, 2006, “A new heuristic embedded approach for multi-constraint air-cargo loading problem” IEEE International Conference on Industrial Informatics.
12. Fisher M.L, 2004, “The Lagrangian Relaxation Method for Solving IntegerProgramming Problems” Management Science 50(12_supplement):1861-1871.
13. Garey M, Johnson D., 1979, “Computers and intractability: a guide to the theory of NP-completeness” San Francisco:W.H. Freeman.
14. Huang, K., Chi, W., 2007, “A Lagrangean relaxation based heuristic for the consolidation problem of airfreight forwarders” Transportation Research Part C: Emerging Technologies 15 (4), 235–245.
15. Held M., Karp R. M., 1970, “The traveling salesman problem and minimum spanning trees. ”, Operations Research, Vol 18,1138-1162.
16. James H. Bookbinder, Samir Elhedhli and Li Z., 2015, “The air cargo consolidation problem with pivot weight : Models and solution methods”, Computers & Operations Research, 59, 22–32.
17. Leung, L.C., Van Hui, Y., Wang, Y., Chen, G., 2009, “A 0-1 LP model for the integration and consolidation of air cargo shipments.” Operations Research 57 (2), 402–412.
18. Li Y, Tao Y, Wang F., 2009, “A compromised large-scale neighborhood search heuristic for capacitated air cargo loading planning.” European Journal of Operational Research 199(2):553–60.
19. Li, Z., Bookbinder, J. H., & Elhedhli, S., 2012, “Optimal shipment decisions for an airfreight forwarder: Formulation and solution methods.” Transportation Research Part C: Emerging Technologies, 21(1), 17-30.
20. Macharis C. and Bontekoning Y.M., 2004, “Opportunities for OR in intermodal freight transport research: A review” European Journal of Operational Research 153, 400–416.
21. Martello, S., Pisinger, D., & Vigo, D., 2000, “The three-dimensional bin packing problem.” Operations Research, 48(2), 256-267.
22. Martine, L., Gilbert, L., Silvano, M.,1995, “An exact algorithm for the dual bin packing problem” Operations Research Letters 17, 9-18.
23. Mongeau, M., Bes, C., 2003, “Optimization of aircraft container loading.” IEEE Trans. Aerospace Electron. Syst. 39 (1), 140–150.
24. Milan, J., 2008, “Modelling the full costs of an intermodal and road freight transport network” Transportation Research Part D, 12, 33-44.
25. Mohamed, H. and Mehdi, S., 2011, “Relaxations and exact solution of the variable sized” Computational Optimization and Applications, 48: 345–368.
26. Paquay, C., Schyns, M. and Limbourg, S., 2016, “A mixed integer programming formulation for the three-dimensional bin packing problem deriving from an air cargo application” International Transactions in Operational Research, 23(1-2), 187-213.
27. Qin, H., Zhang, Z., Qi, Z., & Lim, A., 2014, “The freight consolidation and containerization problem.” European Journal of Operational Research, 234, 37-48.
28. Ross G. T. and Soland M. R., 1975, “A branch and bound algorithm for the generalized problem” Mathematical Programming, 8, 91-103.
29. Tragantalerngsak, S., Holt, J., Ronnqvist, M., 1997, “Lagrangean heuristics for the two-echelon, single-source, capacitated facility location problem.” European Journal of Operational Research 102, 611–625.
30. Wong, W.H., Leung, L.C., Hui, Y.V., 2009, “Airfreight forwarder shipment planning: A mixed 0–1 model and managerial issues in the integration and consolidation of shipments” European Journal of Operational Research 193.
31. Wäscher, G., Haußner,H., Schumann, H., 2007. An improved typology of cutting and packing problems. European Journal of Operational Research 183, 1109–1130.
32. Xue J. and Lai K.K., 1997, “A study on cargo forwarding decisions”, Computers and Industrial Engineering, 33, pp.63-66.
33. Yan, S.Y., Lo, C.T., Shih, Y.L., 2006, “Cargo container loading plan model and solution method for international air express carriers.” Transp. Plann. Technol. 29 (6), 445–470.
34. Yan, S.Y., Shih, Y.L., Shiao, F.Y., 2008, “Optimal cargo container loading plans under stochastic demands for air express carriers.” Transp. Res. Part E 44 (3), 555–575.
35. Y. Wu, 2007, “Modelling containerization of air cargo forwarding problems.” Production Planning & Control Vol. 19, No. 1, 2–11.
36. Y. Wu, 2010, “A dual-response forwarding approach for containerizing air cargoes under uncertainty, based on stochastic mixed 0-1 programming.” European Journal of Operational Research 207, 152–164.
37. Y. Wu, 2011, “Modelling of containerized air cargo forwarding problems under uncertainty.” Journal of the Operational Research Society 62, 1211–1226.
38. Ziliaskopoulos, A. and Wardell, W., 2000, “An intermodal optimum path algorithm for multimodal networks with dynamic arc travel times and switching delays” European Journal of Operational Research, 125, pp. 486_502.
39. Boeing, World Air Cargo Forecast 2014-2015. [1]
40. Boeing, World Air Cargo Forecast 2002-2003. [3]
41. 交通部民用航空局，民航統計年報，民國103 年。[2]
42. 余智仁，「航空貨運承攬業多重併裝模式之創值功能研究-以空併為例」，國立高雄大學高階經營管理碩士在職專班，碩士論文，民國99 年。
43. 吳思賢，「航空貨運承攬業決策輔助系統之研究」，國立交通大學，碩士論文，民國92 年。
44. 卓建宏，「空貨運盤櫃設備規模之研究」，國立臺灣海洋大學，碩士論文，民國93 年。
45. 紀玟豪，「以拉格蘭式鬆弛演算法求解航空貨運承攬業之併裝決策問題」，國立交通大學，碩士論文，民國93 年。
46. 陳宇軒，「整合航空客運與貨運之飛航排程暨班次表建立之研究」，國立中央大學，碩士論文，民國93年。
47. 黃國宣，「複合運輸的路徑與併裝決策模式」，國立交通大學，碩士論文，民國104 年。