基于最小费用流模型的不正常航班恢复问题研究

突发事件会导致航班计划无法按原计划执行，给航空公司及旅客带来巨大损失。而航班恢复问题的难点除了相关因素的复杂性，主要的体现在恢复方案的即时性。因此，为了提出快速有效的航班恢复方案，以降低损失，笔者通过时空网络技术对不正常航班的恢复问题进行描述，实现了对航班在空间和时间上的追踪。基于最小费用流模型，建立了以最小总延误时间为目标函数的整数规划模型，模型同时考虑了航班延误，飞机置换及航班取消的调度策略，并提出采用Floyd-Warshall算法对建立的模型进行求解。最后，通过算例对模型及算法进行验证。研究结果表明：针对突发状况，建立的模型及算法可提出合理的航班恢复方案，证明了模型及算法的可行性及有效性。建立的模型具有普适性，对不正常航班恢复问题的研究具有借鉴意义。

Research on irregular flight recovery based on minimumcost flow model

The occurrence of unexpected incidents will cause flight plan failure to be carried out as planned,which will bring huge losses to airlines and passengers. In addition to the complexity of related factors, the difficulty in the flight recovery problem is mainly reflected in the immediacy of the recovery scheme.Therefore, in order to propose a quick and effective flight recovery plan to reduce the related losses, this paper described the recovery of irregular flight through space-time network technology, and realized the tracking of flights in space and time. Based on the minimumcost flow model, an integer programming model with the minimum delay time as the objective function was established. The model also considered the scheduling strategies of flight delay, aircraft replacement and flight cancellation. The Floyd-Warshall algorithm was proposed to solving the established model. Finally, the model and algorithm were verified by an example. The results show that for the emergency situation, the model and algorithm established in this paper can provide a reasonable flight recovery scheme, and the model and algorithm are feasible and availability. The model established in this paper has a general applicability, and it has certain reference significance for the study of the problem of recovery of abnormal flights.