IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v215y2011i1p227-243.html
   My bibliography  Save this article

SAPI: Statistical Analysis of Propagation of Incidents. A new approach for rescheduling trains after disruptions

Author

Listed:
  • Acuna-Agost, Rodrigo
  • Michelon, Philippe
  • Feillet, Dominique
  • Gueye, Serigne

Abstract

In this paper, we present a new approach to solve the railway rescheduling problem. This problem deals with the reparation of a disturbed railway timetable after incidents in such a way to minimize the difference between the original plan and the new provisional plan. We use a mixed integer linear programming (MIP) formulation that models this problem correctly. However, the large number of variables and constraints denies the possibility to solve this problem efficiently using a standard MIP solver. A new approach called SAPI (Statistical Analysis of Propagation of Incidents) has been developed to tackle the problem. The key point of SAPI is to estimate the probability that an event, one step of the itinerary of a train, is affected by a set of incidents. Using these probabilities, the search space is reduced, obtaining very good solutions in a short time. The method has been tested with two different networks located in France and Chile. The numerical results show that our procedure is viable in practice.

Suggested Citation

  • Acuna-Agost, Rodrigo & Michelon, Philippe & Feillet, Dominique & Gueye, Serigne, 2011. "SAPI: Statistical Analysis of Propagation of Incidents. A new approach for rescheduling trains after disruptions," European Journal of Operational Research, Elsevier, vol. 215(1), pages 227-243, November.
    • Handle: RePEc:eee:ejores:v:215:y:2011:i:1:p:227-243
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221711004954
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. 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.
    2. Jean-François Cordeau & Paolo Toth & Daniele Vigo, 1998. "A Survey of Optimization Models for Train Routing and Scheduling," Transportation Science, INFORMS, vol. 32(4), pages 380-404, November.
    3. Törnquist, Johanna & Persson, Jan A., 2007. "N-tracked railway traffic re-scheduling during disturbances," Transportation Research Part B: Methodological, Elsevier, vol. 41(3), pages 342-362, March.
    4. 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.
    5. Rodriguez, Joaquín, 2007. "A constraint programming model for real-time train scheduling at junctions," Transportation Research Part B: Methodological, Elsevier, vol. 41(2), pages 231-245, February.
    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. Zhang, Huimin & Li, Shukai & Wang, Yihui & Yang, Lixing & Gao, Ziyou, 2021. "Collaborative real-time optimization strategy for train rescheduling and track emergency maintenance of high-speed railway: A Lagrangian relaxation-based decomposition algorithm," Omega, Elsevier, vol. 102(C).
    2. Elio Canestrelli & Marco Corazza & Giuseppe Nadai & Raffaele Pesenti, 2017. "Managing the Ship Movements in the Port of Venice," Networks and Spatial Economics, Springer, vol. 17(3), pages 861-887, September.
    3. M. Shakibayifar & A. Sheikholeslami & F. Corman & E. Hassannayebi, 2020. "An integrated rescheduling model for minimizing train delays in the case of line blockage," Operational Research, Springer, vol. 20(1), pages 59-87, March.
    4. Xuelei Meng & Yahui Wang & Li Lin & Lei Li & Limin Jia, 2021. "An Integrated Model of Train Re-Scheduling and Control for High-Speed Railway," Sustainability, MDPI, vol. 13(21), pages 1-20, October.
    5. Kang, Liujiang & Li, Hao & Sun, Huijun & Wu, Jianjun & Cao, Zhiguang & Buhigiro, Nsabimana, 2021. "First train timetabling and bus service bridging in intermodal bus-and-train transit networks," Transportation Research Part B: Methodological, Elsevier, vol. 149(C), pages 443-462.
    6. Vansteenwegen, Pieter & Dewilde, Thijs & Burggraeve, Sofie & Cattrysse, Dirk, 2016. "An iterative approach for reducing the impact of infrastructure maintenance on the performance of railway systems," European Journal of Operational Research, Elsevier, vol. 252(1), pages 39-53.

    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. Pellegrini, Paola & Rodriguez, Joaquin, 2013. "Single European Sky and Single European Railway Area: A system level analysis of air and rail transportation," Transportation Research Part A: Policy and Practice, Elsevier, vol. 57(C), pages 64-86.
    2. Zhang, Yongxiang & D'Ariano, Andrea & He, Bisheng & Peng, Qiyuan, 2019. "Microscopic optimization model and algorithm for integrating train timetabling and track maintenance task scheduling," Transportation Research Part B: Methodological, Elsevier, vol. 127(C), pages 237-278.
    3. Gianmarco Garrisi & Cristina Cervelló-Pastor, 2019. "Train-Scheduling Optimization Model for Railway Networks with Multiplatform Stations," Sustainability, MDPI, vol. 12(1), pages 1-25, December.
    4. Pellegrini, Paola & Marlière, Grégory & Rodriguez, Joaquin, 2014. "Optimal train routing and scheduling for managing traffic perturbations in complex junctions," Transportation Research Part B: Methodological, Elsevier, vol. 59(C), pages 58-80.
    5. 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.
    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. David Schindl & Nicolas Zufferey, 2015. "A learning tabu search for a truck allocation problem with linear and nonlinear cost components," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(1), pages 32-45, February.
    8. Vaidyanathan, Balachandran & Ahuja, Ravindra K. & Liu, Jian & Shughart, Larry A., 2008. "Real-life locomotive planning: New formulations and computational results," Transportation Research Part B: Methodological, Elsevier, vol. 42(2), pages 147-168, February.
    9. Andrea D’Ariano & Marco Pranzo, 2009. "An Advanced Real-Time Train Dispatching System for Minimizing the Propagation of Delays in a Dispatching Area Under Severe Disturbances," Networks and Spatial Economics, Springer, vol. 9(1), pages 63-84, March.
    10. Cacchiani, Valentina & Furini, Fabio & Kidd, Martin Philip, 2016. "Approaches to a real-world Train Timetabling Problem in a railway node," Omega, Elsevier, vol. 58(C), pages 97-110.
    11. Benjamin Otto, 2019. "Aggregation techniques for frequency assignment in public transportation," Public Transport, Springer, vol. 11(1), pages 51-87, June.
    12. Juraj Čamaj & Eva Brumerčíková & Michal Petr Hranický, 2020. "Information System and Technology Optimization as a Tool for Ensuring the Competitiveness of a Railway Undertaking—Case Study," Sustainability, MDPI, vol. 12(21), pages 1-23, October.
    13. Zhou, Leishan & Tong, Lu (Carol) & Chen, Junhua & Tang, Jinjin & Zhou, Xuesong, 2017. "Joint optimization of high-speed train timetables and speed profiles: A unified modeling approach using space-time-speed grid networks," Transportation Research Part B: Methodological, Elsevier, vol. 97(C), pages 157-181.
    14. Bettinelli, Andrea & Santini, Alberto & Vigo, Daniele, 2017. "A real-time conflict solution algorithm for the train rescheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 237-265.
    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. Valentina Cacchiani & Alberto Caprara & Paolo Toth, 2019. "An Effective Peak Period Heuristic for Railway Rolling Stock Planning," Transportation Science, INFORMS, vol. 53(3), pages 746-762, May.
    17. Kroon, L.G. & Lentink, R.M. & Schrijver, A., 2006. "Shunting of Passenger Train Units: an Integrated Approach," ERIM Report Series Research in Management ERS-2006-068-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.
    18. Wang, Yihui & Zhao, Kangqi & D’Ariano, Andrea & Niu, Ru & Li, Shukai & Luan, Xiaojie, 2021. "Real-time integrated train rescheduling and rolling stock circulation planning for a metro line under disruptions," Transportation Research Part B: Methodological, Elsevier, vol. 152(C), pages 87-117.
    19. Corman, Francesco & D'Ariano, Andrea & Pacciarelli, Dario & Pranzo, Marco, 2010. "A tabu search algorithm for rerouting trains during rail operations," Transportation Research Part B: Methodological, Elsevier, vol. 44(1), pages 175-192, January.
    20. 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.

    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:eee:ejores:v:215:y:2011:i:1:p:227-243. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.