以拉格蘭式鬆弛演算法求解航空貨運承攬業之併裝決策問題

Abstract

航空貨運業在過去的數十年中蓬勃發展，而最近相關的運量預測也顯示未來二十年的成長亦相當樂觀。同時，台灣的經濟發展相當依賴以出口為導向之高科技製造業，一個高效率之航空貨運業將非常有助於台灣產品競爭力之提升。然而，國際航空貨運業是一個作業密集的產業，其經營牽涉眾多的參與者及許多複雜的程序與作業。其中航空貨運承攬業所扮演之角色，一方面是貨主的服務供應者，另一方面也同時是航空公司的消費需求者，於整個航空貨運的流程中扮演著極重要的角色。 由於航空貨運的計費機制上相當複雜，需同時考量託運貨物的重量與體積，且具有顯著的數量折扣，航空貨運承攬業者必須非常有技巧地將所承攬的貨物加以併裝，才能在滿足客戶的需求下，降低支付給航空公司的運費。過去之研究針對航空貨運承攬業之併裝決策問題，發展了混合整數規劃(Mixed Integer Programming – MIP)的模式來求解。然而，受限於運算的複雜度，MIP模型對於較大規模的問題並無法在短時間內找到合理的解答。 為發展合適之求解演算法做為航空貨運併裝決策輔助系統的核心模組，本研究將航空貨運承攬業的併裝決策問題轉換成熟知的集合涵蓋問題(Set Covering Problem - SCP)，再以對求解SCP相當具有成效的拉式鬆弛法為基礎，發展一遞迴性的啟發式求解演算法。為提升求解的效率與品質，本研究並針對演算法之相關議題，如併裝組合空間之調整、可行解之求得、以及參數設定等，進行多項的測試與分析。 數值測試的結果發現，對於小型問題，在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. However, international air cargo business is an operation-intensive industry, which involves many players as well as complex processes and operations. The airfreight forwarders play a very important role in the whole process. They are air service providers for shippers and the consumers for air airlines. The fare system of air cargo is very complex. It considers the weight and volume of the shipment and involves significant quantity discount, airfreight forwarders need to consolidate goods skillfully to the charges from the airlines, while fulfilling customers’ request. Past studies developed mixed integer programming models to solve air cargo forwarders’ consolidation problem. It is hard to solve large scale problems in reasonable time. To develop a suitable heuristic as the core module of decision support systems, this study transforms the air airfreight forwarders’ consolidation problem to well-known set covering problem and use Lagrangean Relaxation, a successful approach for SCP, to develop a recursive heuristic. To raise the efficiency and quality of the solution algorithm, issues such as set adjustment, feasible solution determination, parameters setting, are examined by various kinds analysis and tests. Based on the performed experiments, the heuristic generates the solution very close to the optimal one for the small scale problems, whose optimal solution can be derived from the MIP model. For larger scale problems though MIP model can’t provide optimal solution for comparison, the heuristic still terminates within a reasonable time and generates a solution, which is useful for decision support.