Abstract
The Airline Crew Assignment Problem (ACA) consists of assigning lines of work to a set of crew members such that a set of activities is partitioned and the costs for that assignment are minimized. Especially for European airline companies, complex constraints defining the feasibility of a line of work have to be respected. We developed two different algorithms to tackle the large scale optimization problem of Airline Crew Assignment. The first is an application of the Constraint Programming (CP) based Column Generation Framework. The second approach performs a CP based heuristic tree search. We present how both algorithms can be coupled to overcome their inherent weaknesses by integrating methods from Constraint Programming and Operations Research. Numerical results show the superiority of the hybrid algorithm in comparison to CP based tree search and column generation alone.
Similar content being viewed by others
References
C. Barnhart, E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh and P.H. Vance, Branch-and-price: Column generation for solving huge integer programs, Operations Research 46(3) (1998) 316-329.
A. Caprara, F. Focacci, E. Lamma, P. Mello, M. Milano, P. Toth and D. Vigo, Integrating constraint logic programming and operations research techniques for the crew rostering problem, Software-Practice and Experience 28(1) (1998) 49-76.
A. Caprara, P. Toth, D. Vigo and M. Fischetti, Modeling and solving the crew rostering problem, Operations Research 46(6) (1998) 820-830.
P.R. Day and D.M. Ryan, Flight attendant rostering for short-haul airline operations, Operations Research 45(5) (1997) 649-661.
T. Fahle, U. Junker, S.E. Karisch, N. Kohl, M. Sellmann and B. Vaaben, Constraint programming based column generation for crew assignment, Journal of Heuristics 8(1) (2002) 59-81.
M. Gamache, F. Soumis, D. Villeneuve, J. Desrosiers and E. Gélinas, The preferential bidding system at Air Canada, Transportation Science 32(3) (1998) 246-255.
M.R. Garey and D.S. Johnson, Computers and Intractability (Freeman, New York, 1979).
W.D. Harvey and M.L. Ginsberg, Limited discrepancy search, in: Proceedings of the IJCAI '95 (1997) pp. 607-613.
ILOG, ILOG SOLVER. Reference manual and user manual. V4.4, ILOG, 1999.
ILOG, ILOG CPLEX. Reference manual and user manual. V6.5, ILOG, 1999.
U. Junker, S.E. Karisch, N. Kohl, B. Vaaben, T. Fahle, and M. Sellmann, A framework for constraint programming based column generation, in: Proceedings of the CP '99, Lecture Notes in Computer Science, Vol. 1713 (Springer, Berlin, 1999) pp. 261-274.
R.A. Rushmeier, K.L. Hoffman and M. Padberg, Recent advances in exact optimization of airline scheduling problems, Technical Report, George Mason University (1995).
D.M. Ryan, The solution ofmassive generalized set partitioning problems in aircrew rostering, Journal of the Operational Research Society 43(5) (1992) 459-467.
J. Schulze and T. Fahle, A parallel algorithm for the vehicle routing problem with time window constraints, Annals of Operations Research 86 (1999) 585-607.
M. Sellmann, K. Zervoudakis, P. Stamatopoulos and T. Fahle, Integrating direct CP search and CP-based column generation for the airline crew assignment problem, in: Proceedings of the CP-AIOR '00, Paderborn Center for Parallel Computing, Technical Report tr-001-2000 (2000) pp. 163-170.
P. Shaw, Using constraint programming and local search methods to solve vehicle routing problems, in: Proceedings of the CP '98, Lecture Notes in Computer Science, Vol. 1520 (Springer, Berlin, 1998) pp. 417-431.
P. Stamatopoulos, G. Boukeas, K. Zervoudakis, V. Stoumpos and C. Halatsis, Parallel CP-based direct crew rostering, PARROT Deliverable D-TEC2.1, University of Athens, University of Paderborn (1999).
T.Walsh, Depth-bounded discrepancy search, in: Proceedings of the IJCAI '97 (1997) pp. 1388-1393.
G. Yu (ed.), Operations Research in the Airline Industry, International Series in Operations Research and Management Science, Vol. 9 (Kluwer Academic, Dordrecht, 1998).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Sellmann, M., Zervoudakis, K., Stamatopoulos, P. et al. Crew Assignment via Constraint Programming: Integrating Column Generation and Heuristic Tree Search. Annals of Operations Research 115, 207–225 (2002). https://doi.org/10.1023/A:1021105422248
Issue Date:
DOI: https://doi.org/10.1023/A:1021105422248