Abstract
This paper addresses the Rolling Stock Rebalancing Problem (RSRP) which arises within a passenger railway operator when the rolling stock has to be rescheduled due to changing circumstances. RSRP is relevant both in the short-term planning stage and in the real-time operations.
RSRP has as input a timetable and a rolling stock circulation where the allocation of the rolling stock among the stations at the start or at the end of a certain planning period does not match with the allocation before or after that planning period. The problem is then to modify the input rolling stock circulation in such a way that the number of remaining off-balances is minimal. If all off-balances have been solved, then the obtained rolling stock circulation can be implemented in practice.
For practical usage of solution approaches for RSRP, it is important to solve the problem quickly. Since we prove that RSRP is NP-hard, we focus on heuristic solution approaches: we describe two heuristics and compare them with each other on (variants of) real-life instances of NS, the main Dutch passenger railway operator. Finally, to get further insight in the quality of the proposed heuristics, we also compare their outcomes with optimal solutions obtained by solving an existing rolling stock circulation model.
Article PDF
Similar content being viewed by others
References
Ben-Khedher, N., Kintanar, J., Queille, C., & Stripling, W. (1998). Schedule optimization at SNCF: From conception to day of departure. Interfaces, 28, 6–23.
Brucker, P., Hurink, J., & Rolfes, T. (2003). Routing of railway carriages. Journal of Global Optimization, 27(23), 313–332.
Caprara, A., Kroon, L., Monaci, M., Peeters, M., & Toth, P. (2007). Passenger railway optimization. In C. Barnhart & G. Laporte (Eds.), Handbook in OR & MS (Vol. 14, pp. 129–187). Amsterdam: Elsevier.
Clausen, J., Larsen, A., & Larsen, J. (2005). Disruption management in the airline industry: concepts, models and methods (Technical Report). Informatics and Mathematical Modeling, Technical University of Denmark, Richard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby. http://www2.imm.dtu.dk/pubdb/p.php?3763.
Fioole, P. J., Kroon, L. G., Maróti, G., & Schrijver, A. (2006). A rolling stock circulation model for combining and splitting of passenger trains. European Journal of Operational Research, 174, 1281–1297.
Freling, R., Lentink, R. M., Kroon, L. G., & Huisman, D. (2005). Shunting of passenger train units in a railway station. Transportation Science, 39, 261–272.
Groth, J., Potthoff, D., Clausen, J., Huisman, D., Kroon, L., Maróti, G., & Nyhave Nielsen, M. (2007). Disruption management in passenger railway transportation (Econometric Institute Report EI 2007-05). The Netherlands: Erasmus University Rotterdam. https://ep.eur.nl/handle/1765/8527.
Huisman, D., Kroon, L. G., Lentink, R. M., & Vromans, M. J. C. M. (2005). Operations research in passenger railway transportation. Statistica Neerlandica, 59(4), 467–497.
Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller & J. W. Thatcher (Eds.), Complexity of computer computations (pp. 85–103). New York: Plenum Press.
Kohl, N., Larsen, A., Larsen, J., Ross, A., & Tiourine, S. (2007). Airline disruption management—perspectives, experiences and outlook. Journal of Air Transport Management, 13(3), 149–162.
Lentink, R. M. (2006). Algorithmic decision support for shunt planning. Ph.D. thesis, Erasmus University Rotterdam, The Netherlands.
Li, J., Mirchandani, P. B., & Borenstein, D. (2007). Vehicle rescheduling problem: Model and algorithms. Networks, 50(3), 211–229.
Lingaya, N., Cordeau, J. F., Desaulniers, G., Desrosiers, J., & Soumis, F. (2002). Operational car assignment at VIA rail Canada. Transportation Research B, 36, 755–778.
Peeters, M., & Kroon, L. G. (2008). Circulation of railway rolling stock: A branch-and-price approach. Computers & Operations Research, 35(2), 538–556.
Author information
Authors and Affiliations
Corresponding author
Additional information
G. Maróti was partially supported by the Future and Emerging Technologies train unit of EC (IST priority—6th FP), under contract no. FP6-021235-2 (project ARRIVAL).
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Budai, G., Maróti, G., Dekker, R. et al. Rescheduling in passenger railways: the rolling stock rebalancing problem. J Sched 13, 281–297 (2010). https://doi.org/10.1007/s10951-009-0133-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-009-0133-9