以穩健最佳化分析航班與卸載道之指派問題

A Robust Optimization Model for Flight to Unloading Zone Assignment Problem

劉愛琳(Liou, Irene)

指導教授 ： 林則孟

國立清華大學/工學院/工業工程與工程管理學系/碩士(2017年)

摘要

錯運行李在機場處理的議題中，是相當重要的一個項目。在2016年航空旅客報告之旅客抱怨項目排行榜中，錯運行李排名在第二位；而且，一件錯運行李將造成事後的補償成本，例如在美國，一件錯運行李就得賠償旅客至少500美金。隨著錯運行李數量的增加，將會造成更多旅客的不滿以及機場的營運成本負擔。
機場通常會使用自動化的行李運輸系統(Baggage Handling System; BHS)來處理旅客報到後託運的行李，此行李運輸系統透過傳輸通道將行李運送至卸載道。如果卸載道容量不足，行李必須安排到人工分檢大轉盤由地勤人員分檢，此人工分檢大轉盤所處理的行李還包含了系統中出錯、或是未被辨識的行李，因此分檢複雜度高，卸載作業較有可能出錯。然而，行李運輸系統通常不會因估計未來航班量或旅客量的增長而任意擴建，因此對於面臨逐年增加的旅客量之機場，如何有效的運用現有的卸載道來配置航班是相當重要的。
機場必須指派航班到卸載道，行李運輸系統才會依此指派運作。機場在做航班與卸載道指派時，面臨到的一大難題是未來的變化，並非所有航班皆能準時到達機場，可能因為氣候變化或機台故障等情形，影響航班準點率，而機場也不方便一直根據實務情況變化而不斷重新規劃卸載道指派。因此，對機場來說，一個考慮到未知數而做的穩定規劃是很重要的。本論文提出一個穩定最佳化模型(Robust Optimization model; RO model)，來求解存在隨機性的航班卸載道指派問題。
本論文提出的數學模型是在考慮了機場的營運需求下建構，此模型能在避免發生錯運行李的情況下找到最佳的航班與卸載道配置規劃。本論文以台灣桃園機場為例，投入相關資料求解後，驗證本論文提出的確定行數學模型能有效降低排不下卸載道的航班數量(比起桃園機場的人工經驗排法，降低了平均50%的無法指派的航班數量)。在考慮了實務上的未知數後，本論文以二階段規劃方法建構穩健最佳化模型，並使用Progressive Hedging Algorithm (PHA)來加快RO模型之求解效率，再以Sample Average Approximation (SAA)方法驗證此模型可以在一定情境(scenario)數量下找到品質不錯的解。透過實驗分析，RO模型的求解結果比現有的模型(確定型數學模型以及機場人工經驗排法)帶來更好的績效表現，顯示出RO模型考慮隨機性所做的決策，能為管理者帶來較佳的效益。本論文提出的確定型數學模型以及RO模型，兩者皆有透過模擬模式(Simulation Modeling)來驗證其實務上之可行性。

關鍵字

行李運輸系統 ； 航班卸載道指派 ； 穩健最佳化 ； PHA演算法 ； 模擬模式

並列摘要

Mishandled baggage is one of the major issues in airports. Mishandling of baggage is ranked second in the complaints category by the Air Travel Consumer Report in 2016. In US, passengers are compensated at least $500 per mishandled bag. A large number of mishandled baggage may result in passenger dissatisfaction and is also costly to the airports/airlines.
To transport passengers’ baggage from check-in counters to the unloading zones, baggage handling systems (BHS) are widely used in airports. BHS is an automated system with a set of conveyors to transport and sort most of the baggage to the unloading zones. If the unloading zones in BHS are not fully occupied, baggage will be handled by BHS; otherwise, ground crews have to manually sort the baggage which is more labor intensive, costly and has higher error rates. However, the number of baggage and their variation are usually unknown when the BHS was constructed. The efficiency of using BHS unloading zones becomes important especially for airports with an increasing number of passengers.
To use BHS, airports assign each flight to an unloading zone. One of the major challenges is to consider the future uncertainty in the flight to unloading zone assignment. Not every flight will be on time due to uncertainties such as mechanical problems or weather changes. The latest flight arrival status may change in any minute and it is not possible to re-plan accordingly. Therefore, a robust plan with constant stability in performance with respect to future uncertainty realization is needed. In this research, a robust optimization model is developed to solve the flight to unloading zone assignment problems with consideration of the future uncertainty.
We develop the mathematical model which considers operation requirements for avoiding baggage mishandling and generates an optimal assignment of flights to unloading zones. Our results are evidently superior to that of current airport assignment (by human experiences; taking Taiwan Taoyuan International Airport Terminal Two as case study) in reducing the amount of unassigned flights, 50% on average. Considering data uncertainties, we construct a robust optimization (RO) model using two-stage programming method to generate a robust plan. The computation speed of RO model is accelerated by implementing the progressive hedging algorithm (PHA). The results of RO model are proved to be significant by Sample Average Approximation (SAA) and indicate that RO model is superior in performance to deterministic model (about 10% improvement) and to current assignment (about 100% improvement). Validation of their results are done through simulation modeling.

並列關鍵字

Baggage Handling System ； flight to unloading zone assignments ； Robust Optimization ； Progressive Hedging Algorithm ； Simulation Modeling

參考文獻

Abdelghany, A., Abdelghany, K., & Narasimhan, R.: Scheduling baggage-handling facilities in congested airports. Journal of Air Transport Management (2006) 12(2), 76-81.

Ahmed, M. B., Mansour, F. Z., Haouari, M.: A two-level optimization approach for robust aircraft routing and retiming. Computers & Industrial Engineering, Available online 21 September 2016.

Al-Serafi A. and Elragal A.: Visual Trajectory Pattern Mining: An Exploratory Study in Baggage Handling Systems. Springer International Publishing Switzerland (2014) 159–173.

Amin Jamili: A robust mathematical model and heuristic algorithms for integrated aircraft routing and scheduling, with consideration of fleet assignment problem. Journal of Air Transport Management, Vol. 58, January 2017, 21–30.

Ascó, A., Atkin, J. A. D., & Burke, E. K.: An analysis of constructive algorithms for the airport baggage sorting station assignment problem. Journal of scheduling, 17(6), (2014) 601-609. DOI 10.1007/s10951-013-0361-x