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

A Quasi-Robust Optimization Approach for Crew Rescheduling

Author

Listed:
  • Lucas P. Veelenturf

    (Rotterdam School of Management and ECOPT, Erasmus University Rotterdam, 3000 DR Rotterdam, Netherlands)

  • Daniel Potthoff

    (Ab Ovo Germany, Düsseldorf, 40549 Germany)

  • Dennis Huisman

    (Econometric Institute and ECOPT, Erasmus University Rotterdam, 3000 DR Rotterdam, Netherlands; and Process Quality and Innovation, Netherlands Railways, 3500 HA Utrecht, Netherlands)

  • Leo G. Kroon

    (Rotterdam School of Management and ECOPT, Erasmus University Rotterdam, 3000 DR Rotterdam, Netherlands; and Process Quality and Innovation, Netherlands Railways, 3500 HA Utrecht, Netherlands)

  • Gábor Maróti

    (VU University Amsterdam, 1081 HV Amsterdam, Netherlands; and Process Quality and Innovation, Netherlands Railways, 3500 HA Utrecht, Netherlands)

  • Albert P. M. Wagelmans

    (Econometric Institute and ECOPT, Erasmus University Rotterdam, 3000 DR Rotterdam, Netherlands)

Abstract

This paper studies the real-time crew rescheduling problem in case of large-scale disruptions. One of the greatest challenges of real-time disruption management is the unknown duration of the disruption. In this paper we present a novel approach for crew rescheduling where we deal with this uncertainty by considering several scenarios for the duration of the disruption.The rescheduling problem is similar to a two-stage optimization problem. In the first stage, at the start of the disruption, we reschedule the plan based on the optimistic scenario (i.e., assuming the shortest possible duration of the disruption), while taking into account the possibility that another scenario will be realized. We require a prescribed number of the rescheduled crew duties (a sequential list of tasks which have to be performed by a single crew member) to be recoverable . The true duration of the disruption is revealed in the second stage. By the recoverability of the duties, we expect that the first stage solution can easily be turned into a schedule that is feasible for the realized scenario.We demonstrate the effectiveness of our approach by an application in real-time railway crew rescheduling. The ideas of this paper generalize to certain vehicle rescheduling and manufacturing problems where timetabled tasks which have a fixed start and end location are to be carried out by a given number of servers.We test our approach on a number of instances of Netherlands Railways (NS), the main operator of passenger trains in the Netherlands. The numerical experiments show that the approach indeed finds schedules which are easier to adjust if it turns out that another scenario than the optimistic one is realized for the duration of the disruption.

Suggested Citation

  • Lucas P. Veelenturf & Daniel Potthoff & Dennis Huisman & Leo G. Kroon & Gábor Maróti & Albert P. M. Wagelmans, 2016. "A Quasi-Robust Optimization Approach for Crew Rescheduling," Transportation Science, INFORMS, vol. 50(1), pages 204-215, February.
    • Handle: RePEc:inm:ortrsc:v:50:y:2016:i:1:p:204-215
    DOI: 10.1287/trsc.2014.0545
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.2014.0545
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2014.0545?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. Valentina Cacchiani & Alberto Caprara & Laura Galli & Leo Kroon & Gábor Maróti & Paolo Toth, 2012. "Railway Rolling Stock Planning: Robustness Against Large Disruptions," Transportation Science, INFORMS, vol. 46(2), pages 217-232, May.
    2. Daniel Potthoff & Dennis Huisman & Guy Desaulniers, 2010. "Column Generation with Dynamic Duty Selection for Railway Crew Rescheduling," Transportation Science, INFORMS, vol. 44(4), pages 493-505, November.
    3. Cacchiani, Valentina & Toth, Paolo, 2012. "Nominal and robust train timetabling problems," European Journal of Operational Research, Elsevier, vol. 219(3), pages 727-737.
    4. Erwin Abbink & Matteo Fischetti & Leo Kroon & Gerrit Timmer & Michiel Vromans, 2005. "Reinventing Crew Scheduling at Netherlands Railways," Interfaces, INFORMS, vol. 35(5), pages 393-401, October.
    5. Huisman, D. & Jans, R.F. & Peeters, M. & Wagelmans, A.P.M., 2003. "Combining Column Generation and Lagrangian Relaxation," ERIM Report Series Research in Management ERS-2003-092-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    6. Alberto Caprara & Matteo Fischetti & Paolo Toth, 1999. "A Heuristic Method for the Set Covering Problem," Operations Research, INFORMS, vol. 47(5), pages 730-743, October.
    7. Leo Kroon & Dennis Huisman & Erwin Abbink & Pieter-Jan Fioole & Matteo Fischetti & Gábor Maróti & Alexander Schrijver & Adri Steenbeek & Roelof Ybema, 2009. "The New Dutch Timetable: The OR Revolution," Interfaces, INFORMS, vol. 39(1), pages 6-17, February.
    8. Jespersen-Groth, J. & Potthoff, D. & Clausen, J. & Huisman, D. & Kroon, L.G. & Maróti, G. & Nielsen, M.N., 2007. "Disruption management in passenger railway transportation," Econometric Institute Research Papers EI 2007-05, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    9. Kroon, L.G. & Huisman, D. & Abbink, E.J.W. & Fioole, P-J. & Fischetti, M. & Maróti, G. & Schrijver, A. & Steenbeek, A. & Ybema, R., 2008. "The new Dutch timetable: The OR revolution," Econometric Institute Research Papers EI 2008-19, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    10. Potthoff, D. & Huisman, D. & Desaulniers, G., 2008. "Column generation with dynamic duty selection for railway crew rescheduling," Econometric Institute Research Papers EI 2008-28, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    11. Dennis Huisman & Raf Jans & Marc Peeters & Albert P.M. Wagelmans, 2005. "Combining Column Generation and Lagrangian Relaxation," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 247-270, Springer.
    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. Thijs Verhaegh & Dennis Huisman & Pieter-Jan Fioole & Juan C. Vera, 2017. "A heuristic for real-time crew rescheduling during small disruptions," Public Transport, Springer, vol. 9(1), pages 325-342, July.
    2. Bastian Amberg & Boris Amberg & Natalia Kliewer, 2019. "Robust Efficiency in Urban Public Transportation: Minimizing Delay Propagation in Cost-Efficient Bus and Driver Schedules," Service Science, INFORMS, vol. 53(1), pages 89-112, February.
    3. Heil, Julia & Hoffmann, Kirsten & Buscher, Udo, 2020. "Railway crew scheduling: Models, methods and applications," European Journal of Operational Research, Elsevier, vol. 283(2), pages 405-425.
    4. Evelien van der Hurk & Leo Kroon & Gábor Maróti, 2018. "Passenger Advice and Rolling Stock Rescheduling Under Uncertainty for Disruption Management," Service Science, INFORMS, vol. 52(6), pages 1391-1411, December.

    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. Veelenturf, L.P. & Potthoff, D. & Huisman, D. & Kroon, L.G. & Maróti, G. & Wagelmans, A.P.M., 2013. "A Quasi-Robust Optimization Approach for Resource Rescheduling," Econometric Institute Research Papers 50110, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    2. Leo Kroon & Gábor Maróti & Lars Nielsen, 2015. "Rescheduling of Railway Rolling Stock with Dynamic Passenger Flows," Transportation Science, INFORMS, vol. 49(2), pages 165-184, May.
    3. Kroon, L.G. & Huisman, D., 2011. "Algorithmic Support for Disruption Management at Netherlands Railways," Econometric Institute Research Papers EI 2011-06, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    4. Lukas Bach & Twan Dollevoet & Dennis Huisman, 2016. "Integrating Timetabling and Crew Scheduling at a Freight Railway Operator," Transportation Science, INFORMS, vol. 50(3), pages 878-891, August.
    5. Nielsen, Lars Kjær & Kroon, Leo & Maróti, Gábor, 2012. "A rolling horizon approach for disruption management of railway rolling stock," European Journal of Operational Research, Elsevier, vol. 220(2), pages 496-509.
    6. Bach, L. & Dollevoet, T.A.B. & Huisman, D., 2014. "Integrating Timetabling and Crew," Econometric Institute Research Papers EI 2014-03, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    7. Evelien van der Hurk & Haris N. Koutsopoulos & Nigel Wilson & Leo G. Kroon & Gábor Maróti, 2016. "Shuttle Planning for Link Closures in Urban Public Transport Networks," Transportation Science, INFORMS, vol. 50(3), pages 947-965, August.
    8. Lusby, Richard M. & Larsen, Jesper & Bull, Simon, 2018. "A survey on robustness in railway planning," European Journal of Operational Research, Elsevier, vol. 266(1), pages 1-15.
    9. Louwerse, Ilse & Huisman, Dennis, 2014. "Adjusting a railway timetable in case of partial or complete blockades," European Journal of Operational Research, Elsevier, vol. 235(3), pages 583-593.
    10. Daniel Potthoff & Dennis Huisman & Guy Desaulniers, 2010. "Column Generation with Dynamic Duty Selection for Railway Crew Rescheduling," Transportation Science, INFORMS, vol. 44(4), pages 493-505, November.
    11. Sato, Keisuke & Fukumura, Naoto, 2012. "Real-time freight locomotive rescheduling and uncovered train detection during disruption," European Journal of Operational Research, Elsevier, vol. 221(3), pages 636-648.
    12. Sels, P. & Dewilde, T. & Cattrysse, D. & Vansteenwegen, P., 2016. "Reducing the passenger travel time in practice by the automated construction of a robust railway timetable," Transportation Research Part B: Methodological, Elsevier, vol. 84(C), pages 124-156.
    13. Breugem, T. & Dollevoet, T.A.B. & Huisman, D., 2017. "Is Equality always desirable?," Econometric Institute Research Papers EI2017-30, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    14. Polinder, G.-J. & Breugem, T. & Dollevoet, T.A.B. & Maróti, G., 2019. "An Adjustable Robust Optimization Approach for Periodic Timetabling," Econometric Institute Research Papers EI2019-01, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    15. Liping Ge & Stefan Voß & Lin Xie, 2022. "Robustness and disturbances in public transport," Public Transport, Springer, vol. 14(1), pages 191-261, March.
    16. Potthoff, D. & Huisman, D. & Desaulniers, G., 2008. "Column generation with dynamic duty selection for railway crew rescheduling," Econometric Institute Research Papers EI 2008-28, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    17. Lusby, Richard M. & Haahr, Jørgen Thorlund & Larsen, Jesper & Pisinger, David, 2017. "A Branch-and-Price algorithm for railway rolling stock rescheduling," Transportation Research Part B: Methodological, Elsevier, vol. 99(C), pages 228-250.
    18. Jiang, Feng & Cacchiani, Valentina & Toth, Paolo, 2017. "Train timetabling by skip-stop planning in highly congested lines," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 149-174.
    19. Heil, Julia & Hoffmann, Kirsten & Buscher, Udo, 2020. "Railway crew scheduling: Models, methods and applications," European Journal of Operational Research, Elsevier, vol. 283(2), pages 405-425.
    20. Barrena, Eva & Canca, David & Coelho, Leandro C. & Laporte, Gilbert, 2014. "Single-line rail rapid transit timetabling under dynamic passenger demand," Transportation Research Part B: Methodological, Elsevier, vol. 70(C), pages 134-150.

    More about this item

    Keywords

    robustness; rescheduling; crew;
    All these keywords.

    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:50:y:2016:i:1:p:204-215. 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.