机场航班航线调度优化管理仿真研究

Research on Simulation of Airport Flight Scheduling Optimization Management

飞机航线调度是航空公司组织生产计划活动的关键环节,由于问题的复杂性,是民航界著名的NP难题,合理的航线调度保障航空公司的经济效益。针对机场航班航线调度优化做出研究,首先将飞机航线调配问题进行数学建模,通过引入满足限制条件的有向无环图来定义等图,证明飞机航线调配问题与等图的路径查找问题是等价的,等图的路径查找问题即为满足特定限制条件的图的路径划分问题。随后将飞机的维护限制条件附加到等图中构造出网络状态图,根据对网络状态图的路径划分问题得到飞机航线调配问题的可行解。提出基于网络状态图的线性规划模型,设计成本最小化和飞机使用均衡求解目标函数,提出了不同于列生成方法的基于网络状态图的线性规划求解方法。使用国内某航空公司真实航班数据对提出的方法模型进行了仿真研究,仿真结果表明该方法能够得到经济合理的飞机调度方案,能够为航空公司提供决策支持。

Aircraft routing problem is one of the key factors that affect the operation efficiency of airline compa- nies. It is often referred to be a famous NP-complete problem in civil aviation. Reasonable flight scheduling plans ensure the economic benefits of airlines. Firstly, the aircraft routing problem was expressed in mathematical lan- guage, an equigraph was defined using the directed acyclic graph satisfying several constraints. It was proved that the aircraft routing problem is equivalent to an equigraph routing problem. Equigraph routing problem is a path partition problem on a graph with additional constraints. Then the state graph was built and applied to aircraft routing problem. Finally, a new compact integer linear formulation for aircraft routing was proposed. Then, the goal of using balanced and cost minimization was designed, which is different from the traditional column generation method, and the simula- tion was verified by field data from one airline＂ trunk flight network in china. The simulation results show that the method is feasible and can provide decision support for airlines.