IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v273y2019i1d10.1007_s10479-017-2644-7.html
   My bibliography  Save this article

Complexity, bounds and dynamic programming algorithms for single track train scheduling

Author

Listed:
  • Jonas Harbering

    (Georg-August-University of Göttingen)

  • Abhiram Ranade

    (Indian Institute of Technology Bombay)

  • Marie Schmidt

    (Erasmus University Rotterdam)

  • Oliver Sinnen

    (University of Auckland)

Abstract

In this work we consider the single track train scheduling problem. The problem consists of scheduling a set of trains from opposite sides along a single track. The track has intermediate stations and the trains are only allowed to pass each other at those stations. Traversal times of the trains on the blocks between the stations only depend on the block lengths but not on the train. This problem is a special case of minimizing the makespan in job shop scheduling with two counter routes and no preemption. We develop a lower bound on the makespan of the train scheduling problem which provides us with an easy solution method in some special cases. Additionally, we prove that for a fixed number of blocks the problem can be solved in pseudo-polynomial time.

Suggested Citation

  • Jonas Harbering & Abhiram Ranade & Marie Schmidt & Oliver Sinnen, 2019. "Complexity, bounds and dynamic programming algorithms for single track train scheduling," Annals of Operations Research, Springer, vol. 273(1), pages 479-500, February.
    • Handle: RePEc:spr:annopr:v:273:y:2019:i:1:d:10.1007_s10479-017-2644-7
    DOI: 10.1007/s10479-017-2644-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-017-2644-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/s10479-017-2644-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. James R. Jackson, 1956. "An extension of Johnson's results on job IDT scheduling," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 3(3), pages 201-203, September.
    2. Zhou, Xuesong & Zhong, Ming, 2007. "Single-track train timetabling with guaranteed optimality: Branch-and-bound algorithms with enhanced lower bounds," Transportation Research Part B: Methodological, Elsevier, vol. 41(3), pages 320-341, March.
    3. Carlier, Jacques, 1982. "The one-machine sequencing problem," European Journal of Operational Research, Elsevier, vol. 11(1), pages 42-47, September.
    4. David Kraay & Patrick T. Harker & Bintong Chen, 1991. "Optimal Pacing of Trains in Freight Railroads: Model Formulation and Solution," Operations Research, INFORMS, vol. 39(1), pages 82-99, February.
    5. E. R. Petersen, 1974. "Over-the-Road Transit Time for a Single Track Railway," Transportation Science, INFORMS, vol. 8(1), pages 65-74, February.
    6. Alan S. Manne, 1960. "On the Job-Shop Scheduling Problem," Operations Research, INFORMS, vol. 8(2), pages 219-223, April.
    7. M. R. Garey & D. S. Johnson & Ravi Sethi, 1976. "The Complexity of Flowshop and Jobshop Scheduling," Mathematics of Operations Research, INFORMS, vol. 1(2), pages 117-129, May.
    8. Egon Balas, 1969. "Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm," Operations Research, INFORMS, vol. 17(6), pages 941-957, December.
    9. Ove Frank, 1966. "Two-Way Traffic on a Single Line of Railway," Operations Research, INFORMS, vol. 14(5), pages 801-811, October.
    10. Teofilo Gonzalez, 1982. "Unit Execution Time Shop Problems," Mathematics of Operations Research, INFORMS, vol. 7(1), pages 57-66, February.
    11. 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.
    12. Juan Mesa & Francisco Ortega & Miguel Pozo, 2014. "Locating optimal timetables and vehicle schedules in a transit line," Annals of Operations Research, Springer, vol. 222(1), pages 439-455, November.
    13. Cacchiani, Valentina & Toth, Paolo, 2012. "Nominal and robust train timetabling problems," European Journal of Operational Research, Elsevier, vol. 219(3), pages 727-737.
    14. 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.
    15. Šemrov, D. & Marsetič, R. & Žura, M. & Todorovski, L. & Srdic, A., 2016. "Reinforcement learning approach for train rescheduling on a single-track railway," Transportation Research Part B: Methodological, Elsevier, vol. 86(C), pages 250-267.
    16. Enrique Castillo & Inmaculada Gallego & José Ureña & José Coronado, 2009. "Timetabling optimization of a single railway track line with sensitivity analysis," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 17(2), pages 256-287, December.
    17. 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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. Li, Feng & Gao, Ziyou & Wang, David Z.W. & Liu, Ronghui & Tang, Tao & Wu, Jianjun & Yang, Lixing, 2017. "A subjective capacity evaluation model for single-track railway system with δ-balanced traffic and λ-tolerance level," Transportation Research Part B: Methodological, Elsevier, vol. 105(C), pages 43-66.
    6. Yin, Jiateng & Yang, Lixing & Tang, Tao & Gao, Ziyou & Ran, Bin, 2017. "Dynamic passenger demand oriented metro train scheduling with energy-efficiency and waiting time minimization: Mixed-integer linear programming approaches," Transportation Research Part B: Methodological, Elsevier, vol. 97(C), pages 182-213.
    7. Blazewicz, Jacek & Domschke, Wolfgang & Pesch, Erwin, 1996. "The job shop scheduling problem: Conventional and new solution techniques," European Journal of Operational Research, Elsevier, vol. 93(1), pages 1-33, August.
    8. Mu, Shi & Dessouky, Maged, 2011. "Scheduling freight trains traveling on complex networks," Transportation Research Part B: Methodological, Elsevier, vol. 45(7), pages 1103-1123, August.
    9. Jiateng Yin & Lixing Yang & Xuesong Zhou & Tao Tang & Ziyou Gao, 2019. "Balancing a one‐way corridor capacity and safety‐oriented reliability: A stochastic optimization approach for metro train timetabling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(4), pages 297-320, June.
    10. Limsawasd, Charinee & Athigakunagorn, Nathee & Khathawatcharakun, Phattadon & Boonmee, Atiwat, 2022. "Skip-Stop Strategy Patterns optimization to enhance mass transit operation under physical distancing policy due to COVID-19 pandemic outbreak," Transport Policy, Elsevier, vol. 126(C), pages 225-238.
    11. Li, Feng & Gao, Ziyou & Li, Keping & Yang, Lixing, 2008. "Efficient scheduling of railway traffic based on global information of train," Transportation Research Part B: Methodological, Elsevier, vol. 42(10), pages 1008-1030, December.
    12. 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.
    13. 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.
    14. Li, Feng & Sheu, Jiuh-Biing & Gao, Zi-You, 2014. "Deadlock analysis, prevention and train optimal travel mechanism in single-track railway system," Transportation Research Part B: Methodological, Elsevier, vol. 68(C), pages 385-414.
    15. Zhang, Chuntian & Gao, Yuan & Yang, Lixing & Gao, Ziyou & Qi, Jianguo, 2020. "Joint optimization of train scheduling and maintenance planning in a railway network: A heuristic algorithm using Lagrangian relaxation," Transportation Research Part B: Methodological, Elsevier, vol. 134(C), pages 64-92.
    16. 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.
    17. 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.
    18. 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).
    19. 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.
    20. Da Col, Giacomo & Teppan, Erich C., 2022. "Industrial-size job shop scheduling with constraint programming," Operations Research Perspectives, Elsevier, vol. 9(C).

    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:annopr:v:273:y:2019:i:1:d:10.1007_s10479-017-2644-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.