摘要
不正常航班调度是一个非常复杂的实时网络优化问题,属于NP难问题.同时考虑由飞机资源短缺和机场关闭造成的航班不正常情况,采用时空网络技术为每架飞机构建恢复网络,在此基础上将该问题视为带有容量约束的多个商品的整数最小费用流问题,建立了多商品网络流数学模型.采用列生成算法求解该大规模整数规划问题,对于求得的非整数解采用分支定界法进行处理.最后,给出的算例验证了该方法的正确性和有效性.
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 multicommodity 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.
出处
《系统工程理论与实践》
EI
CSSCI
CSCD
北大核心
2010年第11期2036-2045,共10页
Systems Engineering-Theory & Practice
基金
国家自然科学基金(70771046)
中国民航总局应用开发科技项目(MHRD20080640)
关键词
不正常航班
时空网络
多商品网络流
列生成法
disrupted airline schedules
space-time network
multi-commodity network flow
column generation methods
