基于列生成法的不正常航班调度

不正常航班调度是一个非常复杂的实时网络优化问题,属于NP难问题.同时考虑由飞机资源短缺和机场关闭造成的航班不正常情况,采用时空网络技术为每架飞机构建恢复网络,在此基础上将该问题视为带有容量约束的多个商品的整数最小费用流问题,建立了多商品网络流数学模型.采用列生成算法求解该大规模整数规划问题,对于求得的非整数解采用分支定界法进行处理.最后,给出的算例验证了该方法的正确性和有效性.

Disrupted airline schedules dispatching based on column generation methods

The dispatching of disrupted airline schedules is a very complicated real-time network optimization problem, which belongs to NP-complete problem. Considering the situation caused by both the shortage of aircraft resources and the closure of airports, this paper adopts time-space network technique to construct the recovery network for each aircraft. Based on this, the problem is considered as a multi-commodity integer minimum cost flow with the side constraints, so a mathematic model of multi-commodity network flow is established. Column generation methods are introduced to solve this large integer programming problem, and the branch and bound algorithm is used to handle the non-integer solutions. Finally, a given instance analyzed in details validates the correctness and efficiency of the method.