IDEAS home Printed from https://ideas.repec.org/p/ems/eureir/79917.html
   My bibliography  Save this paper

A heuristic for real-time crew rescheduling during small disruptions

Author

Listed:
  • Verhaegh, T.
  • Huisman, D.
  • Fioole, P-J.
  • Vera, J.C.

Abstract

Due to unforeseen problems, disruptions occur at railway passenger operators. Proper real-time crew management is needed to prevent disruptions to spread over space and time. Netherlands railways (NS) has algorithmic support from a solver to obtain good crew rescheduling solutions during big disruptions. However, small disruptions are still manually solved by human dispatchers who have limited solving capacity. In this paper the rescheduling for crews during small disruptions is modeled as an iterative-deepening depth-first search in a tree, which is combined with several OR techniques, obtaining a heuristic method. The heuristic focuses on real-life usability and uses the up- dated rolling-stock schedule as input. Testing the heuristic on about 5,000 test instances shows that the heuristic delivers good and desirable rescheduling solutions within fraction of seconds, outperforming other well-known methods from the literature.

Suggested Citation

  • Verhaegh, T. & Huisman, D. & Fioole, P-J. & Vera, J.C., 2016. "A heuristic for real-time crew rescheduling during small disruptions," Econometric Institute Research Papers EI2016-09, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    • Handle: RePEc:ems:eureir:79917
    as

    Download full text from publisher

    File URL: https://repub.eur.nl/pub/79917/EI2016-09.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Huisman, Dennis, 2007. "A column generation approach for the rail crew re-scheduling problem," European Journal of Operational Research, Elsevier, vol. 180(1), pages 163-173, July.
    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. Perumal, Shyam S.G. & Lusby, Richard M. & Larsen, Jesper, 2022. "Electric bus planning & scheduling: A review of related problems and methodologies," European Journal of Operational Research, Elsevier, vol. 301(2), pages 395-413.
    2. Borgonjon, Tessa & Maenhout, Broos, 2022. "An exact approach for the personnel task rescheduling problem with task retiming," European Journal of Operational Research, Elsevier, vol. 296(2), pages 465-484.
    3. Masoud Yaghini & Mohammad Karimi & Mohadeseh Rahbar, 2015. "A set covering approach for multi-depot train driver scheduling," Journal of Combinatorial Optimization, Springer, vol. 29(3), pages 636-654, April.
    4. 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.
    5. 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.
    6. Lin, Zhiyuan & Kwan, Raymond S.K., 2016. "A branch-and-price approach for solving the train unit scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 97-120.
    7. Dekker, M.M. & van Lieshout, R.N. & Ball, R.C. & Bouman, P.C. & Dekker, S.C. & Dijkstra, H.A. & Goverde, R.M.P. & Huisman, D. & Panja, D. & Schaafsma, A.M. & van den Akker, M., 2018. "A Next Step in Disruption Management: Combining Operations Research and Complexity Science," Econometric Institute Research Papers EI2018-25, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    8. Taslimi, Bijan & Babaie Sarijaloo, Farnaz & Liu, Hongcheng & Pardalos, Panos M., 2022. "A novel mixed integer programming model for freight train travel time estimation," European Journal of Operational Research, Elsevier, vol. 300(2), pages 676-688.
    9. Chen, Zebin & Li, Shukai & D’Ariano, Andrea & Yang, Lixing, 2022. "Real-time optimization for train regulation and stop-skipping adjustment strategy of urban rail transit lines," Omega, Elsevier, vol. 110(C).
    10. Y. Wang (Ying) & Z. Shang (Zheming) & Huisman, D. & D'Ariano, A. & J.C. Zhang (Jinchuan), 2018. "A Lagrangian Relaxation Approach Based on a Time-Space-State Network for Railway Crew Scheduling," Econometric Institute Research Papers EI2018-45, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    11. 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.
    12. 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.
    13. 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.
    14. Gabriel E. Sánchez-Martínez & Nigel H. M. Wilson & Haris N. Koutsopoulos, 2017. "Schedule-free high-frequency transit operations," Public Transport, Springer, vol. 9(1), pages 285-305, July.
    15. Hilbert Snijders & Ricardo L. Saldanha, 2017. "Decision support for scheduling security crews at Netherlands Railways," Public Transport, Springer, vol. 9(1), pages 193-215, July.
    16. 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.
    17. Mark M. Dekker & Rolf N. Lieshout & Robin C. Ball & Paul C. Bouman & Stefan C. Dekker & Henk A. Dijkstra & Rob M. P. Goverde & Dennis Huisman & Debabrata Panja & Alfons A. M. Schaafsma & Marjan Akker, 2022. "A next step in disruption management: combining operations research and complexity science," Public Transport, Springer, vol. 14(1), pages 5-26, March.
    18. Breugem, T. & van Rossum, B.T.C. & Dollevoet, T. & Huisman, D., 2022. "A column generation approach for the integrated crew re-planning problem," Omega, Elsevier, vol. 107(C).
    19. Yan, Ran & Wang, Shuaian & Cao, Jiannong & Sun, Defeng, 2021. "Shipping Domain Knowledge Informed Prediction and Optimization in Port State Control," Transportation Research Part B: Methodological, Elsevier, vol. 149(C), pages 52-78.
    20. Maenhout, Broos & Vanhoucke, Mario, 2013. "Reconstructing nurse schedules: Computational insights in the problem size parameters," Omega, Elsevier, vol. 41(5), pages 903-918.

    More about this item

    Keywords

    railways; real-time crew rescheduling;

    NEP fields

    This paper has been announced in the following NEP Reports:

    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:ems:eureir:79917. 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: RePub (email available below). General contact details of provider: https://edirc.repec.org/data/feeurnl.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.