IDEAS home Printed from https://ideas.repec.org/a/spr/snopef/v3y2022i4d10.1007_s43069-022-00171-7.html
   My bibliography  Save this article

Multiple Train Repositioning Operations in a Railyard Network

Author

Listed:
  • Mina Aliakbari

    (Texas A&M University)

  • Joseph Geunes

    (Texas A&M University)

Abstract

This paper considers the simultaneous movement of multiple trains within a railyard network, where each of a number of trains has an origin location and destination location on the network. We wish to minimize the total time required to move all trains from their origin to destination locations, while ensuring that at most one train occupies each track segment at any given time. We propose an integer programming model that is able to solve small problem instances exactly, as well as a heuristic solution method for solving problems of realistic size in acceptable computing time. Our constructive heuristic approach uses a ranked priority list of trains that require repositioning, and sequentially determines a route on the network for each train in priority order. We then relax the strict priority ordering rule by applying a Greedy Randomized Adaptive Search Procedure (GRASP) based on the underlying constructive heuristic. As we demonstrate via a set of computational tests, this heuristic approach is able to find good quality feasible solutions in fast computing time, drastically reducing the labor hours typically dedicated to routinely solving this problem in practice.

Suggested Citation

  • Mina Aliakbari & Joseph Geunes, 2022. "Multiple Train Repositioning Operations in a Railyard Network," SN Operations Research Forum, Springer, vol. 3(4), pages 1-31, December.
    • Handle: RePEc:spr:snopef:v:3:y:2022:i:4:d:10.1007_s43069-022-00171-7
    DOI: 10.1007/s43069-022-00171-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s43069-022-00171-7
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s43069-022-00171-7?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
    ---><---

    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. Kanet, John J., 1986. "Tactically delayed versus non-delay scheduling: An experimental investigation," European Journal of Operational Research, Elsevier, vol. 24(1), pages 99-105, January.
    2. 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.
    3. Peter J. Zwaneveld & Leo G. Kroon & H. Edwin Romeijn & Marc Salomon & Stéphane Dauzère-Pérès & Stan P. M. Van Hoesel & Harrie W. Ambergen, 1996. "Routing Trains Through Railway Stations: Model Formulation and Algorithms," Transportation Science, INFORMS, vol. 30(3), pages 181-194, August.
    4. Jin Y. Yen, 1971. "Finding the K Shortest Loopless Paths in a Network," Management Science, INFORMS, vol. 17(11), pages 712-716, July.
    5. 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.
    6. Ralf Borndörfer & Berkan Erol & Thomas Graffagnino & Thomas Schlechte & Elmar Swarat, 2014. "Optimizing the Simplon railway corridor," Annals of Operations Research, Springer, vol. 218(1), pages 93-106, July.
    7. Markus Bohlin & Ronny Hansmann & Uwe T. Zimmermann, 2018. "Optimization of Railway Freight Shunting," International Series in Operations Research & Management Science, in: Ralf Borndörfer & Torsten Klug & Leonardo Lamorgese & Carlo Mannino & Markus Reuther & Thomas Schlec (ed.), Handbook of Optimization in the Railway Industry, chapter 0, pages 181-212, Springer.
    8. 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.
    9. Ravindra K. Ahuja & Krishna C. Jha & Jian Liu, 2007. "Solving Real-Life Railroad Blocking Problems," Interfaces, INFORMS, vol. 37(5), pages 404-419, October.
    10. 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.
    11. Shi Qiang Liu & Erhan Kozan, 2011. "Scheduling Trains with Priorities: A No-Wait Blocking Parallel-Machine Job-Shop Scheduling Model," Transportation Science, INFORMS, vol. 45(2), pages 175-198, May.
    12. Ralf Borndörfer & Torsten Klug & Thomas Schlechte & Armin Fügenschuh & Thilo Schang & Hanno Schülldorf, 2016. "The Freight Train Routing Problem for Congested Railway Networks with Mixed Traffic," Transportation Science, INFORMS, vol. 50(2), pages 408-423, May.
    13. Alberto Caprara & Matteo Fischetti & Paolo Toth, 2002. "Modeling and Solving the Train Timetabling Problem," Operations Research, INFORMS, vol. 50(5), pages 851-861, October.
    14. 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.
    15. 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.
    16. Higgins, A. & Kozan, E. & Ferreira, L., 1996. "Optimal scheduling of trains on a single line track," Transportation Research Part B: Methodological, Elsevier, vol. 30(2), pages 147-161, April.
    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. 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.
    2. Xiaoming Xu & Keping Li & Lixing Yang & Ziyou Gao, 2019. "An efficient train scheduling algorithm on a single-track railway system," Journal of Scheduling, Springer, vol. 22(1), pages 85-105, February.
    3. 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.
    4. Lamorgese, Leonardo & Mannino, Carlo & Natvig, Erik, 2017. "An exact micro–macro approach to cyclic and non-cyclic train timetabling," Omega, Elsevier, vol. 72(C), pages 59-70.
    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. 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.
    7. Wang, Yihui & Tang, Tao & Ning, Bin & Meng, Lingyun, 2017. "Integrated optimization of regular train schedule and train circulation plan for urban rail transit lines," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 105(C), pages 83-104.
    8. Jayanth Krishna Mogali & Joris Kinable & Stephen F. Smith & Zachary B. Rubinstein, 2021. "Scheduling for multi-robot routing with blocking and enabling constraints," Journal of Scheduling, Springer, vol. 24(3), pages 291-318, June.
    9. Yu-Jun Zheng, 2018. "Emergency Train Scheduling on Chinese High-Speed Railways," Transportation Science, INFORMS, vol. 52(5), pages 1077-1091, October.
    10. Zhang, Chuntian & Gao, Yuan & Cacchiani, Valentina & Yang, Lixing & Gao, Ziyou, 2023. "Train rescheduling for large-scale disruptions in a large-scale railway network," Transportation Research Part B: Methodological, Elsevier, vol. 174(C).
    11. 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.
    12. 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.
    13. Leonardo Lamorgese & Carlo Mannino & Mauro Piacentini, 2016. "Optimal Train Dispatching by Benders’-Like Reformulation," Transportation Science, INFORMS, vol. 50(3), pages 910-925, August.
    14. Huang, Yeran & Mannino, Carlo & Yang, Lixing & Tang, Tao, 2020. "Coupling time-indexed and big-M formulations for real-time train scheduling during metro service disruptions," Transportation Research Part B: Methodological, Elsevier, vol. 133(C), pages 38-61.
    15. 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.
    16. Wang, Dian & D’Ariano, Andrea & Zhao, Jun & Zhong, Qingwei & Peng, Qiyuan, 2022. "Integrated rolling stock deadhead routing and timetabling in urban rail transit lines," European Journal of Operational Research, Elsevier, vol. 298(2), pages 526-559.
    17. Meloni, Carlo & Pranzo, Marco & Samà, Marcella, 2022. "Evaluation of VaR and CVaR for the makespan in interval valued blocking job shops," International Journal of Production Economics, Elsevier, vol. 247(C).
    18. Mo, Pengli & D’Ariano, Andrea & Yang, Lixing & Veelenturf, Lucas P. & Gao, Ziyou, 2021. "An exact method for the integrated optimization of subway lines operation strategies with asymmetric passenger demand and operating costs," Transportation Research Part B: Methodological, Elsevier, vol. 149(C), pages 283-321.
    19. Carlo Mannino & Alessandro Mascis, 2009. "Optimal Real-Time Traffic Control in Metro Stations," Operations Research, INFORMS, vol. 57(4), pages 1026-1039, August.
    20. Marco Pranzo & Dario Pacciarelli, 2016. "An iterated greedy metaheuristic for the blocking job shop scheduling problem," Journal of Heuristics, Springer, vol. 22(4), pages 587-611, August.

    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:spr:snopef:v:3:y:2022:i:4:d:10.1007_s43069-022-00171-7. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.