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

The Network Models for Minimum Airport Gate Number Assignment Problem

顏上堯(Shangyao Yan) ； 杜宇平(Yu-Ping Tu) ； 朱橋榮(Chiao-Rong Chu)

《運輸學刊》 15卷2期 (2003/06) Pp. 149-164

摘要

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

關鍵字

機門指派 ； 多重貨物網路流動問題 ； 拉氏演算法

並列摘要

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, subgradient 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.

並列關鍵字

Gate assignment ； Multiple commodity network flow problem ； Lagrangian algorithm

參考文獻

汪進財 Wong, Jinn-Tsai(1992)。機門指派最佳化模式。運輸計劃季刊 Transportation Planning Journal。21(2)

汪進財 Wong, Jinn-Tsai盧清泉 Lu, Ching-Chyuan(1994)。中正機場機坪運轉分析。運輸 Transportation。25

汪進財 Wong, Jinn-Tsai張束珍(1996)。動態機門指派績效評估。運輸計劃季刊 Transportation Planning Journal。25(1)

周義華 Chou, Yi-Hwa夏武正 Chia, Wu-Cheng(1999)。航空站停機位需求之估計。運輸計劃季刊 Transportation Planning Journal。28(4)

陳春益 Chen, Chuen-Yih李宇欣 Lee, Yu-Sin盧華安 Lu, Hua-An(1997)。時空網路應用於機門指派問題之研究。運輸學刊 Journal of the Chinese Institute of Transportation。10(3)