因應班機延遲之最佳化即時機門指派

Optimized Airport Gate Reassignment for Delayed Flights

盧華安(Hua-An Lu)

《運輸計劃季刊》 30卷4期 (2001/12) Pp. 849-869

https://doi.org/10.6402/TPJ.200112.0849

摘要

班機延遲常干擾機場作業之正常運作，當延遲效應足以嚴重影響後續班次作業時，機門重新指派(gate reassignment)工作將扮演紓解擁擠的重要角色。理論上，針對延遲班機進行機門重新指派的結果，應能使其對機場運作的影響減至最低；實務上，卻不得不將部分正常班機也一併考慮，甚至必須藉助遠端停機坪或其他臨時的停機位置，以因應臨時而連續改變的起降班次。本研究旨於探討機場發生嚴重之延遲時，機門重新指派之作業特性，並利用數學規劃構建適當的決策模式。該模式藉時空網路(time-space network)概念表達不同班次指派給機門之可行性，以追求最小化之重新指派成本。測試結果驗證本研究之模式可獲得正確之指派，且在一定規模下以分支限界法(branch-and-bound algorithm)即可快速獲得最佳解；但在處理大規模問題時，演算所費時間仍相當可觀。本研究以拉氏鬆弛法(Lagrangian relaxation)與次梯度演算(subgradient technique)為基礎，發展－拉氏啟發式演算法，其測試結果與最佳解之差距有限，且所需之計算時間隨問題規模穩定微增，演算績效堪稱良好。

關鍵字

機門重新指派 ； 時空網路 ； 分支限界法 ； 拉氏鬆弛法 ； 次梯度演算

並列摘要

Many airport operations are disrupted or forced to change their original plan when flights are delayed. Reassigning gates to those airplanes plays a crucial role in recovering the normal situation from the mess, when it is estimated to be going to keep a long time. Ideally, the optimal reassignment plan can reduce the impact to airport operations to the least level. However, their processes also need to take other normal flights into consideration in real-world cases. When necessary, some airplanes can park on remote bays to reduce the congestion of consecutive flights within a specified period. In this research, we discuss the properties of gate reassignment operations and formulate a model for integer programming, constructed from a concept of the time-space network, to minimize the total difference of reassigning cost. Test results show that this model can be efficiently solved directly by the branch-and-bound algorithm under certain problem scale. A heuristics based on the Lagrangian relaxation and subgradient technique is also suggested to treat the large-scale problems. The reasonable gaps of objective values exist between this heuristics and the branch-and-bound algorithm, but less CPU time is spent by the heuristics in larger problems.

並列關鍵字

Gate reassignment ； Time-space network ； Branch-and-bound algorithm ； Lagrangian relaxation ； Subgradient technique

參考文獻

Ahuja, R. K.Magnanti, T. L.Orlin, J. B.(1993).Network Flows - Theory, Algorithms and Applications.Englewood Cliffs, New Jersey:Prentice-Hall.

Babic, O.Teodorovic, D.Tosic, V.(1984).Aircraft stand assignment to minimize walking.Journal of Transportation Engineering.110

Bihr, R. A.(1990).A Conceptual Solution to the Aircraft Gate Assignment Problem Using 0, 1 Linear Programming.Computers and Industry Engineering.19(1-4)

Bolat, A.(2000).Procedures for Providing Robust Gate Assignments for Arriving Aircrafts.European Journal of Operational Research.120

ILOG, Inc. CPLEXDivision(1998).Using the CPLEX Callable Library.