Document Open Access Logo

Train Scheduling on a Unidirectional Path

Authors Apoorv Garg, Abhiram G. Ranade

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2017.29.pdf
  • Filesize: 0.58 MB
  • 14 pages

Document Identifiers

Author Details

Apoorv Garg
Abhiram G. Ranade

Cite As Get BibTex

Apoorv Garg and Abhiram G. Ranade. Train Scheduling on a Unidirectional Path. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 29:1-29:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FSTTCS.2017.29

Abstract

We formulate what might be the simplest train scheduling problem considered in the literature and show it to be NP-hard.  We also give a log-factor randomised algorithm for it.  In our problem we have a unidirectional train track with equidistant stations, each station initially having at most one train. In addition, there can be at most one train poised to enter each station.  The trains must move to their destinations subject to the constraint that at every time instant there can be at most one train at each station and on the track between stations.  The goal is to minimise the maximum delay of any train.  Our problem can also be interpreted as a packet routing problem, and our work strengthens the hardness results from that literature.

Subject Classification

Keywords
  • Combinatorial optimization
  • Train scheduling
  • Max-delay minimization
  • Complexity analysis
  • Approximation algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. V. Cacchiani, D. Huisman, M. Kidd, L. Kroon, P. Toth, L. Veelenturf, and J. Wagenaar. An overview of recovery models and algorithms for real-time railway rescheduling. Transportation Research Part B: Methodological, 63:15-37, 2014. URL: http://dx.doi.org/10.1016/j.trb.2014.01.009.
  2. X. Cai, C.J. Goh, and Alistair I. Mees. Greedy heuristics for rapid scheduling of trains on a single track. IIE Transactions, 30(5):481-493, May 1998. URL: http://dx.doi.org/10.1023/A:1007551424010.
  3. Gabrio Caimi, Fabián A. Chudak, Martin Fuchsberger, Marco Laumanns, and Rico Zenklusen. A new resource-constrained multicommodity flow model for conflict-free train routing and scheduling. Transportation Science, 45(2):212-227, 2011. URL: http://dx.doi.org/10.1287/trsc.1100.0349.
  4. Te-Wei Chiang, Hai-Yen Hau, Hwan-Ming Chiang, Su-Yun Ko, and Chao-Ho Hsieh. Knowledge-based system for railway scheduling. Data Knowl. Eng., 27(3):289-312, 1998. URL: http://dx.doi.org/10.1016/S0169-023X(97)00040-2.
  5. Andrea E. F. Clementi and Miriam Di Ianni. Optimum schedule problems in store and forward networks. In Proceedings IEEE INFOCOM '94, The Conference on Computer Communications, Thirteenth Annual Joint Conference of the IEEE Computer and Communications Societies, Networking for Global Communications, Toronto, Ontario, Canada, June 12-16, 1994, pages 1336-1343. IEEE, 1994. URL: http://dx.doi.org/10.1109/INFCOM.1994.337560.
  6. Andrea D’Ariano. Improving real-time train dispatching: Models, algorithms and applications. Doctoral thesis, TRAIL Research School, Deft, The Netherlands, 2008. Google Scholar
  7. Wei Fang, Shengxiang Yang, and Xin Yao. A survey on problem models and solution approaches to rescheduling in railway networks. IEEE Trans. Intelligent Transportation Systems, 16(6):2997-3016, 2015. URL: http://dx.doi.org/10.1109/TITS.2015.2446985.
  8. Holger Flier, Matús Mihalák, Anita Schöbel, Peter Widmayer, and Anna Zych. Vertex disjoint paths for dispatching in railways. In Thomas Erlebach and Marco E. Lübbecke, editors, ATMOS 2010 - 10th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, Liverpool, United Kingdom, September 6-10, 2010, volume 14 of OASICS, pages 61-73. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2010. URL: http://dx.doi.org/10.4230/OASIcs.ATMOS.2010.61.
  9. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman &Co., New York, NY, USA, 1979. Google Scholar
  10. J. Harbering, A. Ranade, and M. Schmidt. Single track train scheduling. In Z. Hanzalek, G. Kendall, B. McCollum, and P. Sucha, editors, In proceedings of the 7th Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2015), 25 - 28 Aug 2015, Prague, Czech Republic, pages 102-117, 2015. Google Scholar
  11. R. V. Iyer and S. Ghosh. Daryn-a distributed decision-making algorithm for railway networks: modeling and simulation. IEEE Transactions on Vehicular Technology, 44(1):180-191, February 1995. URL: http://dx.doi.org/10.1109/25.350284.
  12. Johanna Törnquist Krasemann. Design of an effective algorithm for fast response to the re-scheduling of railway traffic during disturbances. Transportation Research Part C: Emerging Technologies, 20(1):62-78, 2012. Special issue on Optimization in Public Transport+ISTT2011. URL: http://dx.doi.org/10.1016/j.trc.2010.12.004.
  13. Frank Thomson Leighton, Bruce M. Maggs, Abhiram G. Ranade, and Satish Rao. Randomized routing and sorting on fixed-connection networks. J. Algorithms, 17(1):157-205, 1994. URL: http://dx.doi.org/10.1006/jagm.1994.1030.
  14. Frank Thomson Leighton, Bruce M. Maggs, and Satish Rao. Packet routing and job-shop scheduling in O(congestion + dilation) steps. Combinatorica, 14(2):167-186, 1994. URL: http://dx.doi.org/10.1007/BF01215349.
  15. Frank Thomson Leighton, Bruce M. Maggs, and Andréa W. Richa. Fast algorithms for finding o(congestion + dilation) packet routing schedules. Combinatorica, 19(3):375-401, 1999. URL: http://dx.doi.org/10.1007/s004930050061.
  16. Joseph Y.-T. Leung, Tommy W. Tam, and Gilbert H. Young. On-line routing of real-time messages. J. Parallel Distrib. Comput., 34(2):211-217, 1996. URL: http://dx.doi.org/10.1006/jpdc.1996.0057.
  17. Carlo Mannino and Alessandro Mascis. Optimal real-time traffic control in metro stations. Operations Research, 57(4):1026-1039, 2009. URL: http://dx.doi.org/10.1287/opre.1080.0642.
  18. Alessandro Mascis and Dario Pacciarelli. Job-shop scheduling with blocking and no-wait constraints. European Journal of Operational Research, 143(3):498-517, 2002. URL: http://dx.doi.org/10.1016/S0377-2217(01)00338-1.
  19. Sundaravalli Narayanaswami and Narayan Rangaraj. Scheduling and rescheduling of railway operations: A review and expository analysis. Technology Operation Management, 2(2):102-122, December 2011. URL: http://dx.doi.org/10.1007/s13727-012-0006-x.
  20. Britta Peis, Martin Skutella, and Andreas Wiese. Packet routing: Complexity and algorithms. In Evripidis Bampis and Klaus Jansen, editors, Approximation and Online Algorithms, 7th International Workshop, WAOA 2009, Copenhagen, Denmark, September 10-11, 2009. Revised Papers, volume 5893 of Lecture Notes in Computer Science, pages 217-228. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-12450-1_20.
  21. Paola Pellegrini and Joaquin Rodriguez. Single european sky and single european railway area: A system level analysis of air and rail transportation. Transportation Research Part A: Policy and Practice, 57:64-86, 2013. URL: http://dx.doi.org/10.1016/j.tra.2013.09.004.
  22. Thomas Rothvoß. A simpler proof for o(congestion + dilation) packet routing. CoRR, abs/1206.3718, 2012. URL: http://arxiv.org/abs/1206.3718.
  23. Ismail Sahin. Railway traffic control and train scheduling based oninter-train conflict management. Transportation Research Part B: Methodological, 33(7):511-534, September 1999. URL: http://dx.doi.org/10.1016/S0191-2615(99)00004-1.
  24. Christian Scheideler. Universal routing strategies for interconnection networks. In G. Goos, J. Hartmanis, and J. van Leeuwen, editors, Lecture Notes in Computer Science 1390, pages 57-67. W. H. Freeman &Co., New York, NY, USA, 1998. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact