Skip to main content
SpringerLink
Log in

Simultaneous optimization of delay management decisions and passenger routes

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

Abstract

The task of delay management is to decide whether connecting trains should wait for delayed feeder trains or depart on time in order to minimize the passengers’ delay. To estimate the effect of the wait-depart decisions on the travel times, most delay management models assume that passengers’ routes are predefined. However, in practice, passengers can adapt their routes to the wait-depart decisions and arising changes in the timetable. For this reason, in this paper we assume that passengers’ demand is given in form of pairs of origins and destinations (OD-pairs) and take wait-depart decisions and decisions on passengers’ routes simultaneously.

This approach, called delay management with re-routing, was introduced in Dollevoet et al. (Transp. Sci. 46(1):74–89, 2012) and we build our research upon the results obtained there. We show that the delay management problem with re-routing is strongly NP-hard even if there is only one OD-pair. Furthermore, we prove that even if there are only two OD-pairs, the problem cannot be approximated with constant approximation ratio unless P=NP. However, for the case of only one OD-pair we propose a polynomial-time algorithm. We show that our algorithm finds an optimal solution if there is no reasonably short route from origin to destination which requires a passenger to enter the same train twice. Otherwise, the solution found by the algorithm is a 2-approximation of an optimal solution and the estimated travel time is a lower bound on the objective value.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Algorithm 1
Fig. 2

Similar content being viewed by others

References

  • Adenso-Díaz B, Oliva González M, González-Torre P (1999) On-line timetable re-scheduling in regional train services. Transp Res, Part B, Methodol 33:387–398

    Article  Google Scholar 

  • Bauer R (2010) Theory and engineering for shortest paths and delay management. PhD thesis, Karlsruher Institut für Technologie

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

    Article  Google Scholar 

  • Borndörfer R, Grötschel M, Pfetsch ME (2008) Models for line planning in public transport. In: Hickman M, Mirchandani P, VoßS (eds) Computer-aided systems in public transport. Lecture notes in economics and mathematical systems, vol 600. Springer, Berlin, pp 363–378

    Chapter  Google Scholar 

  • Cordeau JF, Toth P, Vigo D (1998) A survey of optimization models for train routing and scheduling. Transp Sci 32(4):380–404

    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, Emerg Technol 20(1):79–94

    Article  Google Scholar 

  • de Vries R, De Schutter B, De Moor B (1998) On max-algebraic models for transportation networks. In: Proceedings of the international workshop on discrete event systems, Cagliari, Italy, pp 457–462

    Google Scholar 

  • Dollevoet T, Schmidt M, Schoebel A (2011) Delay management including capacities of stations. In: Caprara A, Kontogiannis S (eds) Proceedings of ATMOS, OASIcs, vol 20. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, pp 88–99

    Google Scholar 

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

    Article  Google Scholar 

  • Fischetti M, Monaci M (2009) Light robustness. In: Ahuja RK, Möhring R, Zaroliagis C (eds) Robust and online large-scale optimization. Lecture note on computer science, vol 5868. Springer, Berlin, pp 61–84

    Chapter  Google Scholar 

  • Fischetti M, Salvagnin S, Zanette A (2009) Fast approaches to improve the robustness of a railway timetable. Transp Sci 43:321–335

    Article  Google Scholar 

  • Garey M, Johnson D (1979) Computers and intractability—a guide to the theory of NP-completeness. Freeman, San Francisco

    Google Scholar 

  • Gatto M, Glaus B, Jacob R, Peeters L, Widmayer P (2004) Railway delay management: exploring its algorithmic complexity. In: Proceedings of 9th Scandinavian Workshop on Algorithm Theory (SWAT). Lecture notes in computer science, vol 3111. Springer, Berlin, pp 199–211

    Google Scholar 

  • Gatto M, Jacob R, Peeters L, Schöbel A (2005) The computational complexity of delay management. In: Kratsch D (ed) Graph-theoretic concepts in computer science: 31st international workshop (WG 2005). Lecture notes in computer science, vol 3787. Springer, Berlin

    Google Scholar 

  • Gatto M, Jacob R, Peeters L, Widmayer P (2007) On-line delay management on a single train line. In: Algorithmic methods for railway optimization. Lecture notes in computer science, vol 4359. Springer, Berlin, pp 306–320

    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 

  • Goerigk M, Schöbel A (2010) An empirical analysis of robustness concepts for timetabling. In: Erlebach T, Lübbecke M (eds) Proceedings of ATMOS, OASIcs, vol 14. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, pp 100–113

    Google Scholar 

  • Goerigk M, Knoth M, Müller-Hannemann M, Schmidt M, Schöbel A (2011) The price of robustness in timetable information. In: Caprara A, Kontogiannis S (eds) Proceedings of ATMOS, OASIcs, vol 20. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, pp 76–87

    Google Scholar 

  • Goverde R (1998) The max-plus algebra approach to railway timetable design. In: Computers in railways VI: proceedings of the 6th international conference on computer aided design, manufacture and operations in the railway and other advanced mass transit systems, Lisbon, pp 339–350

    Google Scholar 

  • Goverde RM (2007) Railway timetable stability analysis using max-plus system theory. Transp Res, Part B, Methodol 41(2):179–201

    Article  Google Scholar 

  • Heidergott B, de Vries R (2001) Towards a control theory for transportation networks. Discrete Event Dyn Syst 11:371–398

    Article  Google Scholar 

  • Heilporn G, Giovanni LD, Labbé M (2008) Optimization models for the single delay management problem in public transportation. Eur J Oper Res 189(3):762–774

    Article  Google Scholar 

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

  • Krumke SO, Thielen C, Zeck C (2011) Extensions to online delay management on a single train line: new bounds for delay minimization and profit maximization. Math Methods Oper Res 74(1):53–75

    Article  Google Scholar 

  • Liebchen C, Lübbecke M, Möhring RH, Stiller S (2009) The concept of recoverable robustness, linear programming recovery, and railway applications. In: Ahuja RK, Möhring R, Zaroliagis C (eds) Robust and online large-scale optimization. Lecture notes in computer science, vol 5868. Springer, Heidelberg, pp 1–27

    Chapter  Google Scholar 

  • Lusby R, Larsen J, Ehrgott M, Ryan D (2011) Railway track allocation: models and methods. OR Spektrum 33:843–883

    Article  Google Scholar 

  • Nachtigall K (1998) Periodic network optimization and fixed interval timetables. Deutsches Zentrum für Luft—und Raumfahrt. Institut für Flugführung, Braunschweig. Habilitationsschrift

    Google Scholar 

  • Nachtigall K, Jerosch K (2008) Simultaneous network line planning and traffic assignment. In: Fischetti M, Widmayer P (eds) Proceedings of ATMOS, OASICS, vol 9. Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Germany

    Google Scholar 

  • Odijk MA (1996) A constraint generation algorithm for the construction of periodic railway timetables. Transp Res, Part B, Methodol 30(6):455–464

    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 

  • Schmidt M (2012) Integrating routing decisions in network problems. PhD thesis, Universität Göttingen

  • Schmidt M, Schöbel A (2010) The complexity of integrating routing decisions in public transportation models. In: Erlebach T, Lübbecke M (eds) Proceedings of ATMOS, OASIcs, vol 14. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, pp 156–169

    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)

  • Schöbel A (2006) Optimization in public transportation. Stop location, delay management and tariff planning from a customer-oriented point of view. Optimization and its applications. Springer, New York

    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, Kratz A (2009) A bicriteria approach for robust timetabling? Lect Notes Comput Sci 5868:119–144

    Article  Google Scholar 

  • Schöbel A, Scholl S (2006) Line planning with minimal travel time. In: 5th workshop on algorithmic methods and models for optimization of railways, no. 06901 in dagstuhl seminar proceedings

    Google Scholar 

  • Serafini P, Ukovich W (1989) A mathematical model for periodic scheduling problems. SIAM J Discrete Math 2:550–581

    Article  Google Scholar 

  • Suhl L, Mellouli T (1999) Requirements for, and design of, an operations control system for railways. In: Computer-aided transit scheduling. Springer, Berlin

    Google Scholar 

  • Suhl L, Biederbick C, Kliewer N (2001a) Design of customer-oriented dispatching support for railways. In: VoßS, Daduna JR (eds) Computer-aided scheduling of public transport. Lecture notes in economics and mathematical systems, vol 505. Springer, Berlin, pp 365–386

    Chapter  Google Scholar 

  • Suhl L, Mellouli T, Biederbick C, Goecke J (2001b) Managing and preventing delays in railway traffic by simulation and optimization. In: Mathematical methods on optimization in transportation systems, pp 3–16

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute for Numerical and Applied Mathematics, University of Göttingen, Göttingen, Germany

    Marie Schmidt

Authors
  1. Marie Schmidt
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Marie Schmidt.

Additional information

This work was partially supported by the Marie Curie Action International Research Staff Exchange Scheme (IRSES) FP7-PEOPLE-2009-IRSES project OptALI under project ID 246647.

Electronic Supplementary Material

Below is the link to the electronic supplementary material.

(PDF 478 kB)

Rights and permissions

Reprints and permissions

About this article

Cite this article

Schmidt, M. Simultaneous optimization of delay management decisions and passenger routes. Public Transp 5, 125–147 (2013). https://doi.org/10.1007/s12469-013-0069-5

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12469-013-0069-5

Keywords

Search

Navigation