IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v32y1998i3p232-245.html
   My bibliography  Save this article

The Operational Airline Crew Scheduling Problem

Author

Listed:
  • Mirela Stojković

    (Groupe d'études et de recherche en analyse des décisions and École Polytechnique, Montréal H3T 1V6, Canada)

  • François Soumis

    (Groupe d'études et de recherche en analyse des décisions and École Polytechnique, Montréal H3T 1V6, Canada)

  • Jacques Desrosiers

    (Groupe d'études et de recherche en analyse des décisions and École des Hautes Études Commerciales, Montréal H3T 1V6, Canada)

Abstract

This paper describes the operational airline crew scheduling problem and represents a first published attempt to solve it. The problem consists of modifying, as necessary, personalized planned monthly assignments of airline crew members during day-to-day operations. It requires covering, at minimal cost, all flight segments from a given time period with available crew while minimizing the disturbances of crew members. To generate modified pairings for selected crew members, both the classical crew pairing problem and the problem of constructing personalized monthly assignments must be treated simultaneously. An optimization approach is proposed for the problem in which the flight schedule is fixed and represents input data. The problem is mathematically formulated as a Set Partitioning type problem, and a column generation method embedded in a branch-and-bound search tree has been implemented to solve it. Good results, from the point of view of both solution times and achieved objectives, have been obtained on generated test problems. Because the solution time is reasonable, several different scenarios of the same problem may be solved. A final decision can then be made by considering all scenarios and choosing the one whose solution is the best in the given situation.

Suggested Citation

  • Mirela Stojković & François Soumis & Jacques Desrosiers, 1998. "The Operational Airline Crew Scheduling Problem," Transportation Science, INFORMS, vol. 32(3), pages 232-245, August.
  • Handle: RePEc:inm:ortrsc:v:32:y:1998:i:3:p:232-245
    DOI: 10.1287/trsc.32.3.232
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.32.3.232
    Download Restriction: no

    File URL: https://libkey.io/10.1287/trsc.32.3.232?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Martin Desrochers & Jacques Desrosiers & Marius Solomon, 1992. "A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 40(2), pages 342-354, April.
    2. Michel Gamache & François Soumis & Daniel Villeneuve & Jacques Desrosiers & Éric Gélinas, 1998. "The Preferential Bidding System at Air Canada," Transportation Science, INFORMS, vol. 32(3), pages 246-255, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    2. Koorush Ziarati & François Soumis & Jacques Desrosiers & Marius M. Solomon, 1999. "A Branch-First, Cut-Second Approach for Locomotive Assignment," Management Science, INFORMS, vol. 45(8), pages 1156-1168, August.
    3. Maenhout, Broos & Vanhoucke, Mario, 2010. "A hybrid scatter search heuristic for personalized crew rostering in the airline industry," European Journal of Operational Research, Elsevier, vol. 206(1), pages 155-167, October.
    4. Filippo Focacci & Andrea Lodi & Michela Milano, 2002. "A Hybrid Exact Algorithm for the TSPTW," INFORMS Journal on Computing, INFORMS, vol. 14(4), pages 403-417, November.
    5. Weijun Xie & Yanfeng Ouyang & Sze Chun Wong, 2016. "Reliable Location-Routing Design Under Probabilistic Facility Disruptions," Transportation Science, INFORMS, vol. 50(3), pages 1128-1138, August.
    6. Park, Jongyoon & Han, Jinil & Lee, Kyungsik, 2024. "Integer optimization models and algorithms for the multi-period non-shareable resource allocation problem," European Journal of Operational Research, Elsevier, vol. 317(1), pages 43-59.
    7. de Lima, Vinícius L. & Alves, Cláudio & Clautiaux, François & Iori, Manuel & Valério de Carvalho, José M., 2022. "Arc flow formulations based on dynamic programming: Theoretical foundations and applications," European Journal of Operational Research, Elsevier, vol. 296(1), pages 3-21.
    8. Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
    9. Hernandez, Florent & Feillet, Dominique & Giroudeau, Rodolphe & Naud, Olivier, 2016. "Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 249(2), pages 551-559.
    10. Mehran Hojati, 2010. "Near-optimal solution to an employee assignment problem with seniority," Annals of Operations Research, Springer, vol. 181(1), pages 539-557, December.
    11. Gang Yu & Michael Argüello & Gao Song & Sandra M. McCowan & Anna White, 2003. "A New Era for Crew Recovery at Continental Airlines," Interfaces, INFORMS, vol. 33(1), pages 5-22, February.
    12. Jeffrey W. Ohlmann & Michael J. Fry & Barrett W. Thomas, 2008. "Route Design for Lean Production Systems," Transportation Science, INFORMS, vol. 42(3), pages 352-370, August.
    13. Baldacci, Roberto & Mingozzi, Aristide & Roberti, Roberto, 2012. "Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints," European Journal of Operational Research, Elsevier, vol. 218(1), pages 1-6.
    14. Timo Gschwind & Stefan Irnich, 2012. "Effective Handling of Dynamic Time Windows and Synchronization with Precedences for Exact Vehicle Routing," Working Papers 1211, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    15. Albert H. Schrotenboer & Evrim Ursavas & Iris F. A. Vis, 2019. "A Branch-and-Price-and-Cut Algorithm for Resource-Constrained Pickup and Delivery Problems," Transportation Science, INFORMS, vol. 53(4), pages 1001-1022, July.
    16. Calvete, Herminia I. & Gale, Carmen & Oliveros, Maria-Jose & Sanchez-Valverde, Belen, 2007. "A goal programming approach to vehicle routing problems with soft time windows," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1720-1733, March.
    17. Capelle, Thomas & Cortés, Cristián E. & Gendreau, Michel & Rey, Pablo A. & Rousseau, Louis-Martin, 2019. "A column generation approach for location-routing problems with pickup and delivery," European Journal of Operational Research, Elsevier, vol. 272(1), pages 121-131.
    18. İbrahim Muter & Ş. İlker Birbil & Güvenç Şahin, 2010. "Combination of Metaheuristic and Exact Algorithms for Solving Set Covering-Type Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 22(4), pages 603-619, November.
    19. Liu, Fuh-Hwa Franklin & Shen, Sheng-Yuan, 1999. "A route-neighborhood-based metaheuristic for vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 118(3), pages 485-504, November.
    20. Lixin Tang & Gongshu Wang & Zhi-Long Chen, 2014. "Integrated Charge Batching and Casting Width Selection at Baosteel," Operations Research, INFORMS, vol. 62(4), pages 772-787, August.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:32:y:1998:i:3:p:232-245. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.