出境航班與轉盤型卸載道之指派問題

Outbound flights and carousel-based unloading zone assignment problem

趙淳慧(Chun-Hui Chao)

指導教授 ： 林則孟

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

摘要

台灣桃園國際機場在2015年進行升級工程，將行李運輸系統的卸載道由直線型改為轉盤型，轉盤型卸載道可同時卸載多個航班，解決卸載道不足的問題，但也產生一些限制，使航班與卸載道指派問題為機場管理的重要議題。
本研究考量機場營運需求、航班限制、卸載道特性、以及地勤人員作業方便性，以改良式基因演算法求解航班與卸載道指派問題。在航班來到密度高的尖峰時刻中，航班可能有排不進卸載道的問題，因此本研究將指派情境分為使用基礎指派條件的情況，以及考量尖峰時刻下可以放寬限制條件的情況。以最小化無法安排之航班數，以及最小化卸載重疊時間為目標，當同時最小化兩目標時，卸載道指派有最佳解之「Pareto set」，提供機場管理卸載道配置之參考。
研究結果發現，現行指派平均每天有162個航班，其中有20~30%的航班排不進卸載道，這些航班會被安排至北登卸載，導致機場管理不便；本研究提出之基礎指派模型，可使無法排進卸載道的航班減少至7~12%，且避免使用北登造成行李分揀錯誤率提高。在考量尖峰時刻下條件放寬時，以開放大航班與中航班重疊以及轉盤容量增加，最能有效減少排不下的航班數量，可以使無法排下的航班數減少至0~2%，也就是一天最多僅有1至3個航班沒有卸載道可以使用，需以人工方式進行行李分揀。
本研究進一步考量卸載時間具有變異性、航班可能延遲之機率情境下，透過模擬驗證隨機性對前述雙績效有顯著影響：航班延遲會使排不下的航班增加；卸載時間具有變異性不僅會產生更多排不下的航班，也會造成卸載重疊時間增加。本研究提出之演算法透過隨機模擬驗證，顯示在卸載時間具有變異性及航班可能延遲情況下仍具有穩定性。

關鍵字

機場行李運輸系統 ； 航班卸載道指派問題 ； 基因演算法 ； 啟發式演算法 ； 最佳資源分配法

並列摘要

Taiwan Taoyuan International Airport carried out an upgrading project in 2015. The unloading zone of baggage handling system changed from lateral chutes to carousels. Carousels can unload the baggage of multi-flights simultaneously to solve the problem of insufficient unloading zone. However, there will be some restrictions on arrangement that make the flight-to-unloading zone assignment problem be an important issue of airport management.
In this research, we consider the operation requirements of airport, restrictions on the flight, characteristics of carousels, and the convenience of crew operations to solve the flight-to-unloading zone assignment problem. In the peak time with high density of flight arrivals, flights may have no carousels to deal with their baggage. This research divides the scenarios of assignment into the condition with basic assignment restrictions, and the condition that during the paek time, restrictions can be relaxed. The objective is to minimize the number of flights that can not be arranged and minimize the overlap time of unloading. When minimizing both objectives, there will be a Pareto set of optimal solutions that can provide airport management some arrangement results.
Results indicate that there are average 162 flights a day, which are about 20~30% flights that have no carousels to unload baggage. These flihts will be arranged to North-board to unload and may result to inconvience of airport management. The basic assignment model proposed in this research can reduce the flights that have no carousels to unload to only 7~12% a day, and avoid using North-board which leads to enhance the sorting error. As considering the relaxed restrictions in peak time, the most effective ways to reduce the flights that have no carousels to unload baggage are let large flight and medium flight can overlap, and to increase the capacity of carousels. It can reduce the flights that have no carousels to unload baggage to about 0~2% a day. That is, there are only 1 to 3 flights in a day that have no carousels to use which baggage have to be handled by manual operation.
This research considered the scenarios which have stochastic unloading time and probability of flight delay, then prove that stochastic significantly affect the two performance by simulaton validation. Flight delay will increase the flights that can not be assigned, and variability of unloading time will not only result to more flights that can not be assigned, but also increase the overlap time. The algorithm proposed in this research still shows the robustness when there will be variability of unloading time and probability of flight delay by simulaton verification.

並列關鍵字

Baggage Handling System(BHS) ； The unloading zone assignment problem of flight ； Genetic Algorithm(GA) ； Heuristic Algorithm ； Optimal Computing Budget Allocation(OCBA)

參考文獻

1.施昺羲（2015），「機場行李運輸系統航班卸載道指派問題」，國立清華大學工業工程與工程管理研究所碩士論文。

2.鍾唯兌（2015），「機場行李搬運系統管控因子之模擬分析」，國立清華大學工業工程與工程管理研究所碩士論文。

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

5.Abdelmaguid, T. F., Nassef, A. O., Kamal, B. A., & Hassan, M. F. (2004). A hybrid GA/heuristic approach to the simultaneous scheduling of machines and automated guided vehicles. International journal of production research, 42(2), 267-281.

6.Ascó, A., Atkin, J. A., & Burke, E. K. (2014). An analysis of constructive algorithms for the airport baggage sorting station assignment problem. Journal of Scheduling, 17(6), 601-619.