Analysis of Strengths and Weaknesses of a MILP Model for Revising Railway Traffic Timetables

Authors Fahimeh Khoshniyat, Johanna Törnquist Krasemann



PDF
Thumbnail PDF

File

OASIcs.ATMOS.2017.10.pdf
  • Filesize: 0.64 MB
  • 17 pages

Document Identifiers

Author Details

Fahimeh Khoshniyat
Johanna Törnquist Krasemann

Cite AsGet BibTex

Fahimeh Khoshniyat and Johanna Törnquist Krasemann. Analysis of Strengths and Weaknesses of a MILP Model for Revising Railway Traffic Timetables. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/OASIcs.ATMOS.2017.10

Abstract

A railway timetable is typically planned one year in advance, but may be revised several times prior to the time of operation in order to accommodate on-demand slot requests for inserting additional trains and network maintenance. Revising timetables is a computationally demanding task, given the many dependencies and details to consider. In this paper, we focus on the potential of using optimization-based scheduling approach for revising train timetables during short term planning, from one week to few hours before the actual operation. The approach relies on a MILP (Mixed Integer Linear Program) model which is solved by using the commercial solver Gurobi. In a previous experimental study, the MILP approach was used to revise a significant part of the annual timetable for a sub-network in Southern Sweden to insert additional trains and allocate time slots for urgent maintenance. The results showed that the proposed MILP approach in many cases generates feasible, good solutions rather fast. However, proving optimality was in several cases time-consuming, especially for larger problems. Thus, there is a need to investigate and develop strategies to improve the computational performance. In this paper, we present results from a study, where a number of valid inequalities has been selected and applied to the MILP model with the aim to reduce the computation time. The experimental evaluation of the selected valid inequalities showed that although they can provide a slight improvement with respect to computation time, they are also weakening the LP relaxation of the model.
Keywords
  • Railway
  • Timetable
  • Short term planning
  • Boosting Methods
  • Valid inequalities

Metrics

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

References

  1. Valentina Cacchiani, Dennis Huisman, Martin Kidd, Leo Kroon, Paolo Toth, Lucas Veelenturf, and Joris Wagenaar. An overview of recovery models and algorithms for real-time railway rescheduling. Transportation Research Part B: Methodological, 63:15-37, May 2014. URL: http://dx.doi.org/10.1016/j.trb.2014.01.009.
  2. Inc. Gurobi Optimization. Gurobi optimizer reference manual, 2017. URL: http://www.gurobi.com.
  3. Fahimeh Khoshniyat and Johanna Törnquist Krasemann. On-demand timetabling in dense railway networks: Methods and challenges. In Proceedings of 7th International Conference on Railway Operations Modelling and Analysis - RailLille, 2017. Google Scholar
  4. Ed Klotz and Alexandra M. Newman. Practical guidelines for solving difficult mixed integer linear programs. Surveys in Operations Research and Management Science, 18(1–2):18-32, October 2013. URL: http://dx.doi.org/10.1016/j.sorms.2012.12.001.
  5. Richard M Lusby, Jesper Larsen, Matthias Ehrgott, and David Ryan. Railway track allocation: models and methods. OR spectrum, 33(4):843-883, 2011. Google Scholar
  6. Sylvain Mouret, Ignacio E. Grossmann, and Pierre Pestiaux. Time representations and mathematical models for process scheduling problems. Computers &Chemical Engineering, 35(6):1038-1063, June 2011. URL: http://dx.doi.org/10.1016/j.compchemeng.2010.07.007.
  7. Paola Pellegrini, Grégory Marliere, Raffaele Pesenti, and Joaquín Rodriguez. RECIFE-MILP: An Effective MILP-Based Heuristic for the Real-Time Railway Traffic Management Problem. IEEE Transactions on Intelligent Transportation Systems, 16(5):2609-2619, October 2015. URL: http://dx.doi.org/10.1109/TITS.2015.2414294.
  8. Johanna Törnquist and Jan A. Persson. N-tracked railway traffic re-scheduling during disturbances. Transportation Research Part B: Methodological, 41(3):342-362, 2007. URL: http://dx.doi.org/10.1016/j.trb.2006.06.001.
  9. Johanna Törnquist Krasemann. Computational decision-support for railway traffic management and associated configuration challenges: An experimental study. Journal of Rail Transport Planning &Management, 2015. URL: http://dx.doi.org/10.1016/j.jrtpm.2015.09.002.
  10. Juan P. Vielma. Mixed Integer Linear Programming Formulation Techniques. SIAM Review, 57(1):3-57, January 2015. URL: http://dx.doi.org/10.1137/130915303.
  11. Peter J. Zwaneveld, Leo G. Kroon, and Stan P.M. van Hoesel. Routing trains through a railway station based on a node packing model. European Journal of Operational Research, 128(1):14 - 33, 2001. URL: http://dx.doi.org/10.1016/S0377-2217(00)00087-4.
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