Abstract
This chapter shows a successful approach how to model and optimize rolling stock rotations that are required for the operation of a passenger timetable. The underlying mathematical optimization problem is described in detail and solved by Rotation Optimizer for Railways (ROTOR), i.e., a complex optimization algorithm based on linear programming and combinatorial methods. ROTOR is used by DB Fernverkehr AG (DBF) in order to optimize intercity express (ICE) rotations for the European high-speed network. We focus on main modeling and solving components, i.e. a hypergraph model and a coarse-to-fine column generation approach. Finally, the chapter concludes with a complex industrial re-optimization application showing the effectiveness of the approach for real world challenges.
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
Similar content being viewed by others
Notes
- 1.
A rolling stock rotation plan (as we deal with) can be seen as a rolling stock roster.
- 2.
- 3.
In order to decrease confusion: The blue circle with the lowest y-coordinate in a natural Cartesian system of coordinates for Fig. 10.2 is meant.
- 4.
We do not provide the detailed changes of departures and arrivals here. The important aspect is that the eight lines illustrated in Fig. 10.3 were directly affected by the 60 min increased driving time.
- 5.
The “W” indicates that the ICE-W vehicles are equipped with “Wirbelstrombremsen”, i.e., eddy current brakes.
References
Ahuja RK, Liu J, Orlin JB, Sharma D, Shughart LA (2005) Solving real-life locomotive-scheduling problems. Transp Sci 39:503–517. ISSN: 1526-5447. https://doi.org/10.1287/trsc.1050.0115 (cited on page 216)
Ahuja RK, Möhring RH, Zaroliagis CD (eds) (2009) Robust and online large-scale optimization: models and techniques for transportation systems. Lecture notes in computer science, vol 5868. Springer, Berlin, Heidelberg. ISBN: 978-3-642-05464-8. https://doi.org/10.1007/978-3-642-05465-5 (cited on page 217)
Anderegg L, Eidenbenz S, Gantenbein M, Stamm C et al (2003) Train routing algorithms: concepts, design choices, and practical considerations. In: Proceedings of the 5th workshop on algorithm engineering and experiments (ALENEX). SIAM, Philadelphia, PA, pp 106–118 (cited on page 216)
Bauarbeiten: ICE-Strecke von Frankfurt nach Köln zeitweise gesperrt. German. Frankfurter Allgemeine Zeitung (FAZ) (2015). faz.net/-gzg-7zfb7 (visited on 09/11/2017) (cited on page 235)
Behrendt S (2008) Dienstreihenfolgeplanung mit ganzzahliger Optimierung. German. Diplomarbeit, Technische Universität Berlin (cited on page 216)
Borndörfer R, Reuther M, Schlechte T (2014) A coarse-to-fine approach to the railway rolling stock rotation problem. In: Funke S, Mihalák M (eds) 14th workshop on algorithmic approaches for transportation modelling, optimization, and systems (ATMOS 2014). OpenAccess series in informatics (OASIcs), vol 42. Schloss Dagstuhl-Leibniz-Zentrum fúr Informatik, pp 79–91. ISBN: 978-3-939897-75-0. https://doi.org/10.4230/OASIcs.ATMOS.2014.79 (cited on page 226)
Cacchiani V, Caprara A, Toth P (2012) A fast heuristic algorithm for the train unit assignment problem. In: Delling D, Liberti L (eds) 12th workshop on algorithmic approaches for transportation modelling, optimization, and systems, ATMOS 2012. OpenAccess series in informatics (OASIcs), vol 25. Schloss Dagstuhl, Wadern, pp 1–9. ISBN: 978-3-939897-45-3. https://doi.org/10.4230/OASIcs.ATMOS.2012.1 (cited on page 217)
Cordeau J-F, Soumis F, Desrosiers J (2001) Simultaneous assignment of locomotives and cars to passenger trains. Oper Res 49:531–548. ISSN: 0030-364X. https://doi.org/10.1287/opre.49.4.531.11226 (cited on page 216)
DB Fernverkehr AG (2015) German intercity-express (ICE) lines. http:bahn.de (visited on 09/01/2015) (Not cited.)
Euler R, Gamrath G (2017) Website of hydraw – hy(pergraph)draw(ing). http:hydraw.zib.de (cited on page 215)
Fioole P-J, Kroon L, Maróti G, Schrijver A (2006) A rolling stock circulation model for combining and splitting of passenger trains. Eur J Oper Res 174(2):1281–1297. ISSN: 0377-2217. https://doi.org/10.1016/j.ejor.2005.03.032 (cited on page 216)
Giacco GL (2014) Rolling stock rostering and maintenance scheduling optimization. PhD thesis, Roma Tre University, HDL: 2307/4429 (cited on page 217)
Giacco GL, Carillo D, D’Ariano A, Pacciarelli D, Marín A (2014) Short-term rail rolling stock rostering and maintenance scheduling. In: Transportation research procedia. 17th EURO working group on transportation, EWGT2014, Sevilla, vol 3, pp 651–659. ISSN: 2352–1465. https://doi.org/10.1016/j.trpro.2014.10.044 (cited on page 217)
Giacco GL, D’Ariano A, Pacciarelli D (2014) Rolling stock rostering optimization under maintenance constraints. J Intell Transp Syst 18(1):95–105. https://doi.org/10.1080/15472450.2013.801712 (cited on pages 217)
Haahr J (2015) Reactive robustness and integrated approaches for railway optimization problems. PhD thesis, DTU Management Engineering (cited on page 217)
Haahr JT, Lusby RM, Larsen J, Pisinger D (2014) A branch-and-price framework for railway rolling stock rescheduling during disruptions. Technical report, DTU Management Engineering (cited on page 217)
Haahr, J, Wagenaar J, Veelenturf L, Kroon L (2015) A comparison of two exact methods for passenger railway rolling stock (re)scheduling. Technical report ERS-2015-007-LIS, ERIM report series research in management, HDL: 1765/78317 (cited on page 217)
Kuhn HW (1955) The Hungarian method for the assignment problem. Nav Res Logist Q 2(1–2):83–97. ISSN: 1931–9193. https://doi.org/10.1002/nav.3800020109 (cited on page 234)
Löbel A (1997) Optimal vehicle scheduling in public transit. PhD thesis, TU Berlin. URN: urn:nbn:de:0297 - zib - 10169 (cited on pages 216, 228)
Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper Res 53(6):1007–1023. https://doi.org/10.1287/opre.1050.0234 (cited on page 224)
Maráti G, Kroon L (2005) Maintenance routing for train units: the transition model. Transp Sci 39:518–525. ISSN: 1526–5447. https://doi.org/10.1287/trsc.1050.0116 (cited on page 216)
Maróti G, Kroon LG (2007) Maintenance routing for train units: the interchange model. Comput Oper Res 34(4):1121–1140. https://doi.org/10.1016/j.cor.2005.05.026 (cited on page 216)
Mellouli T, Suhl L (2007) Rotation planning of locomotive and carriage groups with shared capacities. In: Geraets F, Kroon L, Schoebel A, Wagner D, Zaroliagis CD (eds) Algorithmic methods for railway optimization. Lecture notes in computer science, vol 4359. Springer, Berlin, Heidelberg, pp 276–294. ISBN: 978-3-540-74245-6. https://doi.org/10.1007/978-3-540-74247-0_15 (cited on page 216)
Nielsen LK (2011) Rolling stock rescheduling in passenger railways: applications in short-term planning and in disruption management. PhD thesis, Erasmus University Rotterdam, HDL: 1765/22444 (cited on page 217)
Reuther M (2017) Mathematical optimization of rolling stock rotations. PhD thesis, TU Berlin. https://doi.org/10.14279/depositonce-5865 (cited on pages 216, 218, 219, 220, 221, 222, 223, 224, 226, 228, 230, 232, 233, 234, 237, 239)
Schlechte T (2012) Railway track allocation - models and algorithms. PhD thesis, TU Berlin. https://doi.org/10.14279/depositonce-3124 (cited on page 214)
Thorlacius P, Larsen J, Laumanns M (2015) An integrated rolling stock planning model for the Copenhagen suburban passenger railway. J Rail Transp Plann Manag 5(4):240–262. ISSN: 2210-9706. https://doi.org/10.1016/j.jrtpm.2015.11.001 (cited on page 217)
Toth P, Vigo D (eds) (2014) Vehicle routing. Society for Industrial and Applied Mathematics, Philadelphia, PA. https://doi.org/10.1137/1.9781611973594 (cited on page 217)
Wagenaar J, Kroon L, Schmidt M (2016) Maintenance appointments in railway rolling stock rescheduling. Technical report ERS-2016-001-LIS, ERIM report series research in management Erasmus Research Institute of Management, HDL: 1765/79441 (cited on page 217)
Ziarati K, Soumis F, Desrosiers J, Gélinas S, Saintonge A (1997) Locomotive assignment with heterogeneous consists at CN North America. English. Eur J Oper Res 97(2):281–292. https://doi.org/10.1016/S0377-2217(96)00198-1 (cited on page 216)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this chapter
Cite this chapter
Reuther, M., Schlechte, T. (2018). Optimization of Rolling Stock Rotations. In: Borndörfer, R., Klug, T., Lamorgese, L., Mannino, C., Reuther, M., Schlechte, T. (eds) Handbook of Optimization in the Railway Industry. International Series in Operations Research & Management Science, vol 268. Springer, Cham. https://doi.org/10.1007/978-3-319-72153-8_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-72153-8_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-72152-1
Online ISBN: 978-3-319-72153-8
eBook Packages: Business and ManagementBusiness and Management (R0)