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

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

關鍵字

機門指派；多元商品流量問題；時空網路；具額外限制式之成本最小化流量問題；分支定限法

並列摘要

The airport gate assignment problem is conventionally modeled as an integer programming problem and is heuristically solved for real-world cases. Recently, it has been formulated as a multicommodity flow problem. However, a real-lime algorithm is needed. In this paper, we make use of the time-space network to formulate it as a minimum cost flow problem with side constraints, a set of flow equality constraints. Furthermore, integer solutions can be obtained at the first phase without branching with the branch-and-bound algorithm in our case studies. The experimental result shows that our model is promising.

並列關鍵字

Airport Gate Assignment ； Multicommodity Flow Problem ； Time-Space Network ； Minimum Cost Flow Problem with Side Constraints ； Branch-and-Bound Algorithm

主題瀏覽