A Dynamic Multi-Commodity Flow Optimization Algorithm for Estimating Airport Network Capacity

摘要

Estimating the capacity of an airport network system is an NP-hard problem. It is defined as the maximum traffic that can be accommodated by a network of airports subjected to resource constraints, such as fleet mix and node/link capacity. Mathematically, the problem is modeled as a classical multi-commodity flow (MCF) problem. In MCF it is generally considered that the resources required by the commodities at a node or link cannot change over time and must be independent of the interaction among the commodities. However, in an airport network, the local resource requirements for aircrafts usually change over time due to different weather condition, runway configurations, and different aircraft mix. In addition, in a given airport network, the flow requires a certain amount of time to travel through each link and can't be assumed to travel instantaneously through the network as in the case of an electricity network. These complexities deem existing MCF algorithms inapplicable to estimate the flow capacity of an airport network. To address this problem, we propose a new method to estimate the capacity of an airport network and develop a dynamic multi-commodity flow optimization algorithm. The proposed optimization algorithm is augmented by an iterative Hill-Climber algorithm to solve the network capacity model in which all flow constraints of air traffic are preserved. Experimental results show that the proposed model is not only capable of realistically estimating the airport network capacity under different levels of aircraft mix but also in identifying individual flows at different links and amount of delay for each aircraft.