時空網路應用於機門指派問題之研究

A Time-Space Network Model for the Airport Gate Assignment Problem

傳統上，機門指派之最佳化模式，大多被構建成整數規劃問題，如應用於實務問題上，每每成為大型問題而無法快速求解。近來，該問題被定式為多元商品流量問題，遭遇大型問題演算績效不佳之課題。本研究嘗試運用時空網路協助模式構建，所建模式為具額外限制式之成本小化流量問題，該額外限制式為變數間之流量對稱等式限制，改善了模式構建的複雜性。經以分支定限法求解苦干範例與中正機場簡化實例，所得線性規劃之實數解即為整數最佳解，測試結果亦顯示該模式確能提供合理的指派結果。

The airport gate assignment problem is conventionally modeled as aninteger programming problem and is heuristically solved for real-world cases.Recently, it had been formulated as a multicommdity flow problem. However, areal-time algorithm is needed. In this paper, we make use of the time-spacenetwork to formulate it as a minimum cost flow problem with side contraints, aset of flow equality constraints. Fruthermore, integer solutions can beobtained at the first phase without branching with the branch-and -boundalgorithm in our case studies. The experimental result shows that our model ispromising.