一种修复多机型飞机运行计划的分布式整数规划方法

摘要

在航空公司各条航线的日常运行中时常会受到飞机故障或极端天气等各种干扰从而引起航班延误或取消等现象。为减少干扰给航空公司带来的损失，一种分布式整数规划方法被用来修复受干扰的飞机运行计划，从而使延误航班或取消航班的数量降到最低。首先建立一个基于TSP模型的可行性问题用来生成可行航线。之后在MPI搭建的一个多机分布式计算网络上使用递增映射迭代方法对此问题进行求解。最后将求解得到的可行航线指派给飞机从而得到飞机运行修复计划。通过算例结果比较可以看出此分布式整数规划方法要好于一些文献中同类型方法。%The execution of the airline operation is often deviated from the original schedule due to some unexpected disruptions such as aircraft breakdowns and severe weather conditions.To reduce the losses of the airlines incurred from the disruption, a distributed integer programming is employed to recover the disturbed aircrafts operating schedule so as to minimise the amount of the delayed or cancelled flights. First, a TSP-based feasibility problem is set up to generate feasible flight routes, then the incrementally mapped iterative means is applied to find the solution of this problem on a multi-computer distributed computation network built with MPI.Finally, the feasible flight routes derived from the solution are reassigned to the aircrafts so as to get the recovery plan of aircrafts operation.It can be found from the numerical results comparison that this distributed integer programming approach performs better than some other approaches in literature.