Nominal and robust train timetabling problems.

*(English)*Zbl 1253.90108Summary: We survey the main studies dealing with the train timetabling problem in its nominal and robust versions. Roughly speaking, the nominal version of the problem amounts of determining “good” timetables for a set of trains (on a railway network or on a single one-way line), satisfying the so-called track capacity constraints, with the aim of optimizing an objective function that can have different meanings according to the requests of the railway company (e.g. one can be asked to schedule the trains according to the timetables preferred by the train operators or to maximize the passenger satisfaction). Two are the main variants of the nominal problem: one is to consider a cyclic (or periodic) schedule of the trains that is repeated every given time period (for example every hour), and the other one is to consider a more congested network where only a non-cyclic schedule can be performed. In the recent years, many works have been dedicated to the robust version of the problem. In this case, the aim is to determine robust timetables for the trains, i.e. to find a schedule that avoids, in case of disruptions in the railway network, delay propagation as much as possible. We present an overview of the main works on train timetabling, underlining the differences between models and methods that have been developed to tackle the nominal and the robust versions of the problem.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

##### Keywords:

train timetabling; transportation; cyclic and non-cyclic timetabling; nominal and robust problems##### Software:

PESPLib
PDF
BibTeX
XML
Cite

\textit{V. Cacchiani} and \textit{P. Toth}, Eur. J. Oper. Res. 219, No. 3, 727--737 (2012; Zbl 1253.90108)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Brännlund, U.; Lindberg, P.O.; Nöu, A.; Nilsson, J.E., Allocation of scarce track capacity using Lagrangian relaxation, Transportation science, 32, 358-369, (1998) · Zbl 1004.90035 |

[2] | R. Borndörfer, M. Grötschel, S. Lukac, K. Mitusch, T. Schlechte, S. Schultz, A. Tanner, An Auctioning Approach to Railway Slot Allocation, ZIB Technical Report ZR-05-45, 2005. |

[3] | R. Borndörfer, T. Schlechte, Models for Railway Track Allocation, ZIB Technical Report ZR-07-02, Berlin, 2007. · Zbl 1247.90169 |

[4] | R. Borndörfer, T. Schlechte, A Suitable Model for a Bi-criteria Optimization Approach to Railway Track Allocation, ZIB-Report 08-22, March 2008. |

[5] | Bussieck, M.R.; Winter, T.; Zimmermann, U.T., Discrete optimization in public rail transport, Mathematical programming, 79, 415-444, (1997) · Zbl 0887.90055 |

[6] | V. Cacchiani, A. Caprara, M. Fischetti, A Lagrangian Heuristic for Robustness, with an Application to Train Timetabling, Transportation Science, doi:10.1287/trsc.1110.0378, forthcoming. |

[7] | Cacchiani, V.; Caprara, A.; Toth, P., A column generation approach to train timetabling on a corridor, 4or, 6, 2, 125-142, (2008) · Zbl 1151.90323 |

[8] | Cacchiani, V.; Caprara, A.; Toth, P., Scheduling extra freight trains on railway networks, Transportation research part B, 44, 2, 215-231, (2010) |

[9] | Cai, X.; Goh, C.J., A fast heuristic for the train scheduling problem, Computers and operations research, 21, 499-510, (1994) · Zbl 0799.90068 |

[10] | Caprara, A.; Fischetti, M.; Toth, P., Modeling and solving the train timetabling problem, Operations research, 50, 851-861, (2002) · Zbl 1163.90482 |

[11] | Caprara, A.; Kroon, L.; Monaci, M.; Peeters, M.; Toth, P., Passenger railway optimization, (), 129-187 |

[12] | Caprara, A.; Monaci, M.; Toth, P.; Guida, P.L., A Lagrangian heuristic approach to real-world train timetabling problems, Discrete applied mathematics, 154, 738-753, (2006) · Zbl 1120.90324 |

[13] | Carey, M.; Lockwood, D., A model, algorithms and strategy for train pathing, Journal of the operational research society, 46, 988-1005, (1995) · Zbl 0832.90068 |

[14] | Cicerone, S.; D’Angelo, G.; Di Stefano, G.; Frigioni, D.; Navarra, A., On the interaction between robust timetable planning and delay management, Cocoa, (2008) |

[15] | Cicerone, S.; D’Angelo, G.; Di Stefano, G.; Frigioni, D.; Navarra, A., Recoverable robust timetabling for single delay: complexity and polynomial algorithms for special cases, Journal of combinatorial optimization, 18, 229-257, (2009) · Zbl 1176.90203 |

[16] | S. Cicerone, G. Di Stefano, M. Schachtebeck, A. Schöbel, Dynamic algorithms for recoverable robustness problems, in: ATMOS 2008 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, 2008. <http://drops.dagstuhl.de/opus/volltexte/2008/15871>. · Zbl 1247.90038 |

[17] | Cordeau, J.-F.; Toth, P.; Vigo, D., A survey of optimization models for train routing and scheduling, Transportation science, 32, 380-404, (1998) · Zbl 0987.90507 |

[18] | G. D’Angelo, G. Di Stefano, A. Navarra, Recoverable-robust timetables for trains on single line corridors, in: Proceedings of 3rd International Seminar on Railway Operations Modelling and Analysis (RailZurich2009), 2009. |

[19] | Desrosiers, J.; Dumas, Y.; Solomon, M.M.; Soumis, F., Time constrained routing and scheduling, (), 35-139 · Zbl 0861.90052 |

[20] | Fischetti, M.; Monaci, M., Light robustness, (), 61-84 · Zbl 1266.90196 |

[21] | Fischetti, M.; Salvagnin, D.; Zanette, A., Fast approaches to improve the robustness of a railway timetable, Transportation science, 43, 321-335, (2009) |

[22] | Higgings, A.; Kozan, E.; Ferreira, L., Heuristic techniques for single line train scheduling, Journal of heuristics, 3, 43-62, (1997) · Zbl 1071.90535 |

[23] | Huisman, D.; Kroon, L.G.; Lentink, R.M.; Vromans, M.J.C.M., Operations research in passenger railway transportation, Statistica neerlandica, 59, 467-497, (2005) · Zbl 1149.90435 |

[24] | Jovanovic, D.; Harker, P.T., Tactical scheduling of rail operations: the SCAN I system, Transportation science, 25, 46-64, (1991) |

[25] | Kroon, L.G.; Dekker, R.; Maróti, G.; Retel Helmrich, M.R.; Vromans, M.J.C.M., Stochastic improvement of cyclic railway timetables, Transportation research part B, 42, 6, 553-570, (2008) |

[26] | Kroon, L.G.; Peeters, L.W.P., A variable trip time model for cyclic railway timetabling, Transportation science, 37, 198-212, (2003) |

[27] | C. Liebchen, M. Lübbecke, R. Möhring, S. Stiller, The concept of recoverable robustness, linear programming recovery, and railway applications, in: R.K. Ahuja et al. (Eds.), Robust and Online Large-Scale Optimization, LNCS, vol. 5868, 2009, pp. 1-27. · Zbl 1266.90044 |

[28] | Liebchen, C.; Möhring, R., The modeling power of the periodic event scheduling problem: railway timetables-and beyond, () · Zbl 1168.90459 |

[29] | Liebchen, C.; Proksch, M.; Wagner, F.H., Performance of algorithms for periodic timetable optimization, () · Zbl 1169.90315 |

[30] | Liebchen, C.; Schachtebeck, M.; Schöbel, A.; Stiller, S.; Prigge, A., Computing delay resistant railway timetables, Computers and operations research, 37, 5, 857-868, (2010) · Zbl 1177.90172 |

[31] | T. Lindner, Train Schedule Optimization in Public Rail Transport, Ph.D. Thesis, University of Technology, Braunschweig, 2000. · Zbl 1048.90114 |

[32] | Lindner, T.; Zimmermann, U.T., Cost optimal periodic train scheduling, Mathematical methods of operations research, 62, 281-295, (2005) · Zbl 1109.90042 |

[33] | Lusby, R.M.; Larsenz, J.; Ehrgott, M.; Ryan, D., Railway track allocation: models and methods, OR spectrum, (2010) |

[34] | Mistry, P.; Kwan, R.S.K., Generation and optimization of train timetables using coevolution, Lecture notes in computer science, vol. 2723, (2003), Springer · Zbl 1028.68843 |

[35] | K. Nachtigall, A Branch-and-cut Approach for Periodic Network Programming, Technical Report 29, Hildesheimer Informatik-Berichte, 1994. |

[36] | K. Nachtigall, Periodic Network Optimization and Fixed Interval Timetables, Habilitation Thesis, Deutsches Zentrum für Luft- und Raumfahrt, Braunschweig, 1999. |

[37] | Nachtigall, K.; Voget, S., A genetic algorithm approach to periodic railway synchronization, Computers and operations research, 23, 453-463, (1996) · Zbl 0847.90098 |

[38] | Odijk, M., A constraint generation algorithm for the construction of periodic railway timetables, Transportation research part B, 30, 455-464, (1996) |

[39] | E. Oliveira, B.M. Smith, A Job-Shop Scheduling Model for the Single-Track Railway Scheduling Problem, Technical Report 2000.21, School of Computing Research Report, University of Leeds, 2000. |

[40] | L.W.P. Peeters, Cyclic Railway Timetable Optimization, Ph.D Thesis, Erasmus Research Institute of Management, Erasmus University, Rotterdam, 2003. |

[41] | Peeters, L.W.P.; Kroon, L.G., A cycle based optimization model for the cyclic railway timetabling problem, (), 275-296 · Zbl 0989.90521 |

[42] | A. Schöbel, A. Kratz, A Bicriteria, Approach for robust timetabling, in: R.K. Ahuja et al., (Eds.), Robust and Online Large-Scale Optimization, LNCS, vol. 5868, 2009, pp. 119-144. |

[43] | A. Schrijver, A. Steenbeek, Timetable Construction for Railed, Technical Report, CWI, Amsterdam, 1994 (in Dutch). |

[44] | Semet, Y.; Schoenauer, M., An efficient memetic, permutation-based evolutionary algorithm for real-world train timetabling, Evolutionary computation, 3, 2752-2759, (2005) |

[45] | Serafini, P.; Ukovich, W., A mathematical model for periodic event scheduling problems, SIAM journal on discrete mathematics, 2, 550-581, (1989) · Zbl 0676.90030 |

[46] | Szpigel, B., Optimal train scheduling on a single track railway, (), 343-351 |

[47] | M.P. Tormos, A.L. Lova, L.P. Ingolotti, F. Barber, A Genetic Approach to Robust Train Timetabling, Technical Report ARRIVAL-TR-0173, Arrival Project, 2008. · Zbl 1151.90594 |

[48] | Vansteenwegen, P.; Van Oudheusden, D., Developing railway timetables which guarantee a better service, European journal of operational research, 173, 337-350, (2006) · Zbl 1125.90385 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.