Ir al contenido

Documat

Gaining insight into crew rostering instances through ML-based sequential assignment

  • Philippe Racette [2] ; Frédéric Quesnel [1] ; Andrea Lodi [3] ; François Soumis [2]
    1. [1] University of Quebec at Montreal

      University of Quebec at Montreal

      Canadá

    2. [2] Department of Mathematics and Industrial Engineering and GERAD, Polytechnique Montréal, Montreal, QC, Canada
    3. [3] Canada Excellence Research Chair in Data Science for Real-Time Decision-Making, Polytechnique Montréal, Montreal, QC H3C 3A7, Canada
    Mostrar afiliaciones +
  • Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 32, Nº. Extra 3, 2024 (Ejemplar dedicado a: Mathematical Optimization and Machine Learning), págs. 537-578
  • Idioma: inglés
  • DOI: 10.1007/s11750-024-00678-8
  • Enlaces
  • Resumen

    • Crew scheduling is typically performed in two stages. First, solving the crew pairing problem generates sequences of flights called pairings. Then, the pairings are assigned to crew members to provide each person with a full schedule. A common way to do this is to solve an optimization problem called the crew rostering problem (CRP). However, before solving the CRP, the problem instance must be parameterized appropriately while taking different factors such as preassigned days off, crew training, sick leave, reserve duty, or unusual events into account. In this paper, we present a new method for the parameterization of CRP instances for pilots by scheduling planners. A machine learning-based sequential assignment procedure (seqAsg) whose arc weights are computed using a policy over state–action pairs for pilots is implemented to generate very fast solutions. We establish a relationship between the quality of the solutions generated by seqAsg and that of solutions produced by a state-of-the-art solver. Based on those results, we formulate recommendations for instance parameterization. Given that the seqAsg procedure takes only a few seconds to run, this allows scheduling workers to reparameterize crew rostering instances many times over the course of the planning process as needed.

  • Referencias bibliográficas
    • Bäck T, Foussette C, Krause P (2013) Contemporary evolution strategies, vol 86. Springer, Berlin
    • Bahdanau D, Cho K, Bengio Y (2014) Neural machine translation by jointly learning to align and translate. arXiv preprint. arXiv:1409.0473
    • Bello I, Pham H, Le QV, Norouzi M, Bengio S (2016) Neural combinatorial optimization with reinforcement learning. arXiv preprint. arXiv:1611.09940
    • Beulen M, Scherp L, Santos BF (2020) Dynamic evaluation of airline crew’s flight requests using a neural network. EURO J Transp Logist 9(4):100018....
    • Bonami P, Lodi A, Zarpellon G (2022) A classifier to decide on the linearization of mixed-integer quadratic problems in CPLEX. Oper Res 70(6):3303–3320....
    • Boubaker K, Desaulniers G, Elhallaoui I (2010) Bidline scheduling with equity by heuristic dynamic constraint aggregation. Transp Res Part...
    • Boufaied C, Trabelsi R, Masri H, Krichen S (2016) A construction of rotations-based rosters with a genetic algorithm. In: 2016 IEEE congress...
    • Cappanera P, Gallo G (2004) A multicommodity flow approach to the crew rostering problem. Oper Res 52(4):583–596. https://doi.org/10.1287/opre.1040.0110
    • Caprara A, Toth P, Vigo D, Fischetti M (1998) Modeling and solving the crew rostering problem. Oper Res 46(6):820–830. https://doi.org/10.1287/opre.46.6.820
    • de Armas J, Cadarso L, Juan AA, Faulin J (2017) A multi-start randomized heuristic for real-life crew rostering problems in airlines with...
    • Desaulniers G, Desrosiers J, Dumas Y, Marc S, Rioux B, Solomon MM, Soumis F (1997) Crew pairing at Air France. Eur J Oper Res 97(2):245–259....
    • El Moudani W, Alberto Nunes Cosenza C, de Coligny M, Mora-Camino F (2001) A bi-criterion approach for the airlines crew rostering problem....
    • Elhallaoui I, Metrane A, Desaulniers G, Soumis F (2011) An improved primal simplex algorithm for degenerate linear programs. INFORMS J Comput...
    • Furian N, O’Sullivan M, Walker C, Çela E (2021) A machine learning-based branch and price algorithm for a sampled vehicle routing problem....
    • Gamache M, Soumis F, Marquis G, Desrosiers J (1999) A column generation approach for large-scale aircrew rostering problems. Oper Res 47(2):247–263....
    • Gopalakrishnan B, Johnson EL (2005) Airline crew scheduling: state-of-the-art. Ann Oper Res 140:305–337. https://doi.org/10.1007/s10479-005-3975-3
    • Hansen N, Ostermeier A (2001) Completely derandomized self-adaptation in evolution strategies. Evol Comput 9(2):159–195. https://doi.org/10.1162/106365601750190398
    • Higham CF, Higham DJ (2019) Deep learning: an introduction for applied mathematicians. SIAM Rev 61(4):860–891. https://doi.org/10.1137/18M1165748
    • Juan AA, Faulin J, Ferrer A, Lourenço HR, Barrios B (2013) MIRHA: multi-start biased randomization of heuristics with adaptive local search...
    • Karimi-Mamaghan M, Mohammadi M, Meyer P, Karimi-Mamaghan AM, Talbi E-G (2022) Machine learning at the service of meta-heuristics for solving...
    • Kasirzadeh A, Saddoune M, Soumis F (2017) Airline crew scheduling: models, algorithms, and data sets. EURO J Transp Logist 6(2):111–137. https://doi.org/10.1007/s13676-015-0080-x
    • Kohl N, Karisch SE (2004) Airline crew rostering: problem types, modeling, and optimization. Ann Oper Res 127(1–4):223–257. https://doi.org/10.1023/B:ANOR.0000019091.54417.ca
    • Kool W, van Hoof H, Welling M (2019) Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475
    • Kotary J, Fioretto F, Van Hentenryck P, Wilder B (2021) End-to-end constrained optimization learning: a survey. arXiv preprint arXiv:2103.16378
    • Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper Res 53(6):1007–1023. https://doi.org/10.1287/opre.1050.0234
    • Luˇcic P, Teodorovic D (1999) Simulated annealing for the multi-objective aircrew rostering problem. Transp Res Part A Policy Pract 33(1):19–45....
    • Luˇci´c P, Teodorovi´c D (2007) Metaheuristics approach to the aircrew rostering problem. Ann Oper Res 155:311–338. https://doi.org/10.1007/s10479-007-0216-y
    • Maenhout B, Vanhoucke M (2010) A hybrid scatter search heuristic for personalized crew rostering in the airline industry. Eur J Oper Res 206(1):155–167....
    • Morabit M, Desaulniers G, Lodi A (2021) Machine-learning-based column selection for column generation. Transp Sci 55(4):815–831. https://doi.org/10.1287/trsc.2021.1045
    • Morabit M, Desaulniers G, Lodi A (2023) Machine-learning-based arc selection for constrained shortest path problems in column generation....
    • Nazari M, Oroojlooy A, Snyder LV, Takáˇc M (2018) Deep reinforcement learning for solving the vehicle routing problem. Adv Neural Inf Process...
    • Quesnel F, Desaulniers G, Soumis F (2020a) A branch-and-price heuristic for the crew pairing problem with language constraints. Eur J Oper...
    • Quesnel F, Desaulniers G, Soumis F (2020b) Improving air crew rostering by considering crew preferences in the crew pairing problem. Transp...
    • Quesnel F, Wu A, Desaulniers G, Soumis F (2022) Deep-learning-based partial pricing in a branch-and-price algorithm for personalized crew...
    • Saddoune M, Desaulniers G, Elhallaoui I, Soumis F (2012) Integrated airline crew pairing and crew assignment by dynamic constraint aggregation....
    • Salismans T, Ho J, Chen X, Sidor S, Sutskever I (2017) Evolution strategies as a scalable alternative to reinforcement learning. arXiv preprint,...
    • Schaefer AJ, Johnson EL, Kleywegt AJ, Nemhauser GL (2005) Airline crew scheduling under uncertainty. Transp Sci 39(3):340–348. https://doi.org/10.1287/trsc.1040.0091
    • Silver D, Lever G, Heess N, Degris T, Wierstra D, Riedmiller M (2014) Deterministic policy gradient algorithms. In: International conference...
    • Tahir A, Quesnel F, Desaulniers G, Elhallaoui I, Yaakoubi Y (2021) An improved integral column generation algorithm using machine learning...
    • Vinyals O, Fortunato M, Jaitly N (2015) Pointer networks. Adv Neural Inf Process Syst 28
    • Yaakoubi Y, Soumis F, Lacoste-Julien S (2020a) Flight-connection prediction for airline crew scheduling to construct initial clusters for...
    • Yaakoubi Y, Soumis F, Lacoste-Julien S (2020b) Machine learning in airline crew pairing to construct initial clusters for dynamic constraint...
    • Zeighami V, Soumis F (2019) Combining Benders’ decomposition and column generation for integrated crew pairing and personalized crew assignment...
    • Zeighami V, Saddoune M, Soumis F (2020) Alternating lagrangian decomposition for integrated airline crew scheduling problem. Eur J Oper Res...
    • Zhou S-Z, Zhan Z-H, Chen Z-G, Kwong S, Zhang J (2020) A multi-objective ant colony system algorithm for airline crew rostering problem with...
    • Zhou T, Chen X, Wu X, Yang C (2022) A hybrid multi-objective genetic-particle swarm optimization algorithm for airline crew rostering problem...
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno