Optimizing the simplon railway corridor. (English) Zbl 1301.90028

Summary: This paper presents a case study of a railway timetable optimization for the very dense Simplon corridor, a major railway connection in the Alps between Switzerland and Italy. The key to deal with the complexity of this scenario is the use of a novel aggregation-disaggregation method. Starting from a detailed microscopic representation as it is used in railway simulation, the data is transformed by an automatic procedure into a less detailed macroscopic representation, that is sufficient for the purpose of capacity planning and amenable to state-of-the-art integer programming optimization methods. This macroscopic railway network is saturated with trains. Finally, the optimized timetable is re-transformed to the microscopic level in such a way that it can be operated without any conflicts among the train paths. Using this micro-macro aggregation-disaggregation approach in combination with integer programming methods, it becomes for the first time possible to generate a profit maximal and conflict free timetable for the complete Simplon corridor over an entire day by a simultaneous optimization of all trains requests. In addition, this also allows us to undertake a sensitivity analysis of various problem parameters.


90B35 Deterministic scheduling theory in operations research
90B06 Transportation, logistics and supply chain management
90C10 Integer programming


Full Text: DOI


[1] Borndörfer, R.; Schlechte, T.; Liebchen, C. (ed.); Ahuja, R. K. (ed.); Mesa, J. A. (ed.), Models for railway track allocation, Dagstuhl, Germany, 2007, Schloss Dagstuhl, Germany · Zbl 1247.90169
[2] Borndörfer, R.; Grötschel, M.; Lukac, S.; Mitusch, K.; Schlechte, T.; Schultz, S.; Tanner, A., An auctioning approach to railway slot allocation, Competition and Regulation in Network Industries, 1, 163-196, (2006)
[3] Borndörfer, R.; Grötschel, M.; Pfetsch, M. E., A column-generation approach to line planning in public transport, Transportation Science, 41, 123-132, (2007)
[4] Borndörfer, R.; Erol, B.; Schlechte, T.; Hansen, I. (ed.); Wendler, E. (ed.); Weidmann, U. (ed.); Lüthi, M. (ed.); Rodriguez, J. (ed.); Ricci, S. (ed.); Kroon, L. (ed.), Optimization of macroscopic train schedules via TS-OPT, Zürich, Switzerland
[5] Brännlund, U.; Lindberg, P. O.; Nou, A.; Nilsson, J.-E., Railway timetabling using Langangian relaxation, Transportation Science, 32, 358-369, (1998) · Zbl 1004.90035
[6] Cacchiani, V. (2007). Models and algorithms for combinatorial optimization problems arising in railway applications. PhD thesis, DEIS, Bologna. · Zbl 1162.90330
[7] Cacchiani, V.; Caprara, A.; Toth, P., A column generation approach to train timetabling on a corridor, 4OR, 6, 125-142, (2008) · Zbl 1151.90323
[8] Cai, X.; Goh, C. J., A fast heuristic for the train scheduling problem, Computers & Operations Research, 21, 499-510, (1994) · Zbl 0799.90068
[9] Caimi, G. (2009). Algorithmic decision support for train scheduling in a large and highly utilised railway network. PhD thesis, ETH, Zurich.
[10] Caimi, G.; Burkolter, D.; Herrmann, T.; Fleuren, H. A. (ed.); Hertog, D. (ed.); Kort, P. M. (ed.), Finding delay-tolerant train routings through stations, 136-143, (2004)
[11] Caprara, A.; Fischetti, M.; Toth, P., Modeling and solving the train timetabling problem, Operations Research, 50, 851-861, (2002) · Zbl 1163.90482
[12] Caprara, A.; Galli, L.; Toth, P.; Liebchen, C. (ed.); Ahuja, R. K. (ed.); Mesa, J. A. (ed.), Solution of the train platforming problem, No. 07001, (2007), Schloss Dagstuhl, Germany · Zbl 1247.90036
[13] Corman, F.; D’Ariano, A.; Pacciarelli, D.; Pranzo, M., Centralized versus distributed systems to reschedule trains in two dispatching areas, Public Transport, 2, 219-247, (2010)
[14] Erol, B.; Klemenz, M.; Schlechte, T.; Schultz, S.; Tanner, A.; Allan, A. T. J. (ed.); Arias, E. (ed.); Brebbia, C. A. (ed.); Goodman, C. (ed.); Rumsey, A. F. (ed.), TTPLIB 2008—a library for train timetabling problems, (2008), Southampton
[15] Fischer, F.; Helmberg, C.; Janßen, J.; Krostitz, B.; Fischetti, M. (ed.); Widmayer, P. (ed.), Towards solving very large scale train timetabling problems by Lagrangian relaxation, Dagstuhl, Germany, 2008, Schloss Dagstuhl, Germany · Zbl 1247.90042
[16] Gröger, T. (2002). Simulation der Fahrplanerstellung auf der Basis eines hierarchischen Trassenmanagements und Nachweis der Stabiliät der Betriebsabwicklung. PhD thesis, Veröffentlichungen d. Verkehrswiss. Inst. der Rheinisch-Westfälischen Techn. Hochsch, Aachen.
[17] Hansen, I., & Pachl, J. (2008). Railway, timetable & traffic. Hamburg: Eurailpress.
[18] Hürlimann, D. (2001). Object oriented modeling of infrastructure elements and business processes in railways. PhD thesis, ETH, Zürich.
[19] Jespersen-Groth, J.; Potthoff, D.; Clausen, J.; Huisman, D.; Kroon, L. G.; Maróti, G.; Nielsen, M. N., Disruption management in passenger railway transportation, 399-421, (2009), Berlin · Zbl 1266.90043
[20] Kettner, M.; Sewcyk, B.; Eickmann, C., Integrating microscopic and macroscopic models for railway network evaluation, 2003, Washington
[21] Liebchen, C. (2006). Periodic timetable optimization in public transport. Berlin: Springer. · Zbl 1209.90095
[22] Lusby, R., Larsen, J., Ryan, D., & Ehrgott, M. (2006). Routing trains through railway junctions: a new set packing approach. Technical report, Informatics and Mathematical Modelling, Technical University of Denmark, DTU, Richard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby, 2006. http://www2.imm.dtu.dk/pubdb/p.php?4961 · Zbl 1004.90035
[23] Schlechte, T.; Borndörfer, R.; Erol, B.; Graffagnino, T.; Swarat, E., Micro-macro transformation of railway networks, Journal of Rail Transport Planning & Management, 1, 38-48, (2011)
[24] Siefer, T.; Radtke, A., Railway-simulation key for better operation and optimal use of infrastructure, (2005)
[25] Wendler, E. (1999). Analytische Berechnung der planmässigen Wartezeiten bei asynchroner Fahrplankonstruktion. Aachen: Verkehrswiss. Inst. der Rheinisch-Westfälischen Techn. Hochsch.
[26] Zwaneveld, P. J.; Kroon, L. G.; Romeijn, H. E.; Salomon, M.; Dauzere-Peres, S.; Hoesel, S. P. M.; Ambergen, H. W., Routing trains through railway stations: model formulation and algorithms, Transportation Science, 30, 181-194, (1996) · Zbl 0884.90079
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.