Mixed Set Programming for Crew Pairing

Abstract

Abstract: Crew costs are the second largest direct operating costs in an airline's expenses, only next to fuel costs. However, crew pairing is a highly constrained and complex problem, which makes it extremely difficult to find optimal solutions. In this paper, mixed set programming(MSP)is proposed for the first time to build the model. Quite different from mathematical programming, MSP supports global reasoning over a mixed domain of real numbers, integers, booleans, and sets. Set partitioning model and routing model are the core parts of our model. Computational test shows that problems of real-world size can be solved efficiently within reasonable time.

Key words: crew pairing, mixed set programming, set partitioning, object-oriented modeling

摘要： 机组成本是仅次于燃料成本的第二大直接运营成本,合理的进行机组人员排班对降低航空公司运营成本有着重要意义。然而,机组排班问题是复杂性非常高的组合优化问题,属于NP难题。本文在分析机组排班问题研究进展的基础上,采用混合集合规划方法,综合考虑多种约束,建立了更具有实用性的机组排班优化模型。本文将运筹学理论与业务逻辑相结合,设计了高效的求解策略。利用多组航空公司真实数据对模型进行测试,测试结果表明,模型可以在较短时间内有效求解达到实际应用规模的机组排班问题。

关键词: 机组排班, 混合集合规划, 集合分割, 对象化建模

CLC Number:

LAN Bo-xiong, ZHANG Mi. Mixed Set Programming for Crew Pairing[J]. Operations Research and Management Science, 2014, 23(2): 175-182.

蓝伯雄, 张米. 机组排班的混合集合规划方法研究[J]. 运筹与管理, 2014, 23(2): 175-182.

References

[1] 孙宏,文军.航空公司生产组织与计划[M].成都:西南交通大学出版社,2008.79-107.
[2] Anbil R, Gelman E, Patty B, Tanga R. Recent advances in crew-pairing optimization at american airlines[J]. Interfaces, 1991, 21(1): 62-74.
[3] Barnhart C, Cohn A M, Johnson E L, et al. Airline crew scheduling[M]. Handbook of transportation science: Springer, 2003. 517-560.
[4] Etschmaier M M, Mathaisel D F. Airline scheduling: an overview[J]. Transportation Science,1985, 19(2): 127-138.
[5] 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.
[6] Marsten R E, Shepardson F. Exact solution of crew scheduling problems using the set partitioning model: recent successful applications[J]. Networks, 1981, 11(2): 165-177.
[7] Barnhart C, Johnson E L, Nemhauser G L, et al. Branch-and-price: column generation for solving huge integer program[J]. Operational Research, 1998, 46: 316-329.
[8] Lavoie S, Minoux M, Odier E. A new approach for crew pairing problems by column generation with an application to air transportation[J]. European Journal of Operational Research, 1988, 35(1): 45-58.
[9] Graves G W, McBride R D, Gershkoff I, et al. Flight crew scheduling[J]. Management Science, 1993, 39(6): 736-745.
[10] Gustafsson T. A heuristic approach to column generation for airline crew scheduling[D]. Sweden: Chalmers University of Technology, 1999.
[11] Klabjan D, Johnson E L, Nemhauser G L, et al. Solving large airline crew scheduling problems: random pairing generation and strong branching[J]. Computational Optimization and Applications, 2001, 20(1): 73-91.
[12] Borndorfer R, Schelten U, Schlechte T, et al. A column generation approach to airline crew scheduling[C]. Operations Research Proceedings, 2005. 343-348.
[13] Van Hoai Tran, Gerhard Reinelt, Bock H G. Advanced column generation techniques for crew pairing problems[M]. Modeling, Simulation and Optimization of Complex Processes, 2005. 203-214.
[14] Rousseau L M, Gendreau M, Feillet D. Interior point stabilization for column generation[J]. Operations Research Letters, 2007, 9(35): 660-668.
[15] Beasley J E, Chu P C. A genetic algorithm for the set covering problem[J]. European Journal of Operational Research, 1996, 94: 392-404.
[16] Kornilakis H, Stamatopoulos P. Crew pairing optimization with genetic algorithms[M]. Methods and Applications of Artificial Intelligence: Springer, 2002. 109-120.
[17] Medard C P, Sawhney N. Airline crew scheduling from planning to operations[J]. European Journal of Operational Research, 2007, 183(3): 1013-1027.
[18] AhmadBeygi S, Cohn A, Weir M. An integer programming approach to generating airline crew pairings[J]. Computers & Operations Research, 2009, 36(4): 1284-1298.
[19] Zhou J. Introduction to the constraint language NCL[J]. Journal of Logic Programming, 2000, 45(1-3): 71-103.
[20] Zhou J. The ncl natural constraint language[M]. Springer, 2012.
[21] Colmerauer A. An introduction to prolog III[C]. Computational Logic, Springer Berlin Heidelberg, 1990: 37-79.
[22] Halmos P. R. Naive set theory[M]. Springer, 1960.
[23] Knuth D E, Bibby D. The texbook[M]. Addison-Wesley Reading, MA, USA, 1986.