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

Column generation with dynamic duty selection for railway crew rescheduling

Author

Listed:
  • Potthoff, D.
  • Huisman, D.
  • Desaulniers, G.

Abstract

The Dutch railway network experiences about three large disruptions per day on average. In this paper, we present an algorithm to reschedule the crews when such a disruption occurs. The algorithm is based on column generation techniques combined with Lagrangian heuristics. Since the number of duties is very large in practical instances, we first define a core problem of tractable size. If some tasks remain uncovered in the solution of the core problem, we perform a neighborhood exploration to improve the solution. Computational experiments with real-life instances show that our method is capable of producing good solutions within a couple of minutes of Computation time.

Suggested Citation

  • 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.
    • Handle: RePEc:ems:eureir:14423
    as

    Download full text from publisher

    File URL: https://repub.eur.nl/pub/14423/EI2008-28.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    2. 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.
    3. Pepin, A.S. & Desaulniers, G. & Hertz, A. & Huisman, D., 2006. "Comparison of heuristic approaches for the multiple depot vehicle scheduling problem," Econometric Institute Research Papers EI 2006-34, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    4. Ladislav Lettovský & Ellis L. Johnson & George L. Nemhauser, 2000. "Airline Crew Recovery," Transportation Science, INFORMS, vol. 34(4), pages 337-348, November.
    5. Medard, Claude P. & Sawhney, Nidhi, 2007. "Airline crew scheduling from planning to operations," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1013-1027, December.
    6. Dennis Huisman & Leo G. Kroon & Ramon M. Lentink & Michiel J. C. M. Vromans, 2005. "Operations Research in passenger railway transportation," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 59(4), pages 467-497, November.
    7. 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.
    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. Kaj Holmberg & Di Yuan, 2000. "A Lagrangian Heuristic Based Branch-and-Bound Approach for the Capacitated Network Design Problem," Operations Research, INFORMS, vol. 48(3), pages 461-481, June.
    10. Huisman, D., 2005. "A column generation approach to solve the crew re-scheduling problem," Econometric Institute Research Papers EI 2005-54, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    11. 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.
    12. 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.
    13. Jacques Desrosiers & Marco E. Lübbecke, 2005. "A Primer in Column Generation," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 1-32, 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. 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.
    2. Kroon, L.G. & Huisman, D., 2009. "Algorithmic Support for Railway Disruption Management," Econometric Institute Research Papers EI 2009-50, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    3. 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.
    4. Jonas Ingels & Broos Maenhout, 2017. "Employee substitutability as a tool to improve the robustness in personnel scheduling," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(3), pages 623-658, July.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. Ingels, Jonas & Maenhout, Broos, 2019. "Optimised buffer allocation to construct stable personnel shift rosters," Omega, Elsevier, vol. 82(C), pages 102-117.
    13. 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.
    14. Dollevoet, T.A.B. & Huisman, D. & Kroon, L.G. & Veelenturf, L.P. & Wagenaar, J.C., 2015. "An Iterative Framework for Real-time Railway Rescheduling," Econometric Institute Research Papers EI2015-28, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    15. 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.
    16. Veelenturf, L.P. & Potthoff, D. & Huisman, D. & Kroon, L.G., 2009. "Railway Crew Rescheduling with Retiming," Econometric Institute Research Papers EI 2009-24, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    17. van Lieshout, R.N. & Mulder, J. & Huisman, D., 2016. "The Vehicle Rescheduling Problem with Retiming," Econometric Institute Research Papers EI2016-37, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    18. 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.
    19. Maenhout, Broos & Vanhoucke, Mario, 2018. "A perturbation matheuristic for the integrated personnel shift and task re-scheduling problem," European Journal of Operational Research, Elsevier, vol. 269(3), pages 806-823.

    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. 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.
    2. 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.
    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. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. Martin Josef Geiger & Sandra Huber & Sebastian Langton & Marius Leschik & Christian Lindorf & Ulrich Tüshaus, 2018. "Multi-attribute assignment of trains to departures in rolling stock management," Annals of Operations Research, Springer, vol. 271(2), pages 1131-1163, December.
    12. 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).
    13. 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.
    14. Cacchiani, V. & Huisman, D. & Kidd, M.P. & Kroon, L.G. & Toth, P. & Veelenturf, L.P. & Wagenaar, J.C., 2013. "An Overview of Recovery Models for Real-time Railway Rescheduling," Econometric Institute Research Papers 50112, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    15. 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.
    16. Veelenturf, L.P. & Potthoff, D. & Huisman, D. & Kroon, L.G., 2009. "Railway Crew Rescheduling with Retiming," Econometric Institute Research Papers EI 2009-24, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    17. 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.
    18. Zhang, Yongxiang & Peng, Qiyuan & Yao, Yu & Zhang, Xin & Zhou, Xuesong, 2019. "Solving cyclic train timetabling problem through model reformulation: Extended time-space network construct and Alternating Direction Method of Multipliers methods," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 344-379.
    19. Stephen J. Maher, 2016. "Solving the Integrated Airline Recovery Problem Using Column-and-Row Generation," Transportation Science, INFORMS, vol. 50(1), pages 216-239, February.
    20. Qin, Hu & Moriakin, Anton & Xu, Gangyan & Li, Jiliu, 2024. "The generator distribution problem for base stations during emergency power outage: A branch-and-price-and-cut approach," European Journal of Operational Research, Elsevier, vol. 318(3), pages 752-767.

    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:ems:eureir:14423. 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.