[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

Fast heuristics for delay management with passenger rerouting

  • Original Paper
  • Published:
Public Transport Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

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

    Chapter  Google Scholar 

  • Berger A, Hoffmann R, Lorenz U, Stiller S (2011b) Online railway delay management: hardness, simulation and computation. Simulation 87(7):616–629

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Google Scholar 

  • Dollevoet T, Huisman D, Schmidt M, Schöbel A (2012) Delay management with rerouting of passengers. Transp Sci 46(1):74–89

    Article  Google Scholar 

  • 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

    Chapter  Google Scholar 

  • 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

    Article  Google Scholar 

  • Kliewer N, Suhl L (2011) A note on the online nature of the railway delay management problem. Networks 57(1):28–37

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Chapter  Google Scholar 

  • Schöbel A (2009) Capacity constraints in delay management. Public Transp 1(2):135–154

    Article  Google Scholar 

  • 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

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Twan Dollevoet.

Rights and permissions

Reprints 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

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12469-013-0076-6

Keywords

Navigation