IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v44y2010i1p175-192.html
   My bibliography  Save this article

A tabu search algorithm for rerouting trains during rail operations

Author

Listed:
  • Corman, Francesco
  • D'Ariano, Andrea
  • Pacciarelli, Dario
  • Pranzo, Marco

Abstract

This paper addresses the problem of train conflict detection and resolution, which is dealt every day by traffic controllers to adapt the timetable to delays and other unpredictable events occurring in real-time. We describe a number of algorithmic improvements implemented in the real-time traffic management system ROMA (Railway traffic Optimization by Means of Alternative graphs), achieved by incorporating effective rescheduling algorithms and local rerouting strategies in a tabu search scheme. We alternate a fast heuristic and a truncated branch and bound algorithm for computing train schedules within a short computation time, and investigate the effectiveness of using different neighborhood structures for train rerouting. The computational experiments are based on practical size instances from a dispatching area of the Dutch railway network and include complex disturbances with multiple late trains and blocked tracks. Several small instances are solved to optimality in order to compare the heuristic solutions with the optimum. For small instances, the new tabu search algorithms find optimal solutions. For large instances, the solutions generated by the new algorithms after 20Â s of computation are up to more than 15% better than those achieved within 180Â s by the previous version of ROMA.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:transb:v:44:y:2010:i:1:p:175-192
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191-2615(09)00070-8
    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. Moreno Perez, Jose A. & Marcos Moreno-Vega, J. & Rodriguez Martin, Inmaculada, 2003. "Variable neighborhood tabu search and its application to the median cycle problem," European Journal of Operational Research, Elsevier, vol. 151(2), pages 365-378, December.
    2. Carey, Malachy & Crawford, Ivan, 2007. "Scheduling trains on a network of busy complex stations," Transportation Research Part B: Methodological, Elsevier, vol. 41(2), pages 159-178, February.
    3. Flamini, Marta & Pacciarelli, Dario, 2008. "Real time management of a metro rail terminus," European Journal of Operational Research, Elsevier, vol. 189(3), pages 746-761, September.
    4. 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.
    5. Andrea D'Ariano & Francesco Corman & Dario Pacciarelli & Marco Pranzo, 2008. "Reordering and Local Rerouting Strategies to Manage Train Traffic in Real Time," Transportation Science, INFORMS, vol. 42(4), pages 405-419, November.
    6. Zwaneveld, Peter J. & Kroon, Leo G. & van Hoesel, Stan P. M., 2001. "Routing trains through a railway station based on a node packing model," European Journal of Operational Research, Elsevier, vol. 128(1), pages 14-33, January.
    7. Egon Balas, 1969. "Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm," Operations Research, INFORMS, vol. 17(6), pages 941-957, December.
    8. Ove Frank, 1966. "Two-Way Traffic on a Single Line of Railway," Operations Research, INFORMS, vol. 14(5), pages 801-811, October.
    9. Gabrio Caimi & Dan Burkolter & Thomas Herrmann, 2005. "Finding Delay-Tolerant Train Routings through Stations," Operations Research Proceedings, in: Hein Fleuren & Dick Hertog & Peter Kort (ed.), Operations Research Proceedings 2004, pages 136-143, Springer.
    10. Nicholas G. Hall & Chelliah Sriskandarajah, 1996. "A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process," Operations Research, INFORMS, vol. 44(3), pages 510-525, June.
    11. Mazzarello, Maura & Ottaviani, Ennio, 2007. "A traffic management system for real-time traffic optimisation in railways," Transportation Research Part B: Methodological, Elsevier, vol. 41(2), pages 246-274, February.
    12. 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.
    13. D'Ariano, Andrea & Pacciarelli, Dario & Pranzo, Marco, 2007. "A branch and bound algorithm for scheduling trains in a railway network," European Journal of Operational Research, Elsevier, vol. 183(2), pages 643-657, December.
    14. Mascis, Alessandro & Pacciarelli, Dario, 2002. "Job-shop scheduling with blocking and no-wait constraints," European Journal of Operational Research, Elsevier, vol. 143(3), pages 498-517, December.
    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. Andrea D'Ariano & Francesco Corman & Dario Pacciarelli & Marco Pranzo, 2008. "Reordering and Local Rerouting Strategies to Manage Train Traffic in Real Time," Transportation Science, INFORMS, vol. 42(4), pages 405-419, November.
    2. Samà, Marcella & Pellegrini, Paola & D’Ariano, Andrea & Rodriguez, Joaquin & Pacciarelli, Dario, 2016. "Ant colony optimization for the real-time train routing selection problem," Transportation Research Part B: Methodological, Elsevier, vol. 85(C), pages 89-108.
    3. Dewilde, Thijs & Sels, Peter & Cattrysse, Dirk & Vansteenwegen, Pieter, 2014. "Improving the robustness in railway station areas," European Journal of Operational Research, Elsevier, vol. 235(1), pages 276-286.
    4. 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.
    5. Corman, F. & D’Ariano, A. & Pacciarelli, D. & Pranzo, M., 2012. "Optimal inter-area coordination of train rescheduling decisions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 71-88.
    6. 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.
    7. Wenliang Zhou & Xiaorong You & Wenzhuang Fan, 2020. "A Mixed Integer Linear Programming Method for Simultaneous Multi-Periodic Train Timetabling and Routing on a High-Speed Rail Network," Sustainability, MDPI, vol. 12(3), pages 1-34, February.
    8. Burdett, R.L. & Kozan, E., 2009. "Techniques for inserting additional trains into existing timetables," Transportation Research Part B: Methodological, Elsevier, vol. 43(8-9), pages 821-836, September.
    9. 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.
    10. 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.
    11. Luan, Xiaojie & Wang, Yihui & De Schutter, Bart & Meng, Lingyun & Lodewijks, Gabriel & Corman, Francesco, 2018. "Integration of real-time traffic management and train control for rail networks - Part 1: Optimization problems and solution approaches," Transportation Research Part B: Methodological, Elsevier, vol. 115(C), pages 41-71.
    12. Pellegrini, Paola & Pesenti, Raffaele & Rodriguez, Joaquin, 2019. "Efficient train re-routing and rescheduling: Valid inequalities and reformulation of RECIFE-MILP," Transportation Research Part B: Methodological, Elsevier, vol. 120(C), pages 33-48.
    13. 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.
    14. Carlo Mannino & Alessandro Mascis, 2009. "Optimal Real-Time Traffic Control in Metro Stations," Operations Research, INFORMS, vol. 57(4), pages 1026-1039, August.
    15. Julia Lange & Frank Werner, 2018. "Approaches to modeling train scheduling problems as job-shop problems with blocking constraints," Journal of Scheduling, Springer, vol. 21(2), pages 191-207, April.
    16. Lee, Yusin & Chen, Chuen-Yih, 2009. "A heuristic for the train pathing and timetabling problem," Transportation Research Part B: Methodological, Elsevier, vol. 43(8-9), pages 837-851, September.
    17. 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.
    18. 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.
    19. Mogali, Jayanth Krishna & Barbulescu, Laura & Smith, Stephen F., 2021. "Efficient primal heuristic updates for the blocking job shop problem," European Journal of Operational Research, Elsevier, vol. 295(1), pages 82-101.
    20. Min, Yun-Hong & Park, Myoung-Ju & Hong, Sung-Pil & Hong, Soon-Heum, 2011. "An appraisal of a column-generation-based algorithm for centralized train-conflict resolution on a metropolitan railway network," Transportation Research Part B: Methodological, Elsevier, vol. 45(2), pages 409-429, February.

    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:transb:v:44:y:2010:i:1:p:175-192. 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/wps/find/journaldescription.cws_home/548/description#description .

    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.