×

zbMATH — the first resource for mathematics

Accelerating column generation for aircraft scheduling using constraint propagation. (English) Zbl 1086.90023
Summary: We discuss how constraint programming can improve the performance of a column generation solution process for the NP-hard tail assignment problem in aircraft scheduling. Combining a constraint model of a relaxed Tail Assignment problem with column generation, we achieve substantially improved performance. A generalized preprocessing technique based on constraint propagation is presented that can dramatically reduce the size of the flight network. We also present a heuristic preprocessing method based on the costs of connections, and show how constraint propagation can be used to improve fixing heuristics. Proof of concept is provided using real world Tail Assignment instances.

MSC:
90B35 Deterministic scheduling theory in operations research
90C90 Applications of mathematical programming
Software:
CPLEX
PDF BibTeX Cite
Full Text: DOI
References:
[1] Bockmayr, A.; Kasper, T., Branch and infera unifying framework for integer and finite domain constraint programming. INFORMS journal on computing, 10, 3, 287-300, (1998) · Zbl 1034.90517
[2] Caprara, A.; Focacci, F.; Lamma, E.; Mello, P.; Milano, M.; Toth, P.; Vigo, D., Integrating constraint logic programming and operations research techniques for the crew rostering problem, Software – practice and experience, 28, 1, 49-76, (1998)
[3] Fahle, T.; Junker, U.; Karisch, S.; Kohl, N.; Sellmann, M.; Vaaben, B., Constraint programming based column generation for crew assignment, Journal of heuristics, 8, 1, 59-81, (2002) · Zbl 1073.90542
[4] Hajian, M.; El-Sakkout, H.; Wallace, M.; Richards, E.; Lever, J., Towards a closer integration of finite domain propagation and simplex-based algorithms, Annals of operations research, 81, 421-431, (1998) · Zbl 0906.90146
[5] Ottosson G. Integration of constraint programming and integer programming for combinatorial optimization. PhD thesis, Uppsala University, Uppsala; 2000.
[6] Rodosek, R.; Wallace, M.G.; Hajian, M.T., A new approach to integrating mixed integer programming and constraint logic programming, Annals of operations research, 86, 63-87, (1999) · Zbl 0918.90109
[7] Hane, C.A.; Barnhart, C.; Johnson, E.L.; Marsten, R.E.; Nemhauser, G.L.; Sigismondi, G., The fleet assignment problemsolving a large-scale integer program, Mathematical programming, 70, 211-232, (1995) · Zbl 0840.90104
[8] Hjorring C. Integrating fleet and crew planning. Presentation at 41st AGIFORS annual symposium, Sydney, Australia, 2001.
[9] Gopalan, R.; Talluri, K.T., The aircraft maintenance routing problem, Operations research, 46, 2, 260-271, (1998) · Zbl 0987.90521
[10] Clarke, L.W.; Johnson, E.L.; Nemhauser, G.L.; Zhu, Z., The aircraft rotation problem, Annals of operations research, 69, 33-46, (1997) · Zbl 0880.90036
[11] Grönkvist M. Tail assignment—a combined column generation and constraint programming approach. Lic. thesis, Chalmers University of Technology, Gothenburg, Sweden; 2003.
[12] Feo, T.A.; Bard, J.F., Flight scheduling and maintenance base planning, Management science, 35, 12, (1989)
[13] Barnhart, C.; Boland, N.L.; Clarke, L.W.; Johnsson, E.L.; Nemhauser, G.L.; Shenoi, R.G., Flight string models for aircraft fleeting and routing, Transportation science, 32, 3, 208-220, (1998) · Zbl 0987.90504
[14] Desaulniers, G.; Desrosiers, J.; Dumas, Y.; Solomon, M.M.; Soumis, F., Daily aircraft routing and scheduling, Management science, 43, 6, 841-855, (1997) · Zbl 0890.90057
[15] Rousseau L-M, Gendreau M, Pesant G. Solving small VRPTWs with constraint programming based column generation. In: Proceedings of CPAIOR’02, March 2002. · Zbl 1062.90007
[16] Focacci F, Lodi A, Milano M, Vigo D. Solving TSP through the integration of OR and CP techniques. In: Wallace M, Caseau Y, Jacquet-Lagreze E, Simonis H, Pesant G, editors, Electronic notes in discrete mathematics, vol. 1. Elsevier; 1999. · Zbl 0990.90553
[17] Milano M, Ottosson G, Refalo P, Thorsteinsson ES. The role of integer programming techniques in constraint programming’s global constraints. INFORMS Journal on Computing, Special Issue on “The Merging of Mathematical Programming and Constraint Programming” 2002; 14(4). · Zbl 1238.90101
[18] Ahuja, R.K.; Magnanti, T.L.; Orlin, J.B., Network flows, (1993), Prentice Hall Englewood Cliffs, NJ · Zbl 1201.90001
[19] Dantzig, G.B.; Wolfe, P., Decomposition principle for linear programs. operations research, 8, 101-111, (1959) · Zbl 0093.32806
[20] Gamache, M.; Soumis, F.; Marquis, G.; Desrosiers, J., A column generation approach for large-scale aircrew rostering problems, Operations research, 47, 2, 247-263, (1999) · Zbl 1041.90513
[21] Hjorring C, Hansen J. Column generation with a rule modelling language for airline crew pairing. In: Proceedings of the 34th annual conference of the operational research society of New Zealand, Hamilton, New Zealand, December 1999. p. 133-42.
[22] Desrochers, M.; Soumis, F., A generalized permanent labelling algorithm for the shortest path problem with time windows, Infor, 26, 3, 191-212, (1988) · Zbl 0652.90097
[23] Barnhart, C.; Johnson, E.L.; Nemhauser, G.L.; Savelsbergh, M.W.; Vance, P.H., Branch-and-pricecolumn generation for solving huge integer programs, Operations research, 46, 3, 316-329, (1998) · Zbl 0979.90092
[24] Régin J-C. A filtering algorithm for constraints of difference in CSPs. In: Proceedings of AAAI-94. 1994. p. 362-7.
[25] Kilborn E. Aircraft scheduling and operation – a constraint programming approach. Master’s thesis, Chalmers University of Technology, Gothenburg, Sweden; 2000.
[26] Ilog Inc. CPLEX 7.1 Reference Manual, 2001. http://www.ilog.com/
[27] Ilog Inc. Solver 5.0 Reference Manual, 2001. http://www.ilog.com/
[28] Régin J-C. Generalized arc consistency for global cardinality constraint. In: Proceedings of AAAI-96. 1996. p. 209-15.
[29] Régin J-C., Arc consistency for global cardinality constraints with costs. In: Jaffar J, editor. Principles and practice of constraint programming, vol. 1713, Lecture Notes in Computer Science. Springer, 1999.
[30] Jarrah, A.I.; Goodstein, J.; Narasimhan, R., An efficient airline re-fleeting model for the incremental modification of planned fleet assignments, Transportation science, 34, 4, 349-363, (2000) · Zbl 1014.90060
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.