The Multiple Connections Multi-Airport Ground Holding Problem: Models and Algorithms
针对多机场多航班连接的地面等待问题，构建整数线性规划模型并用CPLEX精确求解，同时提出计算时间仅数秒的启发式算法，在30个实例上误差可接受。
In recent years air traffic has dramatically increased without a corresponding development of airports. Therefore, airports' limited capacity causes air traffic congestion and consequent expensive delays. The only strategy that can be applied in the short term with low investments aims at the optimal management of present resources; its principal device is Ground Holding, which consists of delaying an aircraft take off whenever it is foreseen it will not land in time because of congestion. We consider a traffic situation with “multiple connections” or “banking,” i.e., the situation where some flights are assigned a set of “preceding” flights; no “successive” flight can start until all its preceding flights have landed. The problem consists of distributing delays to flights, so as to minimize the total delay cost, by respecting airport capacity, connections, and time constraints imposed by airlines. We construct an integer linear programming model and we solve it to optimality with CPLEX. Because the computation time is too high (hours) for real-world instances, we propose an alternative heuristic algorithm, which shows a very low computation time (seconds) and acceptable errors when tested on 30 realistic instances with strongly diversified data.