{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T19:43:24Z","timestamp":1781552604672,"version":"3.54.5"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,8,18]],"date-time":"2020-08-18T00:00:00Z","timestamp":1597708800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,8,18]],"date-time":"2020-08-18T00:00:00Z","timestamp":1597708800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Natural Sciences and Engineering Research Council of Canada and Kronos Inc","award":["RDC477127-14"],"award-info":[{"award-number":["RDC477127-14"]}]},{"name":"Natural Sciences and Research Council of Canada and Kronos Inc.","award":["RDC477127-14"],"award-info":[{"award-number":["RDC477127-14"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN Oper. Res. Forum"],"published-print":{"date-parts":[[2020,9]]},"DOI":"10.1007\/s43069-020-00016-1","type":"journal-article","created":{"date-parts":[[2020,8,17]],"date-time":"2020-08-17T22:02:54Z","timestamp":1597701774000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Dynamic Constraint Aggregation for Solving Very Large-scale Airline Crew Pairing Problems"],"prefix":"10.1007","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4469-9813","authenticated-orcid":false,"given":"Guy","family":"Desaulniers","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fran\u00e7ois","family":"Lessard","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammed","family":"Saddoune","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fran\u00e7ois","family":"Soumis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,8,18]]},"reference":[{"issue":"4","key":"16_CR1","doi-asserted-by":"publisher","first-page":"1284","DOI":"10.1016\/j.cor.2008.02.001","volume":"36","author":"S AhmadBeygi","year":"2009","unstructured":"AhmadBeygi S, Cohn A, Weir M (2009) An integer programming approach to generating airline crew pairings. Comput Oper Res 36(4):1284\u20131298","journal-title":"Comput Oper Res"},{"issue":"3","key":"16_CR2","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1287\/trsc.32.3.221","volume":"32","author":"C Barnhart","year":"1998","unstructured":"Barnhart C, Shenoi R (1998a) An approximate model and solution approach for the long-haul crew pairing problem. Transp Sci 32(3):221\u2013231","journal-title":"Transp Sci"},{"key":"16_CR3","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1287\/opre.46.3.316","volume":"46","author":"C Barnhart","year":"1998","unstructured":"Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998b) Branch-and-price: column generation for solving huge integer programs. Oper Res 46:316\u2013329","journal-title":"Oper Res"},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1016\/j.ejor.2017.04.049","volume":"262","author":"H Bouarab","year":"2017","unstructured":"Bouarab H, El Hallaoui I, Metrane A, Soumis F (2017) Dynamic constraint and variable aggregation in column generation. European J Oper Res 262:835\u2013850","journal-title":"European J Oper Res"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/S0377-2217(96)00196-8","volume":"97","author":"HD Chu","year":"1997","unstructured":"Chu HD, Gelman E, Johnson EL (1997) Solving large scale crew scheduling problems. European J Oper Res 97:260\u2013268","journal-title":"European J Oper Res"},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/S0377-2217(96)00195-6","volume":"97","author":"G Desaulniers","year":"1997","unstructured":"Desaulniers G, Desrosiers J, Dumas Y, Marc S, Rioux B, Solomon MM, Soumis F. (1997) Crew pairing at Air France. European J Oper Res 97:245\u2013259","journal-title":"European J Oper Res"},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"Desaulniers G, Desrosiers J, Ioachim I, Solomon MM, Soumis F, Villeneuve D (1998) A unified framework for deterministic time constrained vehicle routing and crew scheduling problems. In: Crainic TG, Laporte G (eds) Fleet Management and Logistics, Norwell, pp 57\u201393","DOI":"10.1007\/978-1-4615-5755-5_3"},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"Desrosiers J, Dumas Y, Solomon MM, Soumis F (1995a) Time constrained routing and scheduling. In: Ball M et al (eds) Network Routing, Handbooks in Operations Research and Management Science, vol 8. Elsevier, Amsterdam, pp 35\u2013139","DOI":"10.1016\/S0927-0507(05)80106-9"},{"key":"16_CR9","volume-title":"Column generation","year":"2005","unstructured":"Desaulniers G, Desrosiers J, Solomon MM (eds) (2005a) Column generation. Springer, New York"},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"Desrosiers J, L\u00fcbbecke M (2005b) A primer in column generation. In: Desaulniers G, Desrosiers J, Solomon MM (eds) Column Generation, chap. 1. Springer, NY, pp 1\u201332","DOI":"10.1007\/0-387-25486-2_1"},{"key":"16_CR11","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.engappai.2018.05.008","volume":"74","author":"M Deveci","year":"2018","unstructured":"Deveci M, Demirel N\u00c7 (2018) A survey of the literature on airline crew scheduling. Eng Appl Artif Intel 74:54\u201369","journal-title":"Eng Appl Artif Intel"},{"issue":"1","key":"16_CR12","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s12469-011-0038-9","volume":"3","author":"V D\u00fcck","year":"2011","unstructured":"D\u00fcck V, Wesselmann F, Suhl L (2011) Implementing a branch and price and cut method for the airline crew pairing optimization problem. Public Transp 3(1):43\u201364","journal-title":"Public Transp"},{"issue":"5","key":"16_CR13","doi-asserted-by":"publisher","first-page":"1713","DOI":"10.1016\/j.cor.2006.10.007","volume":"35","author":"I Elhallaoui","year":"2008","unstructured":"Elhallaoui I, Desaulniers G, Metrane A, Soumis F (2008) Bi-dynamic constraint aggregation and subproblem reduction. Comput Oper Res 35(5):1713\u20131724","journal-title":"Comput Oper Res"},{"issue":"4","key":"16_CR14","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1287\/ijoc.1100.0425","volume":"23","author":"I Elhallaoui","year":"2011","unstructured":"Elhallaoui I, Metrane A, Desaulniers G, Soumis F (2011) An improved primal simplex algorithm for degenerate linear programs. Informs J Comput 23(4):569\u2013577","journal-title":"Informs J Comput"},{"issue":"2","key":"16_CR15","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/s10107-008-0254-5","volume":"123","author":"I Elhallaoui","year":"2010","unstructured":"Elhallaoui I, Metrane A, Soumis F, Desaulniers G (2010) Multiphase dynamic constraint aggregation for set partitioning type problems. Math Program 123(2):345\u2013370","journal-title":"Math Program"},{"key":"16_CR16","doi-asserted-by":"publisher","first-page":"632","DOI":"10.1287\/opre.1050.0222","volume":"53","author":"I Elhallaoui","year":"2005","unstructured":"Elhallaoui I, Villeneuve D, Soumis F, Desaulniers G (2005) Dynamic aggregation of set partitioning constraints in column generation. Oper Res 53:632\u2013645","journal-title":"Oper Res"},{"key":"16_CR17","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s10479-005-3975-3","volume":"140","author":"B Gopalakrishnan","year":"2005","unstructured":"Gopalakrishnan B, Johnson EL (2005) Airline crew scheduling: state-of-the-art. Ann Oper Res 140:305\u2013337","journal-title":"Ann Oper Res"},{"key":"16_CR18","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1287\/mnsc.39.6.657","volume":"39","author":"KL Hoffman","year":"1993","unstructured":"Hoffman K L, Padberg M (1993) Solving airline crew scheduling problems by branch-and-cut. Manag Sci 39:657\u2013682","journal-title":"Manag Sci"},{"key":"16_CR19","doi-asserted-by":"crossref","unstructured":"Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. In: Desaulniers G, Desrosiers J, Solomon M (eds) Column generation. Springer, New York, pp 33\u201365","DOI":"10.1007\/0-387-25486-2_2"},{"key":"16_CR20","first-page":"297","volume":"43","author":"M Jepsen","year":"2008","unstructured":"Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2008) A non-robust branch-and-cut-and-price algorithm for the vehicle routing problem with time windows. Oper Res 43:297\u2013325","journal-title":"Oper Res"},{"issue":"2","key":"16_CR21","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s13676-015-0080-x","volume":"6","author":"A Kasirzadeh","year":"2017","unstructured":"Kasirzadeh A, Saddoune M, Soumis F (2017) Airline crew scheduling: models, algorithms, and data sets. EURO J Transp Logist 6(2):111\u2013137","journal-title":"EURO J Transp Logist"},{"key":"16_CR22","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1023\/A:1011223523191","volume":"20","author":"D Klabjan","year":"2001","unstructured":"Klabjan D, Johnson E, Nemhauser G, Gelman E, Ramaswamy S (2001) Solving large airline crew scheduling problems: random pairing generation and strong branching. Comput Optim Appl 20:73\u201391","journal-title":"Comput Optim Appl"},{"issue":"1","key":"16_CR23","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0377-2217(88)90377-3","volume":"35","author":"S Lavoie","year":"1988","unstructured":"Lavoie S, Minoux M, Odier E (1988) A new approach for crew pairing problems by column generation with an application to air transportation. European J Oper Res 35(1):45\u201358","journal-title":"European J Oper Res"},{"issue":"6","key":"16_CR24","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1287\/opre.1050.0234","volume":"53","author":"ME L\u00fcbbecke","year":"2005","unstructured":"L\u00fcbbecke M E, Desrosiers J (2005) Selected topics in column generation. Oper Res 53(6):1007\u20131023","journal-title":"Oper Res"},{"key":"16_CR25","doi-asserted-by":"publisher","first-page":"1451","DOI":"10.1016\/j.cor.2003.11.013","volume":"32","author":"A Mercier","year":"2005","unstructured":"Mercier A, Cordeau JF, Soumis F (2005) A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem. Comput Oper Res 32:1451\u20131476","journal-title":"Comput Oper Res"},{"issue":"3","key":"16_CR26","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1016\/j.cor.2010.11.005","volume":"40","author":"I Muter","year":"2013","unstructured":"Muter I, Ilker Birbil S, Bulbul K, Sahin G, Yenigun H, Tas D, Tuzun D (2013) Solving a robust airline crew pairing problem with column generation. Comput Oper Res 40(3):815\u2013830","journal-title":"Comput Oper Res"},{"key":"16_CR27","doi-asserted-by":"crossref","unstructured":"Parmentier A, Meunier F (2020) Aircraft routing and crew pairing: updated algorithms at Air France. Omega, forthcoming","DOI":"10.1016\/j.omega.2019.05.009"},{"key":"16_CR28","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.cor.2016.11.020","volume":"80","author":"F Quesnel","year":"2017","unstructured":"Quesnel F, Desaulniers G, Soumis Fr (2017) A new heuristic branching scheme for the crew pairing problem with base constraints. Comput Oper Res 80:159\u2013172","journal-title":"Comput Oper Res"},{"issue":"3","key":"16_CR29","doi-asserted-by":"publisher","first-page":"1040","DOI":"10.1016\/j.ejor.2019.11.043","volume":"283","author":"F Quesnel","year":"2020","unstructured":"Quesnel F, Desaulniers G, Soumis F (2020a) A branch-and-price heuristic for the crew pairing problem with language constraints. European J Oper Res 283(3):1040\u20131054","journal-title":"European J Oper Res"},{"issue":"1","key":"16_CR30","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1287\/trsc.2019.0913","volume":"54","author":"F Quesnel","year":"2020","unstructured":"Quesnel F, Desaulniers G, Soumis F (2020b) Improving air crew rostering by considering crew preferences in the crew pairing problem. Transp Sci 54(1):97\u2013114","journal-title":"Transp Sci"},{"issue":"1","key":"16_CR31","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1287\/trsc.1110.0379","volume":"46","author":"M Saddoune","year":"2012","unstructured":"Saddoune M, Desaulniers G, Elhallaoui I, Soumis F (2012) Integrated airline crew pairing and crew assignment by dynamic constraint aggregation. Transp Sci 46(1):39\u201355","journal-title":"Transp Sci"},{"issue":"3","key":"16_CR32","doi-asserted-by":"publisher","first-page":"805","DOI":"10.1016\/j.cor.2010.11.003","volume":"40","author":"M Saddoune","year":"2013","unstructured":"Saddoune M, Desaulniers G, Soumis F (2013) Aircrew pairings with possible repetitions of the same flight number. Comput Oper Res 40(3):805\u2013814","journal-title":"Comput Oper Res"},{"issue":"3","key":"16_CR33","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1007\/s13676-019-00145-6","volume":"8","author":"A Tahir","year":"2019","unstructured":"Tahir A, Desaulniers G, Elhallaoui I (2019a) Integral column generation. EURO J Transp Logist 8(3):713\u2013744","journal-title":"EURO J Transp Logist"},{"key":"16_CR34","unstructured":"Tahir A, Desaulniers G, Elhallaoui I (2019b) Integral column generation for set partitioning problems with side constraints, Technical report, Les Cahiers du GERAD G-2019-85, HEC Montr\u00e9al, pp 25"},{"key":"16_CR35","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1287\/opre.45.2.188","volume":"45","author":"PH Vance","year":"1997","unstructured":"Vance PH, Barnhart C, Johnson EL, Nemhauser GL (1997) Airline crew scheduling: a new formulation and decomposition algorithm. Oper Res 45:188\u2013200","journal-title":"Oper Res"},{"key":"16_CR36","unstructured":"Yaakoubi Y (2019) Combiner intelligence artificielle et programmation math\u00e9matique pour la planification des horaires des \u00e9quipages en transport a\u00e9rien. PhD dissertation Polytechnique, Montr\u00e9al"},{"issue":"2","key":"16_CR37","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1287\/opre.2013.1247","volume":"62","author":"A Zaghrouti","year":"2014","unstructured":"Zaghrouti A, Soumis F, El Hallaoui I (2014) Integral simplex using decomposition for the set partitioning problem. Oper Res 62(2):435\u2013449","journal-title":"Oper Res"},{"issue":"C","key":"16_CR38","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.eswa.2016.01.045","volume":"55","author":"B Zeren","year":"2016","unstructured":"Zeren B, \u00d6zkol I (2016) A Novel Column Generation Strategy for Large Scale Airline Crew Pairing Problems. Expert Syst Appl 55(C):133\u2013144","journal-title":"Expert Syst Appl"}],"container-title":["SN Operations Research Forum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-020-00016-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s43069-020-00016-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-020-00016-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T13:08:48Z","timestamp":1667826528000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s43069-020-00016-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,18]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["16"],"URL":"https:\/\/doi.org\/10.1007\/s43069-020-00016-1","relation":{"is-basis-for":[{"id-type":"doi","id":"10.52843\/cassyni.jj5t91","asserted-by":"object"}]},"ISSN":["2662-2556"],"issn-type":[{"value":"2662-2556","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,18]]},"assertion":[{"value":"13 March 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 June 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 August 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with Ethical Standards"}},{"value":"G. Desaulniers and F. Soumis have received a research grant from the company Kronos who owned Ad Opt when this research project was conducted. Ad Opt is now part of the company IBS Software.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Conflict of Interest"}}],"article-number":"19"}}