Optimizing the simplon railway corridor. (English) Zbl 1301.90028

Borndörfer, Ralf; Erol, Berkan; Graffagnino, Thomas; Schlechte, Thomas; Swarat, Elmar

Ann. Oper. Res. 218, 93-106 (2014).

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.

MSC:

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

Keywords:

railway track allocation; network aggregation; case study; simplon corridor

Software:

TTPLib

References:

[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