Abstract
In this paper we propose a reformulation of RECIFE-MILP aimed at boosting the algorithm performance. RECIFE-MILP is a mixed integer linear programming based heuristic for the real-time railway traffic management problem, that is the problem of re-routing and rescheduling trains in case of perturbation in order to minimize the delay propagation. The reformulation which we propose exploits the topology of the railway infrastructure. Specifically, it capitalizes on the implicit relations between routing and scheduling decisions to reduce the number of binary variables of the formulation. In an experimental analysis based on realistic instances representing traffic in the French Pierrefitte-Gonesse junction, we show the performance improvement achievable through the reformulation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
For readability, in the following, with a slight abuse of notation, we say that we reformulate RECIFE-MILP instead of the formulation at the basis of the RECIFE-MILP algorithm.
References
Cacchiani, V., Huisman, D., Kidd, M., Kroon, L., Toth, P., Veelenturf, L., Wagenaar, J.: An overview of recovery models and algorithms for real-time railway rescheduling. Transp. Res. Part B Method. 63, 15–37 (2014)
Corman, F., Meng, L.: A review of online dynamic models and algorithms for railway traffic management. IEEE Trans. Intel. Transp. Syst. 16(3), 1274–1284 (2015)
Fang, W., Yang, S., Yao, X.: A survey on problem models and solution approaches to rescheduling in railway networks. IEEE Trans. Intel. Transp. Syst. 16(6), 2997–3016 (2017)
Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85–103. Springer (1972)
Lusby, R., Larsen, J., Ehrgott, M., Ryan, D.: Railway track allocation: models and methods. OR Spectr. 33(4), 843–883 (2011)
Pachl,J.: Timetable design principles. In: Hansen, I.A., Pachl, J. (eds.) Railway Timetable and Traffic, Chap. 2, pp. 9–42. Eurailpress | DVV Rail Media, Hambourg, Germany (2008)
Pellegrini, P., Marliere, G., Pesenti, R., Rodriguez, J.: RECIFE-MILP: an effective MILP-based heuristic for the real-time railway traffic management problem. IEEE Trans. Intel. Transp. Syst. 16(5), 2609–2619 (2015)
Pellegrini, P., Marlière, G., Rodriguez, J.: Optimal train routing and scheduling for managing traffic perturbations in complex junctions. Transp. Res. Part B Method. 59, 58–80 (2014)
Pellegrini, P., Marliere, G., Rodriguez, J.: A detailed analysis of the actual impact of real-time railway traffic management optimization. J. Rail Transp. Plan. Manag. 6(1), 13–31 (2016)
Quaglietta, E., Pellegrini, P., Goverde, R.M.P., Albrecht, T., Jaekel, B., Marlière, G., Rodriguez, J., Dollevoet, T., Ambrogio, B., Carcasole, D., Giaroli, M., Nicholson, G.: The ON-TIME real-time railway traffic management framework: a proof-of-concept using a scalable standardised data communication architecture. Transp. Res. Part C Em. Technol. 63, 23–50 (2016)
Samà, M., Pellegrini, P., D’Ariano, A., Rodriguez, J., Pacciarelli, D.: Ant colony optimization for the real-time train routing selection problem. Transp. Res. Part B Method. 85, 89–108 (2016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Pellegrini, P., Marlière, G., Pesenti, R., Rodriguez, J. (2017). A MILP Reformulation for Train Routing and Scheduling in Case of Perturbation. In: Sforza, A., Sterle, C. (eds) Optimization and Decision Science: Methodologies and Applications. ODS 2017. Springer Proceedings in Mathematics & Statistics, vol 217. Springer, Cham. https://doi.org/10.1007/978-3-319-67308-0_50
Download citation
DOI: https://doi.org/10.1007/978-3-319-67308-0_50
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-67307-3
Online ISBN: 978-3-319-67308-0
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)