Top

Published in:

2018 | OriginalPaper | Chapter

5. Robust Train Timetabling

Authors : Valentina Cacchiani, Paolo Toth

Published in: Handbook of Optimization in the Railway Industry

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Nowadays railway systems are highly affected by disturbances, occurring in daily operations, and causing train delays and passenger inconvenience. Not only they negatively affect the passengers satisfaction, but they also cause additional operational costs, since the planned schedule needs to be modified in real-time. Train timetabling is a particularly critical phase in railway system management, since, in real-time operations, all the changes applied to the planned timetable impact on platform assignment, rolling stock circulation and crew scheduling. Therefore, in the strategic planning, it is an important issue to determine robust timetables, i.e., timetables that “perform well” under disturbances, avoiding delay propagation as much as possible. In this chapter, we present state-of-the-art methods that achieve robust timetables, and discuss their advantages and drawbacks.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Freight Train Routing

next chapter Modern Challenges in Timetabling

Bauer R, Schöbel A (2014) Rules of thumb: practical online-strategies for delay management. Public Transp 6(1–2):85–105. ISSN: 1866-749X. https://doi.org/10.1007/s12469-013-0082-8 (cited on page 110)CrossRef

Ben-Tal A, Nemirovski A (1998) Robust convex optimization. Math Oper Res 23(4):769–805. https://doi.org/10.1287/moor.23.4.769 (cited on page 98)CrossRef

Ben-Tal A, Nemirovski A (2000) Robust solutions of linear programming problems contaminated with uncertain data. Math Program 88(3):411–424. https://doi.org/10.1007/PL00011380 (cited on page 98)CrossRef

Ben-Tal A, Nemirovski A (2002) Robust optimization–methodology and applications. Math Program 92(3):453–480. https://doi.org/10.1007/s101070100286 (cited on page 98)CrossRef

Bertsimas D, Sim M (2003) Robust discrete optimization and network flows. Math Program 98(1):49–71. https://doi.org/10.1007/s10107-003-0396-4 (cited on page 98)CrossRef

Bertsimas D, Sim M (2004) The price of robustness. Oper Res 52(1):35–53. https://doi.org/10.1287/opre.1030.0065 (cited on page 98)CrossRef

Bešinović N, Goverde RMP, Quaglietta E, Roberti R (2016) An integrated micro-macro approach to robust railway timetabling. Transp Res B Methodol 87:14–32. https://doi.org/10.1016/j.trb.2016.02.004 (cited on page 109)CrossRef

Birge JR, Louveaux F (2011) Introduction to stochastic programming. Springer Science & Business Media, New York. https://doi.org/10.1007/978-1-461-40237-4 (cited on page 98)CrossRef

Cacchiani V, Toth P (2012) Nominal and robust train timetabling problems. Eur J Oper Res 219(3):727–737. Feature clusters. ISSN: 0377-2217. https://doi.org/10.1016/j.ejor.2011.11.003 (cited on pages 94, 95)

10.

Cacchiani V, Caprara A, Toth P (2010) Scheduling extra freight trains on railway networks. Transp Res B Methodol 44(2):215–231. https://doi.org/10.1016/j.trb.2009.07.007 (cited on page 106)CrossRef

11.

Cacchiani V, Caprara A, Fischetti M (2012) A Lagrangian heuristic for robustness, with an application to train timetabling. Transp Sci 46(1):124–133. https://doi.org/10.1287/trsc.1110.0378 (cited on pages 96, 97, 106, 107, 108, 109, 110, 111, 112)

12.

Cacchiani V, Galli L, Toth P (2015) A tutorial on non-periodic train timetabling and platforming problems. EURO J Transp Logist 4(3):285–320. https://doi.org/10.1007/s13676-014-0046-4 (cited on page 95)CrossRef

13.

Caprara A, Fischetti M, Toth P (2002) Modeling and solving the train timetabling problem. Oper Res 50(5):851–861. https://doi.org/10.1287/opre50.5.851.362 (cited on pages 96, 106, 108)

14.

Caprara A, Galli L, Stiller S, Toth P (2014) Delayrobust event scheduling. Oper Res 62(2):274–283. https://doi.org/10.1287/opre.2014.1259 (cited on page 102)CrossRef

15.

Cicerone S, D’Angelo G, Di Stefano G, Frigioni D, Navarra A (2009) Recoverable robust timetabling for single delay: complexity and polynomial algorithms for special cases. J Comb Optim 18(3):229–257. https://doi.org/10.1007/s10878-009-9247-4 (cited on page 102)CrossRef

16.

Cicerone S, D’Angelo G, Di Stefano G, Frigioni D, Navarra A, Schachtebeck M, Schöbel A (2009) Recoverable robustness in shunting and timetabling. In: Ahuja RK, Möhring RH, Zaroliagis CD (eds) Robust and online largescale optimization. Springer, Berlin, pp 28–60. https://doi.org/10.1007/978-3-642-05465-5_2 (cited on pages 102, 111)

17.

D’Angelo G, Di Stefano G, Navarra A (2009) Evaluation of recoverable-robust timetables on tree networks. In: Fiala J, Kratochvíl J, Miller M (eds) Combinatorial algorithms. Springer, Berlin, pp 24–35. https://doi.org/10.1007/978-3-642-10217-2_6 (cited on page 102)CrossRef

18.

Ehrgott M (2006) Multicriteria optimization. Springer Science & Business Media, Berlin. https://doi.org/10.1007/3-540-27659-9 (cited on page 106)

19.

Fischetti M, Monaci M (2009) Light robustness. In: Ahuja RK, Möhring RH, Zaroliagis CD (eds) Robust and online large-scale optimization. Springer, Berlin, pp 61–84. https://doi.org/10.1007/978-3-642-05465-5_3 (cited on pages 98, 104)

20.

Fischetti M, Salvagnin D, Zanette A (2009) Fast approaches to improve the robustness of a railway timetable. Transp Sci 43(3):321–335. https://doi.org/10.1287/trsc1090.0264 (cited on pages 97, 100, 104, 106, 109, 110, 111)

21.

Goerigk M, Schöbel A (2010) An empirical analysis of robustness concepts for timetabling. In: Proceedings of the 10th workshop on algorithmic approaches for transportation modelling optimization, and systems (ATMOS 2010). OpenAccess series in informatics (OASIcs), vol 14. Schloss Dagstuhl, Wadern, pp 100–113. https://doi.org/10.4230/OASIcs.ATMOS.2010.100 (cited on page 103)

22.

Goerigk M, Schöbel A (2014) Recovery-to-optimality: a new two-stage approach to robustness with an application to aperiodic timetabling. Comput Oper Res 52:1–15. https://doi.org/101016/j.cor.2014.06.025 (cited on pages 103, 104, 111)

23.

Goerigk M, Schmidt M, Schöbel A, Knoth M, Müller-Hannemann M (2013) The price of strict and light robustness in timetable information. Transp Sci 48(2):225–242. https://doi.org/10.1287/trsc.2013.0470 (cited on page 105)CrossRef

24.

Goverde RMP, Bešinović N, Binder A, Cacchiani V, Quaglietta E, Roberti R, Toth P (2016) A three-level framework for performance-based railway timetabling. Transp Res C: Emerg Technol 67:62–83. https://doi.org/10.1016/j.trc.2016.02.004 (cited on page 112)CrossRef

25.

Kroon L, Maróti G, Helmrich MR, Vromans M, Dekker R (2008) Stochastic improvement of cyclic railway timetables. Transp Res B Methodol 42(6):553–570. https://doi.org/10.1016/j.trb.2007.11.002 (cited on pages 97, 98, 101, 105, 108, 111)

26.

Liebchen C (2008) The first optimized railway timetable in practice. Transp Sci 42(4):420–435. https://doi.org/10.1287/trsc1080.0240 (cited on page 95)CrossRef

27.

Liebchen C, Lübbecke M, Möhring R, Stiller S (2009) The concept of recoverable robustness, linear programming recovery and railway applications. In: Ahuja RK, Möhring RH, Zaroliagis CD (eds) Robust and online large-scale optimization. Springer, Berlin, pp 1–27. https://doi.org/10.1007/978-3-642-05465-5_1 (cited on pages 101, 103, 111)

28.

Liebchen C, Schachtebeck M, Schöbel A, Stiller S, Prigge A (2010) Computing delay resistant railway timetables. Comput Oper Res 37(5):857–868. https://doi.org/10.1016/j.cor.2009.03.022 (cited on pages 105, 110)

29.

Lusby RM, Larsen J, Ehrgott M, Ryan D (2011) Railway track allocation: models and methods. OR Spectr 33(4):843–883. https://doi.org/10.1007/s00291-009-0189-0 (cited on page 95)CrossRef

30.

Meng L, Zhou X (2011) Robust single-track train dispatching model under a dynamic and stochastic environment: a scenario-based rolling horizon solution approach. Transp Res B Methodol 45(7):1080–1102. https://doi.org/10.1016/j.trb.2011.05.001 (cited on page 100)CrossRef

31.

Schachtebeck M, Schöbel A (2010) To wait or not to wait-and who goes first? Delay management with priority decisions. Transp Sci 44(3):307–321. https://doi.org/10.1287/trsc.1100.0318 (cited on page 110)CrossRef

32.

Schlechte T, Borndörfer R (2010) Balancing efficiency and robustness–a bi-criteria optimization approach to railway track allocation. In: Ehrgott M, Naujoks B, Stewart TJ, Wallenius J (eds) Multiple criteria decision making for sustainable energy and transportation systems. Springer, Berlin, pp 105–116. https://doi.org/10.1007/978-3-642-04045-0_9 (cited on page 109)

33.

Schöbel A (2014) Generalized light robustness and the trade-off between robustness and nominal quality. Math Meth Oper Res 80(2):161–191. https://doi.org/10.1007/s0018601404749 (cited on page 106)CrossRef

34.

Schöbel A, Kratz A (2009) A bicriteria approach for robust timetabling. In: Ahuja RK, Möhring RH, Zaroliagis CD (eds) Robust and online large-scale optimization. Springer, Berlin, pp 119–144. https://doi.org/10.1007/978-3-642-05465-5_5 (cited on page 109)

35.

Serafini P, Ukovich W (1989) A mathematical model for periodic scheduling problems. SIAM J Discret Math 2(4):550–581. ISSN: 0895-4801. https://doi.org/10.1137/0402049 (cited on page 95)CrossRef

36.

Soyster AL (1973) Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper Res 21(5):1154–1157. https://doi.org/10.1287/opre.21.5.1154 (cited on pages 98)

37.

Website of the ARRIVAL EU Project (June 2017). https://arrival.cti.gr (cited on page 111)

38.

Website of the OnTime EU Project (June 2017). https://ontime-project.eu (cited on pages 111, 112)

Title: Robust Train Timetabling
Authors: Valentina Cacchiani
Paolo Toth
Publisher: Springer International Publishing
Book: Handbook of Optimization in the Railway Industry
Print ISBN: 978-3-319-72152-1

Electronic ISBN: 978-3-319-72153-8

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-72153-8_5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"