Railway timetabling: a maximum bottleneck path algorithm for finding an additional train path

  • PDF / 2,933,452 Bytes
  • 27 Pages / 439.37 x 666.142 pts Page_size
  • 26 Downloads / 185 Views

DOWNLOAD

REPORT


Railway timetabling: a maximum bottleneck path algorithm for finding an additional train path Fredrik Ljunggren1,2 · Kristian Persson1,3 · Anders Peterson1 · Christiane Schmidt1  Accepted: 31 August 2020 © The Author(s) 2020

Abstract We present an algorithm to insert a train path in an existing railway timetable close to operation, when we want to affect the existing (passenger) traffic as little as possible. Thus, we consider all other trains as fixed, and aim for a resulting train path that maximizes the bottleneck robustness, that is, a train path that maximizes the temporal distance to neighboring trains in the timetable. Our algorithm is based on a graph formulation of the problem and uses a variant of Dijkstra’s algorithm. We present an extensive experimental evaluation of our algorithm for the Swedish railway stretch from Malmö to Hallsberg. Moreover, we analyze the size of our constructed graph. Keywords  Railway timetabling · Robust train path · Bottleneck train path · Network algorithm · Freight transportation

This work subsumes the extended abstract that appeared in the Proceedings of the 14th International Conference on Advanced Systems in Public Transport and TransitData 2018 (Ljunggren et al. 2018). This research is a result of a collaboration between Linköping University and Trafikverket, and part of the EU H2020 Shift2Rail subprojects ARCC (Grant no. 730813) and FR8HUB (Grant no. 777402), and partially funded by Trafikverket (Dnr TRV 2016/75881, and Dnr TRV 2017/68055). The authors are grateful to Magnus Wahlborg (Trafikverket) for fruitful discussions and Martin Aronsson (SICS RISE) for timetable data. * Christiane Schmidt [email protected] Fredrik Ljunggren [email protected] Kristian Persson [email protected] Anders Peterson [email protected] 1

Communications and Transport Systems, ITN, Linköping University, Norrköping, Sweden

2

Present Address: Trafikverket, Stockholm, Sweden

3

Present Address: Sweco, Stockholm, Sweden



13

Vol.:(0123456789)



F. Ljunggren et al.

1 Introduction Over the last decades, both passenger traffic and freight traffic volumes in Sweden increased—from 1996 to 2016 by 82% (from about 7000 to 12800 passenger kilometers) and by 23% (from about 55 to about 68 million ton-kilometers), respectively, see (Grimm 2012; Trafikanalys 2017a, b). In all of Europe, freight traffic volume increases, and while the volume transported via railway within the EU has stagnated over the last years, see Eurostat (2017), the European commission sees the potential to revitalize rail freight (Commission of the European communities 2007): road congestion and the high oil price make road transport more expensive, railway transport is much safer, and increasing environmental concerns favor railway over road traffic. On the other hand, today’s wagon load traffic is ineffective and marshalling complicates the transport—these problems need to be alleviated to comply with a political vision of increased freight traffic volumes. One problem for the freight