Abstract
Delay management models determine which connections should be maintained in case of a delayed feeder train. Recently, delay management models are developed that take into account that passengers will adjust their routes when they miss a connection. However, for large-scale real-world instances, these extended models become too large to be solved with standard integer programming techniques. We therefore develop several heuristics to tackle these larger instances. The dispatching rules that are used in practice are our first heuristic. Our second heuristic applies the classical delay management model without passenger rerouting. Finally, the third heuristic updates the parameters of the classical model iteratively. We compare the quality of these heuristic solution methods on real-life instances from Netherlands Railways. In this experimental study, we show that our iterative heuristic can solve large-scale real-world instances within a short computation time. Furthermore, the solutions obtained by this iterative heuristic are of good quality.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Bauer R, Schöbel A (2011) Rules of thumb—practical online-strategies for delay management. Technical report, Institut für Numerische und Angewandte Mathematik
Berger A, Blaar C, Gebhardt A, Müller-Hannemann M, Schnee M (2011a) Passenger flow-oriented train disposition. In: Demetrescu C, Halldórsson MM (eds) Algorithms—ESA 2011. Lecture notes in computer science, vol 6942. Springer, Berlin, pp 227–238. ISBN 978-3-642-23718-8
Berger A, Hoffmann R, Lorenz U, Stiller S (2011b) Online railway delay management: hardness, simulation and computation. Simulation 87(7):616–629
Corman F, D’Ariano A, Pacciarelli D, Pranzo M (2012) Bi-objective conflict detection and resolution in railway traffic management. Transp Res Part C 20(1):79–94
D’Ariano A, Corman F, Pacciarelli D, Pranzo M (2008) Reordering and local rerouting strategies to manage train traffic in real time. Transp Sci 42(4):405–419
Dollevoet T, Schmidt M, Schöbel A (2011) Delay management including capacities of stations. In: Caprara A, Kontogiannis S (eds) 11th workshop on algorithmic approaches for transportation modelling, optimization, and systems. OpenAccess series in informatics (OASIcs), vol 20. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, pp 88–99
Dollevoet T, Huisman D, Schmidt M, Schöbel A (2012) Delay management with rerouting of passengers. Transp Sci 46(1):74–89
Gatto M, Jacob R, Peeters L, Schöbel A (2005) The computational complexity of delay management. In: Graph-theoretic concepts in computer science: 31st international workshop (WG 2005). Lecture notes in computer science, vol 3787, pp 227–238
Ginkel A, Schöbel A (2007) To wait or not to wait? The bicriteria delay management problem in public transportation. Transp Sci 41(4):527–538
Kliewer N, Suhl L (2011) A note on the online nature of the railway delay management problem. Networks 57(1):28–37
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
Schöbel A (2001) A model for the delay management problem based on mixed-integer programming. Electron Notes Theor Comput Sci 50(1):1–10
Schöbel A (2007) Integer programming approaches for solving the delay management problem. In: Algorithmic methods for railway optimization. Lecture notes in computer science, vol 4359. Springer, Berlin, pp 145–170
Schöbel A (2009) Capacity constraints in delay management. Public Transp 1(2):135–154
Suhl L, Biederbick C, Kliewer N (2001) Design of customer-oriented dispatching support for railways. In: Voss S, Daduna JR (eds) Computer-aided scheduling of public transport. Lecture notes in economics and mathematical systems, vol 505. Springer, Berlin, pp 365–386. ISBN 978-3-540-42243-3
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Dollevoet, T., Huisman, D. Fast heuristics for delay management with passenger rerouting. Public Transp 6, 67–84 (2014). https://doi.org/10.1007/s12469-013-0076-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12469-013-0076-6