机组排班是航空公司运营计划的重要环节。传统对机组排班问题的研究,通常不考虑延误对排班的影响,导致机组排班的鲁棒性较差。本文在传统机组排班模型的基础上考虑延误成本,以最小化各项任务成本和延误成本为目标,提出了考虑随机延误因素的机组排班数学规划模型。然后提出求解此模型的启发式列生成算法,该算法可有效缩小问题规模,减少求解过程中的迭代次数并提高求解质量。利用航空公司真实飞行数据进行测试,证明算法可在短时间内求解大规模机组排班问题。最后,通过仿真试验证实考虑延误的机组排班模型可有效提升排班的鲁棒性。
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.
[1] Etschmaier M M,Mathaisel D F. Airline scheduling:An overview[J]. Transportation Science,1985, 19(2):127-138.
[2] Ernst A T, Jiang H, Krishnamoorthy M,Sier D. Staff scheduling and rostering:A review of applications, methods and models[J]. European Journal of Operational Research,2004, 153(1):3-27.
[3] 李雄, 刘光才, 颜明池,等. 航班延误引发的航空公司及旅客经济损失[J]. 系统工程, 2007,25(12):20-23.
[4] Rosenberger J, Schaefer A, Golldsman D, et al. A stochastic model of airline operations[J]. Transportation Science,2003, 36(4):357-377.
[5] Eggenberg N, Salani M,Bierlaire M. Uncertainty feature optimization:An implicit paradigm for problems with noisy data[J]. Networks,2011,57(3):270-284.
[6] Eggenberg N,Salani M. Uncertainty feature optimization for the airline scheduling problem[R]. Working Paper,Transport and Mobility Laboratory,2009.
[7] Shebalov S,Klabjan D. Robust airline scheduling:Move-up crews[J]. Transportation Science,2006, 40(3):300-312.
[8] Yen J W,Brige J R. A stochastic programming approach to the airline crew scheduling problem[J]. Transportation Science,2006, 40(1):3-14.
[9] Dück V, Ionescu L, Kliewer N, et al.Increasing stability of crew and aircraft schedules[J]. Transportation research part C:Emerging Technologies, 2012, 20(1):47-61.
[10] Muter ?, ?lker Birbil ?, Bülbül K, et al. Solving a robust airline crew pairing problem with column generation[J]. Computers & Operations Research, 2013, 40(3):815-830.
[11] Dunbar M, Froyland G, Wu C L. An integrated scenario-based approach for robust aircraft routing, crew pairing and re-timing[J]. Computers & Operations Research, 2014, 45(5):68-86.
[12] 牟德一, 王志新, 夏群. 基于机组延误概率的鲁棒性机组配对问题[J]. 系统管理学报, 2011, 20(2):207-212.
[13] Mou Deyi, Zhang Yingnan. Multi-objective integer programming model and algorithm of the crew pairing problem in a stochastic environment[J]. WSEAS Transactions on Mathematics, 2013, 12(8):809-818.
[14] Lan Shan, Clarke J P, Barnhart C. Planning for robust airline operations:Optimizing aircraft routings and flight departure times to minimize passenger disruptions[J]. Transportation Science, 2006, 40(1):15-28.
[15] Rubin J. A technique for the solution of massive set-covering problems with application to airline crew scheduling[J]. Transportation Science,1973, 7(1):34-48.
[16] Hoai T V, Reinelt G, Bock H G. Advanced column generation techniques for crew pairing problems[M]//Bock H G,Phu H X, Kostina E,et al. Modeling, simulation and optimization of complex processes, 2005:203-214.
[17] Gopalan R,Talluri K T. The aircraft maintenance routing problem[J]. Operations Research,1998, 46(2):260-271.
[18] Yu Gang, Arguello M,Song Gao,et al. A new era for crew scheduling recovery at continental airlines[J]. Interfaces,2003, 33(1):5-22.
