機門數量最少化網路模式之研究

The Network Models for Minimum Airport Gate Number Assignment Problem

機場機門之數量與使用效率，為影響機場營運績效及服務水準的關鍵因素之一。在日常營運中，最少機門數常為機場當局重要參考指標之一。在傳統實務上對於飛機停靠機門的指派，太多以人工經驗方式處理，較缺乏系統性及最佳化觀念之分析，而以往學者所提的最佳化機門指派模式，並未以最少機門數作為規劃目標之研究，緣此，本研究利用一新式網路流動技巧，以最少機門數為目標，先建立一單機型機門指派基本模式。此模式為一純網路問題，本研究以網路單體法求解此模式。之後，本研究再參考一般實務界常用之多機型機門停靠及航械地面等候策略，發展多機型機門及航機等候之營運策略模式。此網路模式可定式為多重貨物網路流動問題。為有效求解實務上所面臨之大規模問題，本研究利用拉氏演算法架構，綜合網路單體法、自行發展之啟發式解法及次梯度法，發展一求解演算法，求解此策略模式。最後，本研究以國內一主要國際機場之營運資料為例，進行測試分析，結果顯示本研究所提出之機門指派模式反求解演算法的效果甚佳。

The number of gates and their usage efficiency are essential to an airport level of service. In short-term operations under congestion, what is the minimum number of gates that can operate all flights in peak periods in an airport? The topic is always important to airport authorities. In tradition, airport authorities usually assign flights to gates in a manual way, which lacks of systematic and optimal analysis. Although academic researchers have proposed some optimal gate assignment models, these models did not aim at minimizing the number of gates. In this research, we attempt to employ the network flow techniques to develop two gate assignment models, to solve the minimum number of gates for the airport short-term operation. We first construct a basic model. Referring to multiple aircraft types and ground holding strategies used in practices, we then develop a strategic model based on the basic model, in order to solve the minimum number of gates. The model is formulated as network flow problems with side constraints or multiple commodity network problems, which are characterized as NP-hard in terms of optimization. To efficiently solve large-scale problems in practices, we develop a Lagrangian algorithm based on Lagargian relaxation, sub gradient methods, network simplex method and other heuristics. Finally, to evaluate the models and the solution algorithms developed in the research, we perform a case study using data from a Taiwan international airport. The results show the good performance of the models and the solution algorithm.