考虑延误因素的机组排班模型研究

Airline Crew Pairing Model with Stochastic Disruptions

机组排班是航空公司运营计划的重要环节。传统对机组排班问题的研究,通常不考虑延误对排班的影响,导致机组排班的鲁棒性较差。本文在传统机组排班模型的基础上考虑延误成本,以最小化各项任务成本和延误成本为目标,提出了考虑随机延误因素的机组排班数学规划模型。然后提出求解此模型的启发式列生成算法,该算法可有效缩小问题规模,减少求解过程中的迭代次数并提高求解质量。利用航空公司真实飞行数据进行测试,证明算法可在短时间内求解大规模机组排班问题。最后,通过仿真试验证实考虑延误的机组排班模型可有效提升排班的鲁棒性。

The crew pairing problem is one of the fundamental elements in strategic planning of airline companies. So far, crew pairing is mostly modeled as a deterministic problem, not concerning about flight delays. However, the airline industry is currently under great pressure to improve its on-time performance, so researches on robust models and solutions are in great need. Based on the literature review, a robust crew pairing model with consideration of stochastic disruptions is proposed in this paper. A deeper analysis of interdependencies of flight delays is given first in order to model the problem more accurately. For the purpose of better evaluating the costs caused by flight delays, delay costs are distinguished into normal delay cost and cancel cost according to whether those delays would result in partial flights cancellation. Due to the complexity of the crew paring problem itself, as well as the stochastic and interdependent features of flight delays, it is highly difficult to find feasible or optimal solutions of the model. Therefore, a heuristic column generation algorithm is introduced in this paper, which is proved to be highly efficient. The computational test shows that problems of real-world size can be solved efficiently within reasonable time. Furthermore, simulations are given to compare performances of our model with traditional deterministic model under same disruptions, and the results show that our model could highly increase robustness of crew pairing process.