IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v42y2008i4p420-435.html
   My bibliography  Save this article

The First Optimized Railway Timetable in Practice

Author

Listed:
  • Christian Liebchen

    (Kombinatorische Optimierung und Graphenalgorithmen, Technische Universität, D-10623 Berlin, Germany)

Abstract

A short time ago, decision support by operations research methods in railway companies was limited to operations planning (e.g., vehicle scheduling, duty scheduling, crew rostering). In effect since December 12, 2004, the 2005 timetable of the Berlin subway is based on the results of mathematical programming techniques. It is the first such service concept that has been put into daily operation. Profiting from these techniques, compared with the previous timetable, the Berlin subway today operates with a timetable that offers shorter passenger waiting times---both at stops and at transfers---and even saves one train. The work is based on a well-established graph model, the periodic event-scheduling problem ( Pesp ). This model was introduced as early as 1989. Besides describing in detail its first success story in practice, in this paper we also deepen a result on the asymptotic complexity of the Pesp : we provide MAXSNP-hardness proofs of two natural optimization variants.

Suggested Citation

  • Christian Liebchen, 2008. "The First Optimized Railway Timetable in Practice," Transportation Science, INFORMS, vol. 42(4), pages 420-435, November.
    • Handle: RePEc:inm:ortrsc:v:42:y:2008:i:4:p:420-435
    DOI: 10.1287/trsc.1080.0240
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1080.0240
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1080.0240?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Christian Liebchen & Mark Proksch & Frank H. Wagner, 2008. "Performance of Algorithms for Periodic Timetable Optimization," Lecture Notes in Economics and Mathematical Systems, in: Mark Hickman & Pitu Mirchandani & Stefan Voß (ed.), Computer-aided Systems in Public Transport, pages 151-180, Springer.
    2. Ralf Borndörfer & Martin Grötschel & Marc E. Pfetsch, 2007. "A Column-Generation Approach to Line Planning in Public Transport," Transportation Science, INFORMS, vol. 41(1), pages 123-132, February.
    3. Alberto Caprara & Matteo Fischetti & Paolo Toth, 2002. "Modeling and Solving the Train Timetabling Problem," Operations Research, INFORMS, vol. 50(5), pages 851-861, October.
    4. Odijk, Michiel A., 1996. "A constraint generation algorithm for the construction of periodic railway timetables," Transportation Research Part B: Methodological, Elsevier, vol. 30(6), pages 455-464, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Cacchiani, Valentina & Furini, Fabio & Kidd, Martin Philip, 2016. "Approaches to a real-world Train Timetabling Problem in a railway node," Omega, Elsevier, vol. 58(C), pages 97-110.
    2. Zhang, Yongxiang & Peng, Qiyuan & Lu, Gongyuan & Zhong, Qingwei & Yan, Xu & Zhou, Xuesong, 2022. "Integrated line planning and train timetabling through price-based cross-resolution feedback mechanism," Transportation Research Part B: Methodological, Elsevier, vol. 155(C), pages 240-277.
    3. Zhang, Yongxiang & Peng, Qiyuan & Yao, Yu & Zhang, Xin & Zhou, Xuesong, 2019. "Solving cyclic train timetabling problem through model reformulation: Extended time-space network construct and Alternating Direction Method of Multipliers methods," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 344-379.
    4. Jakub OZIOMEK & Andrzej ROGOWSKI, 2018. "Improvement Of Regularity Of Urban Public Transport Lines By Means Of Intervals Synchronization," Transport Problems, Silesian University of Technology, Faculty of Transport, vol. 13(4), pages 91-102, December.
    5. Rolf N. Van Lieshout, 2021. "Integrated Periodic Timetabling and Vehicle Circulation Scheduling," Transportation Science, INFORMS, vol. 55(3), pages 768-790, May.
    6. Hartleb, Johann & Schmidt, Marie, 2022. "Railway timetabling with integrated passenger distribution," European Journal of Operational Research, Elsevier, vol. 298(3), pages 953-966.
    7. Wenliang Zhou & Xiaorong You & Wenzhuang Fan, 2020. "A Mixed Integer Linear Programming Method for Simultaneous Multi-Periodic Train Timetabling and Routing on a High-Speed Rail Network," Sustainability, MDPI, vol. 12(3), pages 1-34, February.
    8. Yan, Fei & Goverde, Rob M.P., 2019. "Combined line planning and train timetabling for strongly heterogeneous railway lines with direct connections," Transportation Research Part B: Methodological, Elsevier, vol. 127(C), pages 20-46.
    9. Kang, Liujiang & Zhu, Xiaoning & Sun, Huijun & Wu, Jianjun & Gao, Ziyou & Hu, Bin, 2019. "Last train timetabling optimization and bus bridging service management in urban railway transit networks," Omega, Elsevier, vol. 84(C), pages 31-44.
    10. Yu-Jun Zheng, 2018. "Emergency Train Scheduling on Chinese High-Speed Railways," Transportation Science, INFORMS, vol. 52(5), pages 1077-1091, October.
    11. Han Zheng & Junhua Chen & Zhaocha Huang & Jianhao Zhu, 2022. "Joint Optimization of Multi-Cycle Timetable Considering Supply-to-Demand Relationship and Energy Consumption for Rail Express," Mathematics, MDPI, vol. 10(21), pages 1-29, November.
    12. Martin-Iradi, Bernardo & Ropke, Stefan, 2022. "A column-generation-based matheuristic for periodic and symmetric train timetabling with integrated passenger routing," European Journal of Operational Research, Elsevier, vol. 297(2), pages 511-531.
    13. Ralf Borndörfer & Berkan Erol & Thomas Graffagnino & Thomas Schlechte & Elmar Swarat, 2014. "Optimizing the Simplon railway corridor," Annals of Operations Research, Springer, vol. 218(1), pages 93-106, July.
    14. Cacchiani, Valentina & Toth, Paolo, 2012. "Nominal and robust train timetabling problems," European Journal of Operational Research, Elsevier, vol. 219(3), pages 727-737.
    15. Pellegrini, Paola & Rodriguez, Joaquin, 2013. "Single European Sky and Single European Railway Area: A system level analysis of air and rail transportation," Transportation Research Part A: Policy and Practice, Elsevier, vol. 57(C), pages 64-86.
    16. Barrena, Eva & Canca, David & Coelho, Leandro C. & Laporte, Gilbert, 2014. "Single-line rail rapid transit timetabling under dynamic passenger demand," Transportation Research Part B: Methodological, Elsevier, vol. 70(C), pages 134-150.
    17. Robenek, Tomáš & Maknoon, Yousef & Azadeh, Shadi Sharif & Chen, Jianghang & Bierlaire, Michel, 2016. "Passenger centric train timetabling problem," Transportation Research Part B: Methodological, Elsevier, vol. 89(C), pages 107-126.
    18. Jonas Harbering, 2017. "Delay resistant line planning with a view towards passenger transfers," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 25(3), pages 467-496, October.
    19. Polinder, G.-J. & Kroon, L.G. & Aardal, K. & Schmidt, M.E. & Molinaro, M., 2018. "Resolving infeasibilities in railway timetabling instances," ERIM Report Series Research in Management ERS-2018-002-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    20. Zhou, Wenliang & Tian, Junli & Xue, Lijuan & Jiang, Min & Deng, Lianbo & Qin, Jin, 2017. "Multi-periodic train timetabling using a period-type-based Lagrangian relaxation decomposition," Transportation Research Part B: Methodological, Elsevier, vol. 105(C), pages 144-173.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:42:y:2008:i:4:p:420-435. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.