Abstract
Efficiently coordinating the movement of trains on a railway network is a central part of the planning process for a railway company. This paper reviews models and methods that have been proposed in the literature to assist planners in finding train routes. Since the problem of routing trains on a railway network entails allocating the track capacity of the network (or part thereof) over time in a conflict-free manner, all studies that model railway track allocation in some capacity are considered relevant. We hence survey work on the train timetabling, train dispatching, train platforming, and train routing problems, group them by railway network type, and discuss track allocation from a strategic, tactical, and operational level.
Similar content being viewed by others
References
Adenso-Diaź B, Olivia González M, González-Torre P (1999) On-line timetable re-scheduling in regional train services. Transp Res B 33: 387–398
Albrecht T (2009) Automated timetable design for demand-oriented service on surburban railways. Public Transp 1(1): 5–20
Assad AA (1980) Modelling of rail networks: toward a routing/makeup model. Transp Sci Part B 14: 101–114
Billionnet A (2003) Using integer programming to solve the train-platforming problem. Transp Sci 37(2): 213–222
Borndörfer R, Schlechte T (2007a) Models for railway track allocation. Technical Report 07–02, Konrad-Zuse-Zentrum für Informationstechnik Berlin
Borndörfer R, Schlechte T (2007b) Solving railway track allocation problems. Technical Report 07–20, Konrad-Zuse-Zentrum für Informationstechnik Berlin
Borndörfer R, Grötschel M, Lukac S, Mitusch M, Schlechte T, Schultz S, Tanner A (2005) An auctioning approach to railway slot allocation. Technical Report 05–45, Konrad-Zuse-Zentrum für Informationstechnik Berlin
Brännlund U, Lindberg PO, Nõu A, Nilsson JE (1998) Railway timetabling using lagrangian relaxation. Transp Sci 32(4): 358–369
Burkolter D (2005) Capacity of railways in station areas using petri nets. PhD thesis, Swiss Federal Institute of Technology Zurich
Bussieck MR, Winter T, Zimmerman UT (1997) Discrete optimization in public rail trainsport. Math Program 79: 415–444
Cacchiani V, Caprara A, Toth P (2008) A column generation approach to train timetabling on a corridor. 4OR 6: 125–142
Cai X, Goh CJ (1994) A fast heuristic for the train scheduling problem. Comput Oper Res 21(5): 499–510
Cai X, Goh CJ, Mees AI (1998) Greedy heuristics for rapid scheduling of trains on a single track. IIE Trans 30: 481–493
Caimi G, Burkolter D, Herrmann T (2005) Finding delay-tolerant train routings through stations. In: Fleuren H (eds) Operations research proceedings 2004: selected papers of the annual international conference of the German operations research society (GOR) jointly organized with the Netherlands society. Springer, Berlin, pp 136–143
Caprara A, Fischetti M, Toth P (2002) Modeling and solving the train timetabling problem. Oper Res 50(5): 851–861
Caprara A, Monaci M, Toth P, Guida PL (2006) A lagrangian heuristic alogorithn for a real-world train timetabling problem. Discret Appl Math 154: 738–753
Caprara A, Galli L, Toth P (2007a) Solution of the train platforming problem. In: Liebchen C, Ahuja RK, Mesa JA (eds) ATMOS 2007—7th workshop on algorithmic approaches for transportation modeling, optimization, and systems, Dagstuhl, Germany. Internationales Begegnungs und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany
Caprara A, Kroon LG, Monaci M, Peeters M, Toth P (2007) Passenger railway optimization. In: Barnhart C, Laporte G (eds) Handbooks in operations research and management science, vol 14, chap 3. Elsevier, Amsterdam, pp 129–187
Carey M (1994a) Extending a train pathing model from one-way to two-way track. Transp Res Part B 28B(5): 395–400
Carey M (1994b) A model and strategy for train pathing with choice of lines, platforms, and routes. Transp Res Part B 28B: 333–353
Carey M, Carville S (2003) Scheduling and platforming trains at busy complex stations. Transp Res Part A 37: 195–224
Carey M, Crawford I (2007) Scheduling trains on a network of busy complex stations. Transp Sci Part B 41: 159–178
Carey M, Lockwood D (1995) A model, algorithms and strategy for train pathing. J Oper Res Soc 46(8): 988–1005
Cordeau J, Toth P, Vigo D (1998) A survey of optimization models for train routing and scheduling. Transp Sci 32(4): 380–400
Cornelsen S, Di Stefano G (2007) Track assignment. J Discret algorithms 5(2): 250–261
D’Ariano A, Pacciarelli D, Pranzo M (2007) A branch-and-bound algorithm for scheduling trains in a railway network. Eur J Oper Res 183: 643–657
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
De Luca Cardillo D, Mione N (1998) k L-list τ colouring of graphs. Eur J Oper Res 106: 160–164
Delorme X (2003) Modélisation et résolution de problèmes liés à l’exploitation d’infrastructures ferroviaires. PhD thesis, Université de Valenciennes et du Hainaut Cambrésis
Delorme X, Rodriguez J, Gandibleux X (2001) Heuristics for railway infrastructure saturation. Electron Notes Theor Comput Sci 50(1): 39–53
Delorme X, Gandibleux X, Rodriguez J (2004) GRASP for set packing problems. Eur J Oper Res 153(3): 564–580
Dorfman MJ, Medanic J (2004) Scheduling trains on a railway network using a discrete event model of railway traffic. Transp Res Part B 38(1): 81–98
Fischetti M, Salvagnin D, Zanette A (2009) Fast approaches to improve the robustness of a railway timetable. Transp Sci 43: 321–335
Freling R, Lentink RM, Kroon LG, Huisman D (2005) Shunting of passenger train units in a railway station. Transp Sci 39(2): 261–272
Fuchsberger M (2007) Solving the train scheduling problem in a main station area via a resource constrained space–time integer multi-commodity flow. Master’s thesis, Institute for Operations Research ETH Zurich
Gandibleux X, Delorme X, T’Kindt V (2004) Ant colony optimisation algorithm for the set packing problem. In: ANTS Workshop, pp 49–60
Gandibleux X, Jorge J, Angibaud S, Delorme X, Rodriguez J (2005) An ant colony optimization inspired algorithm for the set packing problem with application to railway infrastructure. In: Proceedings of the sixth metaheuristics international conference (MIC2005), pp 390–396
Herrman TM (2006) Stability of timetables and train routings through station regions. PhD thesis, Swiss Federal Insitute of Technology Zurich
Higgins A, Kozan E, Ferreira L (1996) Optimal scheduling of trains on a single line track. Transp Res Part B 30B(2): 147–161
Higgins A, Kozan E, Ferreira L (1997) Heuristic techniques for single line train scheduling. J Heuristics 3: 43–62
Hooghiemstra JS, Kroon LG, Odijk MA, Salomon M, Zwaneveld PJ (1999) Decision support systems support the search for win–win solutions in railway network design. Interfaces 29(2): 15–32
Huisman D, Kroon LG, Lentik RM, Vromans MJCM (2005) Operations research in passenger railway transportation. Technical report, Erasmus Research Institute of Management
Jovanović D, Harker PT (1991) Tactical scheduling of rail operations: the scan i system. Transp Sci 25(1): 46–64
Kraay D, Harker PT, Chen B (1991) Optimal pacing of trains in freight railroads: model formulation and solution. Oper Res 39(1): 82–99
Kroon LG, Peeters L (2003) A variable trip time model for cyclic railway timetabling. Transp Sci 37: 198–212
Kroon LG, Lentink RM, Schrijver A (2008) Shunting of passenger train units. Transp Sci 42(4): 436–449
Liebchen C (2003) Finding short integral cycle bases for cyclic timetabling. Technical Report 12, Technische Universität Berlin, Institut fur Mathematik
Liebchen C (2006) Periodic timetable optimization in public transportation. PhD thesis, Technische Universität Berlin
Liebchen C, Möhring R (2004) The modelling power of the periodic event scheduling problem: railway timetables—and beyond. Technical Report 2004/20, Technische Universität Berlin, Institut fur Mathematik
Liebchen C, Peeters L (2002) On cyclic timetabling and cycles in graphs. Technical Report 761/2002, Technische Universität Berlin, Institut fur Mathematik
Liebchen C, Stiller S (2009) Delay resistant timetabling. Public Transp 1(1): 55–72
Liebchen C, Proksch M, Wagner FH (2008) Performance of algorithms for periodic timetable optimization. In: Hickman M, Mirchandani P, Voss S (eds) Computed-aided systems in transport (CASPT2004). Springer, Berlin, pp 00–00
Lindner T (2000) Train schedule optimization in public rail transportation. PhD thesis, Technical University of Braunschweig
Lusby RM (2008) Optimization methods for routing trains through railway junctions. PhD thesis, The University of Auckland
Mascis A, Pacciarelli D (2000) Machine scheduling via alternative graphs. Technical Report DIA-46-2000, Dipartimento di Informatica e Automazione, Universitá Roma Tre, Roma, Italy
Mascis A, Pacciarelli D (2002) Job shop scheduling with blocking and no-wait constraints. Eur J Oper Res 143(3): 498–517
Nachtigall K (1996) Cutting planes for a polyhedron associated with a periodic network. Technical Report IB 112-96/17, Deutsche Forschungsanstalt für Luft- und Raumfahrt e.V
Nachtigall K (1998) Periodic network optimization and fixed interval timetables. Habilitation Thesis
Nachtigall K, Voget S (1996) A genetic algorithm approach to periodic railway synchronization. Comput Oper Res 23(5): 453–463
Odijk MA (1996) A constraint generation algorithm for the construction of periodic timetables. Transp Res B 30(6): 455–464
Oliveira O, Smith BM (2000) A job shop scheduling model for the single track-railway timetabling problem. Technical Report 2000.21, University of Leeds
Pachl J (2004) Systemtechnik des Schienenverkehrs (in German). B.G. Teubner, Stuttgart
Peeters L (2003) Cyclic railway timetable optimization. PhD thesis, Erasmus Research Institute of Management
Rezanova N, Ryan DM (2009) The train driver recover problem—a set partitioning based model and solution method. Comput Oper Res (forthcoming). doi:10.1016/j.cor.2009.03.023
Rodriguez J (2007) A constraint programming model for real-time trains scheduling at junctions. Transp Res Part B 41(2): 231–245
Rodriguez J, Kermad L (1998) Constraint programming for real-time train circulation management problems in railway nodes. In: Proceedings of the international conference on computer aided design, manufacture and operation in the railway and other advanced mass transit systems, pp 597–606
Rodriguez J, Delorme X, Gandibleux X (2002) Railway infrastructure saturation using constraint programming approach. In: Computers in railways VIII. WIT Press, Lemmos, Greece, pp 807–816
Roy B, Sussman B (1964) Les problèm d’ordonnancement avec contraintes disjonctives. Note ds no. 9 bis. SEMA, Paris
Şahin İ (1999) Railway traffic control and train scheduling based on inter-train conflict management. Transp Res Part B 33: 511–534
Sauder R, Westerman WM (1983) Computer aided train dispatching: decision support through optimization. Interfaces 6: 24–37
Schöbel A (2009) Capacity constraints in delay management. Public Transp 1(2): 135–154
Schrijver A, Steenbeek A (1994) Timetable construction for railned (in Dutch). Technical report, C.W.I. Center for Mathematics and Computer Science, Amsterdam
Serafini P, Ukovich W (1989) A mathematical model for periodic scheduling problems. Soc Ind Appl Math J Discret Math 2(4): 550–581
Szpigel B (1973) Optimal train scheduling on a single line railway. Oper Res 72: 344–351
Törnquist J (2005) Computer-based decision support for railway traffic scheduling and dispatching: a review of models and algorithms. In: ATMOS2005 (algorithmic methods and models for optimization of railways), Palma de Mallorca, Spain, October 2005. Dagstuhl Research Online Publication Server (DROPS)
Törnquist J, Persson JA (2007) N-tracked railway traffic rescheduling during disturbances. Transp Res Part B 41(3): 342–362
Vaidyanathan B, Ahuja RK, Orlin JB (2008) The locomotive routing problem. Transp Sci 42: 492–507
Vansteenwegen P, Van Oudheusden D (2006) Develo** railway timetable which guarantee a better service. Eur J Oper Res 173: 337–350
Velásquez R, Ehrgott M, Ryan D, Schöbel A (2005) A set packing approach to routing trains through railway stations. In: Proceedings of the 40th annual conference of the operational research society of New Zealand, pp 305–314
Walker CG, Snowden JN, Ryan DM (2005) Simultaneous disruption recovery of a train timetable and crew roster in real time. Comput Oper Res 32(8): 2077–2094
Wong RCW, Yuen WY, KwokWah Fung T, Leung JMY (2008) Timetable synchronization for rail mass transit. Transp Sci 42: 57–69
Zwaneveld PJ (1997) Routing of trains and allocation of passenger lines. PhD thesis, Rotterdam School of Management, TRAIL Research School
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(3): 181–194
Zwaneveld PJ, Kroon LG, Romeijn HE (1997) Routing trains through railway stations: complexity issues. Eur J Oper Res 98: 485–498
Zwaneveld PJ, Kroon LG, van Hoesel SPM (2001) Routing trains through a railway station based on a node packing model. Eur J Oper Res 128: 14–33
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lusby, R.M., Larsen, J., Ehrgott, M. et al. Railway track allocation: models and methods. OR Spectrum 33, 843–883 (2011). https://doi.org/10.1007/s00291-009-0189-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00291-009-0189-0