Abstract
We consider (small) disturbances of a railway system. In case of such delays, one has to decide if connecting trains should wait for delayed feeder trains or if they should depart on time, i.e. which connections should be maintained and which can be dropped. Finding such wait-depart decisions (minimizing e.g. the average delay of the passengers) is called the delay management problem. In the literature, the limited capacity of the tracks (meaning that no two trains can use the same piece of track at the same time) has so far been neglected in the delay management problem. In this paper we present models and first results integrating these important constraints. We develop algorithmic approaches that have been tested at a real-world example provided by Deutsche Bahn AG.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
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 33B:387–398
Billionnet A (2003) Using integer programming to solve the train platforming problem. Transp Sci 37(2):213–222
Bissantz N, Güttler S, Jacobs J, Kurby S, Schaer T, Schöbel A, Scholl S (2005) DisKon—Disposition und Konfliktlösungs-management für die beste Bahn. Eisenb Rundsch (ETR) 45(12):809–821 (in German)
Brucker P, Heitmann S, Knust S (2002) Scheduling railway traffic at a construction site. OR Spektr 24(1):19–30
Cicerone S, Di Stefano G, Schachtebeck M, Schöbel A (2008) Dynamic algorithms for recoverable robustness problems. In: Fischetti M, Widmayer P (eds) ATMOS 2008—8th workshop on algorithmic approaches for transportation modeling, optimization, and systems. Dagstuhl seminar proceedings
Cordeau J-F (1998) A survey of optimization models for train routing and scheduling. Transp Sci 32(4):380–404
De Giovanni L, Heilporn G, Labbé M (2008) Optimization models for the single delay management problem in public transportation. Eur J Oper Res 189(3):762–774
Gatto M, Glaus B, Jacob R, Peeters L, Widmayer P (2004) Railway delay management: Exploring its algorithmic complexity. In: Proc 9th Scandinavian workshop on algorithm theory (SWAT). LNCS, vol 3111, pp 199–211
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). LNCS, vol 3787
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
Heidergott B, de Vries R (2001) Towards a control theory for transportation networks. Discrete Event Dyn Syst 11:371–398
Jacobs J (2004) Reducing delays by means of computer-aided ‘on-the-spot’ rescheduling. In: Computers in railways (Comprail) IX, pp 603–612
Jobmann C, Schöbel A (2007) Approaches for solving delay management problems. Project work within DisKon
Nachtigall K (1998) Periodic network optimization and fixed interval timetables. Deutsches Zentrum für Luft- und Raumfahrt, Institut für Flugführung, Braunschweig. Habilitationsschrift
Norio T, Yoshiaki T, Noriyuki T, Chikara H, Kunimitsu M (2005) Train rescheduling algorithm which minimizes passengers dissatisfaction. In: LNAI, vol 3533. Springer, Berlin, pp 829–838
Pachl J (2000) Safe disposition and scheduling in railway operation. Signal + Draht 92(5):38–41
Ryan DM, Foster BA (1981) An integer programming approach to scheduling. In: Wren A (ed) Computer scheduling of public transport urban passenger vehicle and crew scheduling. North-Holland, Amsterdam, pp 269–280
Schachtebeck M, Schöbel A (2009) To wait or not to wait and who goes first? Delay management with priority decisions. Working paper
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) Customer-oriented optimization in public transportation. Optimization and its applications. Springer, New York
Schöbel A (2007) Integer programming approaches for solving the delay management problem. In: Algorithmic methods for railway optimization. LNCS, vol 4359. Springer, Berlin, pp 145–170
Szpigel B (1973) Optimal train scheduling on a single track railway. In: Ross M (ed) Operational research ’72: Proceedings of the 6th IFORS international conference on operational research. North-Holland, Amsterdam, pp 343–352
Törnquist J (2005) Computer-based decision support for railway traffic scheduling and dispatching: A review of models and algorithms. In: Proceedings of ATMOS 2005
Velasquez R, Ehrgott M, Ryan D, Schöbel A (2005) A set-packing aproach to routing trains through railway stations. In: 40th annual conference of the operations research society of New Zealand, pp 305–314
Wegele S, Schnieder E (2005) Dispatching of train operations using genetic algorithms. In: 1st international seminar on railway operations modelling and analysis, Delft
Zwaneveld PJ (1996) Routing trains through railway stations: Model formulation and algorithms. Transp Sci 30:181–194
Zwaneveld PJ, Kroon LG, Romeijn HE, Salomon M, Dauzere-Peres S, van Hoesel SPM, Ambergen HW (1996) Routing trains through railway stations: Model formulation and algorithms. Transp Sci 30(33):181–194
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was partially supported by the Klaproth-Stiftung and by the Future and Emerging Technologies Unit of EC (IST priority—6th FP), under contract no. FP6-021235-2 (project ARRIVAL).
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Schöbel, A. Capacity constraints in delay management. Public Transp 1, 135–154 (2009). https://doi.org/10.1007/s12469-009-0010-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12469-009-0010-0