×

zbMATH — the first resource for mathematics

Combining column generation and constraint programming to solve the tail assignment problem. (English) Zbl 1179.90207
Summary: Within the area of short term airline operational planning, Tail Assignment is the problem of assigning flight legs to individual identified aircraft while satisfying all operational constraints, and optimizing some objective function. In this article, we propose that Tail Assignment should be solved as part of both the short and the long term airline planning. We further present a hybrid column generation and constraint programming solution approach. This approach can be used to quickly produce solutions for operations management, and also to produce close-to-optimal solutions for long and mid term planning scenarios. We present computational results which illustrate the practical usefulness of the approach.

MSC:
90B80 Discrete location and assignment
Software:
CPLEX
PDF BibTeX Cite
Full Text: DOI
References:
[1] Ahuja, R. K., Liu, J., Goodstein, J., Mukherjee, A., Orlin, J. B., & Sharma, D. (2003). Solving multi-criteria combined through fleet assignment models. In T. A. Ciriani, G. Fasano, S. Gliozzi, & R. Tadei (Eds.), Operations research in space and air (pp. 233–256). Dordrecht: Kluwer Academic. · Zbl 1051.90514
[2] Barnhart, C., Boland, N. L., Clarke, L. W., Johnson, E. L., Nemhauser, G. L., & Shenoi, R. G. (1998a). Flight string models for aircraft fleeting and routing. Transportation Science, 32(3), 208–220. · Zbl 0987.90504
[3] Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998b). Branch-and-Price: Column generation for solving huge integer programs. Operations Research, 46(3), 316–329. · Zbl 0979.90092
[4] Berge, M. E., & Hopperstad, C. A. (1993). Demand driven dispatch: a method for dynamic aircraft capacity assignment, Models and Algorithms. Operations Research, 41(1), 153–168. · Zbl 0775.90146
[5] Clarke, L. W., Johnson, E. L., Nemhauser, G. L., & Zhu, Z. (1997). The aircraft rotation problem. Annals of Operations Research, 69, 33–46. · Zbl 0880.90036
[6] Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8, 101–111. · Zbl 0093.32806
[7] Dash Optimization Ltd.: (2002). Xpress-Optimizer Reference Manual, release 14.
[8] Desaulniers, G., Desrosiers, J., & Solomon, M. M. (1999). Accelerating strategies in column generation methods for vehicle routing and crew scheduling problems. Les Cahiers du GERAD G-99-36, GERAD. · Zbl 1017.90045
[9] Desrochers, M., & Soumis, F. (1988). A generalized permanent labelling algorithm for the shortest path problem with time windows. INFOR, 26(3), 191–212. · Zbl 0652.90097
[10] du Merle, O., Villeneuve, D., Desrosiers, J., & Hansen, P. (1999). Stabilized column generation. Discrete Mathematics, 194, 229–237. · Zbl 0949.90063
[11] Elf, M., Jünger, M., & Kaibel, V. (2003). Rotation planning for the continental service of a European airline. In W. Jager & H. J. Krebs (Eds.), Mathematics–key technologies for the future. Joint projects between universities and industry (pp. 675–689). Berlin: Springer. · Zbl 1077.90505
[12] Even, S., Itai, A., & Shamir, A. (1976). On the complexity of timetable and multicommodity flow problems. SIAM Journal on Computing, 5(4), 691–703. · Zbl 0358.90021
[13] Fahle, T., Junker, U., Karisch, S. E., Kohl, N., Sellmann, M., & Vaaben, B. (2002). Constraint programming based column generation for crew assignment. Journal of Heuristics, 8(1), 59–81. · Zbl 1073.90542
[14] Foster, B. A., & Ryan, D. M. (1981). An integer programming approach to scheduling. In A. Wren (Ed.), Computer scheduling in public transport (pp. 269–280). Amsterdam: North-Holland.
[15] Gamache, M., Soumis, F., Marquis, G., & Desrosiers, J. (1999). A column generation approach for large-scale aircrew rostering problems. Operations Research, 47(2), 247–263. · Zbl 1041.90513
[16] Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: a guide to the theory of np-completeness. San Fransisco: Freeman. · Zbl 0411.68039
[17] Gopalan, R., & Talluri, K. T. (1998). The aircraft maintenance routing problem. Operations Research, 46(2), 260–271. · Zbl 0987.90521
[18] Grönkvist, M. (2003). Tail assignment–a combined column generation and constraint programming approach. Lic. thesis, Department of Computing Science, Chalmers University of Technology, Gothenburg, Sweden.
[19] Grönkvist, M. (2004). A Constraint programming model for tail assignment. In Lecture notes in computer science: Vol. 3011. Proceedings of CPAIOR’04 (pp. 142–156). Berlin: Springer. · Zbl 1094.68644
[20] Grönkvist, M. (2005). The Tail Assignment Problem. Ph.D. thesis, Department of Computing Science, Chalmers University of Technology, Gothenburg, Sweden. · Zbl 1094.68644
[21] Grönkvist, M. (2006). Accelerating column generation for aircraft scheduling using constraint propagation. Computers & Operations Research, 33(10), 2918–2934. · Zbl 1086.90023
[22] Hane, C. A., Barnhart, C., Johnson, E. L., Marsten, R. E., Nemhauser, G. L., & Sigismondi, G. (1995). The fleet assignment problem: solving a large-scale integer program. Mathematical Programming, 70, 211–232. · Zbl 0840.90104
[23] Hjorring, C. A. (2004). Solving larger crew pairing problems. In Proceedings of TRISTAN V: the fifth triennial symposium on transportation analysis. Le Gosier, Guadeloupe. · Zbl 1203.90091
[24] ILOG Inc.: (2001). ILOG CPLEX 7.5 Reference Manual.
[25] Jarrah, A. I., & Strehler, J. C. (2000). An optimization model for assigning through flights. IIE Transactions, 32(3), 237–244.
[26] Jarrah, A. I., Goodstein, J., & Narasimhan, R. (2000). An efficient airline re-fleeting model for the incremental modification of planned fleet assignments. Transportation Science, 34(4), 349–363. · Zbl 1014.90060
[27] Kabbani, N. M., & Patty, B. W. (1992). Aircraft routing at American airlines. In Proceedings of the thirty-second annual symposium of AGIFORS.
[28] Lübbecke, M. E., & Desrosiers, J. (2002). Selected topics in column generation. Les Cahiers du GERAD G-2002-64, Department of Mathematical Optimization, Braunschweig University of Technology, and GERAD. Submitted to Operations Research. · Zbl 1165.90578
[29] Martins, E. Q. V., & dos Santos, J. L. E. (1999). The labelling algorithm for the multiobjective shortest path problem. (Technical report). Departamento de Matemática, Universidade de Coimbra, Coimbra, Portugal.
[30] Rannou, B. (1986). A new approach to crew pairing optimization. Presentation at 26th AGIFORS Annual Symposium, Bowness-on-Windermere, England.
[31] Régin, J. C. (1994). A filtering algorithm for constraints of difference in CSPs. In Proceedings of AAAI-94 (pp. 362–367).
[32] Rosenberger, J. M., Johnson, E. L., & Nemhauser, G. L. (2004). A robust fleet-assignment model with hub isolation and short cycles. Transportation Science, 38, 3.
[33] Rousseau, L. M., Gendreau, M., & Pesant, G. (2002). Solving small VRPTWs with constraint programming based column generation. In Proceedings of CPAIOR’02. · Zbl 1062.90007
[34] Schaefer, A. J., Johnson, E. L., Kleywegt, A. J., & Nemhauser, G. L. (2001). Airline crew scheduling under uncertainty. tech. rep. (Technical Report). Georgia Institute of Technology, Atlanta, GA, USA.
[35] Talluri, K. T. (1998). The four-day aircraft maintenance problem. Transportation Science, 32, 43–53. · Zbl 1004.90501
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.