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

Shift Planning Under Delay Uncertainty at Air France: A Vehicle-Scheduling Problem with Outsourcing

Author

Listed:
  • Julie Poullet

    (Applied Mathematics Department, École Polytechnique, 91128 Palaiseau, France;)

  • Axel Parmentier

    (CERMICS, École des Ponts Paristech, 77420 Champs-sur-Marne, France)

Abstract

Airlines must operate many jobs in airports, such as passenger check-in or runway tasks. In airlines’ hubs, airlines generally choose to perform these jobs with their own agents. Shift planning aims at building the sequences of jobs operated by the airline agents and has been widely studied given its impact on operating costs. The impact of delayed flights is generally not taken into account despite the propagation of flight delays along these sequences: If a flight is late, then the agents doing the corresponding jobs are delayed, and may arrive late to their next jobs and delay the corresponding flights. Since delay costs are much higher than the costs of outsourcing jobs, if the agent who is supposed to operate a job is still working elsewhere when the job begins, then airlines tend to outsource the job to their own dedicated team or to a third party. We introduce a stochastic version of the shift-planning problem that takes into account outsourcing costs due to delay. It can be seen as a natural stochastic generalization of the vehicle-scheduling problem in which delayed jobs are outsourced. We propose a column-generation approach to solve it, whose key element is the pricing subproblem algorithm, modeled as a stochastic resource-constrained shortest-path problem. Numerical results on Air France industrial instances show the benefits of using our stochastic version of the shift-planning problem and the efficiency of the solution method. Moving to the stochastic version enables Air France to reduce total operating costs by 3.5%–4.8% on instances with more than 200 jobs, and our algorithm can solve to near optimality instances with up to 400 jobs.

Suggested Citation

  • Julie Poullet & Axel Parmentier, 2020. "Shift Planning Under Delay Uncertainty at Air France: A Vehicle-Scheduling Problem with Outsourcing," Transportation Science, INFORMS, vol. 54(4), pages 956-972, July.
  • Handle: RePEc:inm:ortrsc:v:54:y:2020:i:4:p:956-972
    DOI: 10.1287/trsc.2019.0960
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/trsc.2019.0960
    Download Restriction: no

    File URL: https://libkey.io/10.1287/trsc.2019.0960?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. Gendreau, Michel & Laporte, Gilbert & Seguin, Rene, 1996. "Stochastic vehicle routing," European Journal of Operational Research, Elsevier, vol. 88(1), pages 3-12, January.
    2. Gilbert Laporte & François Louveaux & Hélène Mercure, 1992. "The Vehicle Routing Problem with Stochastic Travel Times," Transportation Science, INFORMS, vol. 26(3), pages 161-170, August.
    3. Michael J. Brusco & Larry W. Jacobs & Robert J. Bongiorno & Duane V. Lyons & Baoxing Tang, 1995. "Improving Personnel Scheduling at Airline Stations," Operations Research, INFORMS, vol. 43(5), pages 741-751, October.
    4. Van den Bergh, Jorne & Beliën, Jeroen & De Bruecker, Philippe & Demeulemeester, Erik & De Boeck, Liesje, 2013. "Personnel scheduling: A literature review," European Journal of Operational Research, Elsevier, vol. 226(3), pages 367-385.
    5. Li, Xiangyong & Tian, Peng & Leung, Stephen C.H., 2010. "Vehicle routing problems with time windows and stochastic travel and service times: Models and algorithm," International Journal of Production Economics, Elsevier, vol. 125(1), pages 137-145, May.
    6. Rong, Aiying & Grunow, Martin, 2009. "Shift designs for freight handling personnel at air cargo terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 45(5), pages 725-739, September.
    7. Santos, Georgina & Robin, Maël, 2010. "Determinants of delays at European airports," Transportation Research Part B: Methodological, Elsevier, vol. 44(3), pages 392-403, March.
    8. Thomas J. Holloran & Judson E. Byrn, 1986. "United Airlines Station Manpower Planning System," Interfaces, INFORMS, vol. 16(1), pages 39-50, February.
    9. M J Brusco & T R Johns, 2011. "An integrated approach to shift-starting time selection and tour-schedule construction," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(7), pages 1357-1364, July.
    10. Antoon W.J. Kolen & Jan Karel Lenstra & Christos H. Papadimitriou & Frits C.R. Spieksma, 2007. "Interval scheduling: A survey," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(5), pages 530-543, August.
    11. Ernst, A. T. & Jiang, H. & Krishnamoorthy, M. & Sier, D., 2004. "Staff scheduling and rostering: A review of applications, methods and models," European Journal of Operational Research, Elsevier, vol. 153(1), pages 3-27, February.
    12. D. Dowling & M. Krishnamoorthy & H. Mackenzie & D. Sier, 1997. "Staff rostering at a large international airport," Annals of Operations Research, Springer, vol. 72(0), pages 125-147, January.
    13. Stefan Irnich & Guy Desaulniers, 2005. "Shortest Path Problems with Resource Constraints," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 33-65, Springer.
    14. Sol Schindler & Ted Semmel, 1993. "Station Staffing at Pan American World Airways," Interfaces, INFORMS, vol. 23(3), pages 91-98, June.
    15. Cynthia Barnhart & Peter Belobaba & Amedeo R. Odoni, 2003. "Applications of Operations Research in the Air Transport Industry," Transportation Science, INFORMS, vol. 37(4), pages 368-391, November.
    16. Marius M. Solomon & Jacques Desrosiers, 1988. "Survey Paper---Time Window Constrained Routing and Scheduling Problems," Transportation Science, INFORMS, vol. 22(1), pages 1-13, February.
    17. Shan Lan & John-Paul Clarke & Cynthia Barnhart, 2006. "Planning for Robust Airline Operations: Optimizing Aircraft Routings and Flight Departure Times to Minimize Passenger Disruptions," Transportation Science, INFORMS, vol. 40(1), pages 15-28, February.
    18. Stolletz, Raik, 2010. "Operational workforce planning for check-in counters at airports," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(3), pages 414-425, May.
    19. Leslie C. Edie, 1954. "Traffic Delays at Toll Booths," Operations Research, INFORMS, vol. 2(2), pages 107-138, May.
    20. Joyce W. Yen & John R. Birge, 2006. "A Stochastic Programming Approach to the Airline Crew Scheduling Problem," Transportation Science, INFORMS, vol. 40(1), pages 3-14, February.
    21. Eric Prescott-Gagnon & Guy Desaulniers & Michael Drexl & Louis-Martin Rousseau, 2010. "European Driver Rules in Vehicle Routing with Time Windows," Transportation Science, INFORMS, vol. 44(4), pages 455-473, November.
    22. Yan, Shangyao & Chen, Chia-Hung & Chen, Chung-Kai, 2006. "Long-term manpower supply planning for air cargo terminals," Journal of Air Transport Management, Elsevier, vol. 12(4), pages 175-181.
    23. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Wang, Wenshu & Xie, Kexin & Guo, Siqi & Li, Weixing & Xiao, Fan & Liang, Zhe, 2023. "A shift-based model to solve the integrated staff rostering and task assignment problem with real-world requirements," European Journal of Operational Research, Elsevier, vol. 310(1), pages 360-378.
    2. Wu, Zhiying & Xu, Guoning & Chen, Qingxin & Mao, Ning, 2023. "Two stochastic optimization methods for shift design with uncertain demand," Omega, Elsevier, vol. 115(C).

    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. Van den Bergh, Jorne & Beliën, Jeroen & De Bruecker, Philippe & Demeulemeester, Erik & De Boeck, Liesje, 2013. "Personnel scheduling: A literature review," European Journal of Operational Research, Elsevier, vol. 226(3), pages 367-385.
    2. Arpan Rijal & Marco Bijvank & Asvin Goel & René de Koster, 2021. "Workforce Scheduling with Order-Picking Assignments in Distribution Facilities," Transportation Science, INFORMS, vol. 55(3), pages 725-746, May.
    3. Ferdinand Kiermaier & Markus Frey & Jonathan F. Bard, 2020. "The flexible break assignment problem for large tour scheduling problems with an application to airport ground handlers," Journal of Scheduling, Springer, vol. 23(2), pages 177-209, April.
    4. Ivan Kovynyov & Ralf Mikut, 2019. "Digital technologies in airport ground operations," Netnomics, Springer, vol. 20(1), pages 1-30, April.
    5. Errico, F. & Desaulniers, G. & Gendreau, M. & Rei, W. & Rousseau, L.-M., 2016. "A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times," European Journal of Operational Research, Elsevier, vol. 249(1), pages 55-66.
    6. M J Brusco & T R Johns, 2011. "An integrated approach to shift-starting time selection and tour-schedule construction," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(7), pages 1357-1364, July.
    7. Wu, Cheng-Lung & Lim, Shao Xuan, 2021. "Effects of enterprise bargaining and agreement clauses on the operating cost of airline ground crew scheduling," Journal of Air Transport Management, Elsevier, vol. 91(C).
    8. Emilio Zamorano & Annika Becker & Raik Stolletz, 2018. "Task assignment with start time-dependent processing times for personnel at check-in counters," Journal of Scheduling, Springer, vol. 21(1), pages 93-109, February.
    9. Oyku Ahipasaoglu & Nesim Erkip & Oya Ekin Karasan, 2019. "The venue management problem: setting staffing levels, shifts and shift schedules at concession stands," Journal of Scheduling, Springer, vol. 22(1), pages 69-83, February.
    10. Lishun Zeng & Mingyu Zhao & Yangfan Liu, 2019. "Airport ground workforce planning with hierarchical skills: a new formulation and branch-and-price approach," Annals of Operations Research, Springer, vol. 275(1), pages 245-258, April.
    11. Ehmke, Jan Fabian & Campbell, Ann Melissa & Urban, Timothy L., 2015. "Ensuring service levels in routing problems with time windows and stochastic travel times," European Journal of Operational Research, Elsevier, vol. 240(2), pages 539-550.
    12. Lin, Shih-Wei & Ying, Kuo-Ching, 2014. "Minimizing shifts for personnel task scheduling problems: A three-phase algorithm," European Journal of Operational Research, Elsevier, vol. 237(1), pages 323-334.
    13. Jaime Miranda & Pablo A. Rey & Antoine Sauré & Richard Weber, 2018. "Metro Uses a Simulation-Optimization Approach to Improve Fare-Collection Shift Scheduling," Interfaces, INFORMS, vol. 48(6), pages 529-542, November.
    14. Vidal, Thibaut & Laporte, Gilbert & Matl, Piotr, 2020. "A concise guide to existing and emerging vehicle routing problem variants," European Journal of Operational Research, Elsevier, vol. 286(2), pages 401-416.
    15. Jiang, J. & Ng, K.M. & Teo, K.M., 2016. "Satisficing measure approach for vehicle routing problem with time windows under uncertaintyAuthor-Name: Nguyen, V.A," European Journal of Operational Research, Elsevier, vol. 248(2), pages 404-414.
    16. Zamorano, Emilio & Stolletz, Raik, 2017. "Branch-and-price approaches for the Multiperiod Technician Routing and Scheduling Problem," European Journal of Operational Research, Elsevier, vol. 257(1), pages 55-68.
    17. Borzou Rostami & Guy Desaulniers & Fausto Errico & Andrea Lodi, 2021. "Branch-Price-and-Cut Algorithms for the Vehicle Routing Problem with Stochastic and Correlated Travel Times," Operations Research, INFORMS, vol. 69(2), pages 436-455, March.
    18. Andrew Lim & Zhenzhen Zhang & Hu Qin, 2017. "Pickup and Delivery Service with Manpower Planning in Hong Kong Public Hospitals," Transportation Science, INFORMS, vol. 51(2), pages 688-705, May.
    19. F. Errico & G. Desaulniers & M. Gendreau & W. Rei & L.-M. Rousseau, 2018. "The vehicle routing problem with hard time windows and stochastic service times," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(3), pages 223-251, September.
    20. Mathias A. Klapp & Alan L. Erera & Alejandro Toriello, 2018. "The One-Dimensional Dynamic Dispatch Waves Problem," Transportation Science, INFORMS, vol. 52(2), pages 402-415, March.

    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:54:y:2020:i:4:p:956-972. 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.