IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v84y2016icp124-156.html
   My bibliography  Save this article

Reducing the passenger travel time in practice by the automated construction of a robust railway timetable

Author

Listed:
  • Sels, P.
  • Dewilde, T.
  • Cattrysse, D.
  • Vansteenwegen, P.

Abstract

Automatically generating timetables has been an active research area for some time, but the application of this research in practice has been limited. We believe this is due to two reasons. Firstly, some of the models in the literature impose artificial upper bounds on time supplements. This causes a high risk of generating infeasibilities. Secondly, some models that leave out these upper bounds often generate solutions that contain some very large time supplements because these supplements are not penalised in the objective function. The reason is that these objective functions often do not completely correspond to the true goal of a timetable. We solve both problems by minimising our objective function: total passenger travel time, expected in practice. Since this function evaluates and indirectly steers all time related decision variables in the system, we do not need to further restrict the ranges of any of these variables. As a result, our model does not suffer from infeasibilities generated by such artificial upper bounds for supplements.

Suggested Citation

  • Sels, P. & Dewilde, T. & Cattrysse, D. & Vansteenwegen, P., 2016. "Reducing the passenger travel time in practice by the automated construction of a robust railway timetable," Transportation Research Part B: Methodological, Elsevier, vol. 84(C), pages 124-156.
    • Handle: RePEc:eee:transb:v:84:y:2016:i:c:p:124-156
    DOI: 10.1016/j.trb.2015.12.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261515002684
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2015.12.007?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Kroon, Leo & Maróti, Gábor & Helmrich, Mathijn Retel & Vromans, Michiel & Dekker, Rommert, 2008. "Stochastic improvement of cyclic railway timetables," Transportation Research Part B: Methodological, Elsevier, vol. 42(6), pages 553-570, July.
    2. Dennis Huisman & Leo G. Kroon & Ramon M. Lentink & Michiel J. C. M. Vromans, 2005. "Operations Research in passenger railway transportation," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 59(4), pages 467-497, November.
    3. Cacchiani, Valentina & Toth, Paolo, 2012. "Nominal and robust train timetabling problems," European Journal of Operational Research, Elsevier, vol. 219(3), pages 727-737.
    4. Sels, P. & Vansteenwegen, P. & Dewilde, T. & Cattrysse, D. & Waquet, B. & Joubert, A., 2014. "The train platforming problem: The infrastructure management company perspective," Transportation Research Part B: Methodological, Elsevier, vol. 61(C), pages 55-72.
    5. Christian Liebchen, 2007. "Periodic Timetable Optimization in Public Transport," Operations Research Proceedings, in: Karl-Heinz Waldmann & Ulrike M. Stocker (ed.), Operations Research Proceedings 2006, pages 29-36, Springer.
    6. G. Caimi & F. Chudak & M. Fuchsberger & M. Laumanns & R. Zenklusen, 2011. "A New Resource-Constrained Multicommodity Flow Model for Conflict-Free Train Routing and Scheduling," Transportation Science, INFORMS, vol. 45(2), pages 212-227, May.
    7. Nachtigall, Karl & Voget, Stefan, 1997. "Minimizing waiting times in integrated fixed interval timetables by upgrading railway tracks," European Journal of Operational Research, Elsevier, vol. 103(3), pages 610-627, December.
    8. Dewilde, Thijs & Sels, Peter & Cattrysse, Dirk & Vansteenwegen, Pieter, 2014. "Improving the robustness in railway station areas," European Journal of Operational Research, Elsevier, vol. 235(1), pages 276-286.
    9. Gabrio Caimi & Dan Burkolter & Thomas Herrmann & Fabian Chudak & Marco Laumanns, 2009. "Design of a Railway Scheduling Model for Dense Services," Networks and Spatial Economics, Springer, vol. 9(1), pages 25-46, March.
    10. Leo Kroon & Dennis Huisman & Erwin Abbink & Pieter-Jan Fioole & Matteo Fischetti & Gábor Maróti & Alexander Schrijver & Adri Steenbeek & Roelof Ybema, 2009. "The New Dutch Timetable: The OR Revolution," Interfaces, INFORMS, vol. 39(1), pages 6-17, February.
    11. Winnie Daamen & Rob Goverde & Ingo Hansen, 2009. "Non-Discriminatory Automatic Registration of Knock-On Train Delays," Networks and Spatial Economics, Springer, vol. 9(1), pages 47-61, March.
    12. Burdett, R.L. & Kozan, E., 2010. "A disjunctive graph model and framework for constructing new train schedules," European Journal of Operational Research, Elsevier, vol. 200(1), pages 85-98, January.
    13. Cacchiani, Valentina & Caprara, Alberto & Toth, Paolo, 2010. "Scheduling extra freight trains on railway networks," Transportation Research Part B: Methodological, Elsevier, vol. 44(2), pages 215-231, February.
    14. Wendler, E., 2007. "The scheduled waiting time on railway lines," Transportation Research Part B: Methodological, Elsevier, vol. 41(2), pages 148-158, February.
    15. Peter J. Zwaneveld & Leo G. Kroon & H. Edwin Romeijn & Marc Salomon & Stéphane Dauzère-Pérès & Stan P. M. Van Hoesel & Harrie W. Ambergen, 1996. "Routing Trains Through Railway Stations: Model Formulation and Algorithms," Transportation Science, INFORMS, vol. 30(3), pages 181-194, August.
    16. Kroon, L.G. & Huisman, D. & Abbink, E.J.W. & Fioole, P-J. & Fischetti, M. & Maróti, G. & Schrijver, A. & Steenbeek, A. & Ybema, R., 2008. "The new Dutch timetable: The OR revolution," Econometric Institute Research Papers EI 2008-19, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    17. E. E. Osuna & G. F. Newell, 1972. "Control Strategies for an Idealized Public Transportation System," Transportation Science, INFORMS, vol. 6(1), pages 52-72, February.
    18. 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.
    19. Shi Qiang Liu & Erhan Kozan, 2011. "Scheduling Trains with Priorities: A No-Wait Blocking Parallel-Machine Job-Shop Scheduling Model," Transportation Science, INFORMS, vol. 45(2), pages 175-198, May.
    20. Valentina Cacchiani & Alberto Caprara & Matteo Fischetti, 2012. "A Lagrangian Heuristic for Robustness, with an Application to Train Timetabling," Transportation Science, INFORMS, vol. 46(1), pages 124-133, February.
    21. Vansteenwegen, P. & Van Oudheusden, D., 2007. "Decreasing the passenger waiting time for an intercity rail network," Transportation Research Part B: Methodological, Elsevier, vol. 41(4), pages 478-492, May.
    22. Carey, Malachy & Carville, Sinead, 2003. "Scheduling and platforming trains at busy complex stations," Transportation Research Part A: Policy and Practice, Elsevier, vol. 37(3), pages 195-224, March.
    23. Alberto Caprara & Laura Galli & Paolo Toth, 2011. "Solution of the Train Platforming Problem," Transportation Science, INFORMS, vol. 45(2), pages 246-257, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Guo, Xin & Sun, Huijun & Wu, Jianjun & Jin, Jiangang & Zhou, Jin & Gao, Ziyou, 2017. "Multiperiod-based timetable optimization for metro transit networks," Transportation Research Part B: Methodological, Elsevier, vol. 96(C), pages 46-67.
    2. Limsawasd, Charinee & Athigakunagorn, Nathee & Khathawatcharakun, Phattadon & Boonmee, Atiwat, 2022. "Skip-Stop Strategy Patterns optimization to enhance mass transit operation under physical distancing policy due to COVID-19 pandemic outbreak," Transport Policy, Elsevier, vol. 126(C), pages 225-238.
    3. Schön, Cornelia & König, Eva, 2018. "A stochastic dynamic programming approach for delay management of a single train line," European Journal of Operational Research, Elsevier, vol. 271(2), pages 501-518.
    4. Ralf Borndörfer & Heide Hoppmann & Marika Karbstein, 2017. "Passenger routing for periodic timetable optimization," Public Transport, Springer, vol. 9(1), pages 115-135, July.
    5. Gkiotsalitis, K. & Alesiani, F., 2019. "Robust timetable optimization for bus lines subject to resource and regulatory constraints," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 128(C), pages 30-51.
    6. Van Thielen, Sofie & Corman, Francesco & Vansteenwegen, Pieter, 2018. "Considering a dynamic impact zone for real-time railway traffic management," Transportation Research Part B: Methodological, Elsevier, vol. 111(C), pages 39-59.
    7. Zhou, Li & Yang, Xin & Wang, Huan & Wu, Jianjun & Chen, Lei & Yin, Haodong & Qu, Yunchao, 2020. "A robust train timetable optimization approach for reducing the number of waiting passengers in metro systems," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 558(C).
    8. 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.
    9. Erfan Hassannayebi & Seyed Hessameddin Zegordi & Mohammad Reza Amin-Naseri & Masoud Yaghini, 2018. "Optimizing headways for urban rail transit services using adaptive particle swarm algorithms," Public Transport, Springer, vol. 10(1), pages 23-62, May.
    10. Burggraeve, Sofie & Vansteenwegen, Pieter, 2017. "Robust routing and timetabling in complex railway stations," Transportation Research Part B: Methodological, Elsevier, vol. 101(C), pages 228-244.
    11. Xie, J. & Wong, S.C. & Zhan, S. & Lo, S.M. & Chen, Anthony, 2020. "Train schedule optimization based on schedule-based stochastic passenger assignment," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 136(C).
    12. Lusby, Richard M. & Larsen, Jesper & Bull, Simon, 2018. "A survey on robustness in railway planning," European Journal of Operational Research, Elsevier, vol. 266(1), pages 1-15.
    13. Yan, Fei & Bešinović, Nikola & Goverde, Rob M.P., 2019. "Multi-objective periodic railway timetabling on dense heterogeneous railway corridors," Transportation Research Part B: Methodological, Elsevier, vol. 125(C), pages 52-75.
    14. Polinder, Gert-Jaap & Breugem, Thomas & Dollevoet, Twan & Maróti, Gábor, 2019. "An adjustable robust optimization approach for periodic timetabling," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 50-68.
    15. Jiang, Feng & Cacchiani, Valentina & Toth, Paolo, 2017. "Train timetabling by skip-stop planning in highly congested lines," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 149-174.
    16. Li, Shukai & Zhou, Xuesong & Yang, Lixing & Gao, Ziyou, 2018. "Automatic train regulation of complex metro networks with transfer coordination constraints: A distributed optimal control framework," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 228-253.
    17. Högdahl, Johan & Bohlin, Markus & Fröidh, Oskar, 2019. "A combined simulation-optimization approach for minimizing travel time and delays in railway timetables," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 192-212.
    18. Zeyu Wang & Leishan Zhou & Bin Guo & Xing Chen & Hanxiao Zhou, 2021. "An Efficient Hybrid Approach for Scheduling the Train Timetable for the Longer Distance High-Speed Railway," Sustainability, MDPI, vol. 13(5), pages 1-22, February.

    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. Sparing, Daniel & Goverde, Rob M.P., 2017. "A cycle time optimization model for generating stable periodic railway timetables," Transportation Research Part B: Methodological, Elsevier, vol. 98(C), pages 198-223.
    2. Vansteenwegen, Pieter & Dewilde, Thijs & Burggraeve, Sofie & Cattrysse, Dirk, 2016. "An iterative approach for reducing the impact of infrastructure maintenance on the performance of railway systems," European Journal of Operational Research, Elsevier, vol. 252(1), pages 39-53.
    3. Burggraeve, Sofie & Vansteenwegen, Pieter, 2017. "Robust routing and timetabling in complex railway stations," Transportation Research Part B: Methodological, Elsevier, vol. 101(C), pages 228-244.
    4. Dewilde, Thijs & Sels, Peter & Cattrysse, Dirk & Vansteenwegen, Pieter, 2014. "Improving the robustness in railway station areas," European Journal of Operational Research, Elsevier, vol. 235(1), pages 276-286.
    5. 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.
    6. 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.
    7. Lu, Gongyuan & Ning, Jia & Liu, Xiaobo & Nie, Yu (Marco), 2022. "Train platforming and rescheduling with flexible interlocking mechanisms: An aggregate approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 159(C).
    8. 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.
    9. Nikola Bešinović & Rob M. P. Goverde, 2019. "Stable and robust train routing in station areas with balanced infrastructure capacity occupation," Public Transport, Springer, vol. 11(2), pages 211-236, August.
    10. Martin Josef Geiger & Sandra Huber & Sebastian Langton & Marius Leschik & Christian Lindorf & Ulrich Tüshaus, 2018. "Multi-attribute assignment of trains to departures in rolling stock management," Annals of Operations Research, Springer, vol. 271(2), pages 1131-1163, December.
    11. Cacchiani, Valentina & Toth, Paolo, 2012. "Nominal and robust train timetabling problems," European Journal of Operational Research, Elsevier, vol. 219(3), pages 727-737.
    12. 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.
    13. Sels, P. & Vansteenwegen, P. & Dewilde, T. & Cattrysse, D. & Waquet, B. & Joubert, A., 2014. "The train platforming problem: The infrastructure management company perspective," Transportation Research Part B: Methodological, Elsevier, vol. 61(C), pages 55-72.
    14. Matthew E. H. Petering & Mojtaba Heydar & Dietrich R. Bergmann, 2016. "Mixed-Integer Programming for Railway Capacity Analysis and Cyclic, Combined Train Timetabling and Platforming," Transportation Science, INFORMS, vol. 50(3), pages 892-909, August.
    15. Polinder, Gert-Jaap & Breugem, Thomas & Dollevoet, Twan & Maróti, Gábor, 2019. "An adjustable robust optimization approach for periodic timetabling," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 50-68.
    16. Julius Pätzold, 2021. "Finding robust periodic timetables by integrating delay management," Public Transport, Springer, vol. 13(2), pages 349-374, June.
    17. 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.
    18. Lu, Gongyuan & Nie, Yu(Marco) & Liu, Xiaobo & Li, Denghui, 2019. "Trajectory-based traffic management inside an autonomous vehicle zone," Transportation Research Part B: Methodological, Elsevier, vol. 120(C), pages 76-98.
    19. Polinder, Gert-Jaap & Schmidt, Marie & Huisman, Dennis, 2021. "Timetabling for strategic passenger railway planning," Transportation Research Part B: Methodological, Elsevier, vol. 146(C), pages 111-135.
    20. Kroon, L.G. & Peeters, L.W.P. & Wagenaar, J.C. & Zuidwijk, R.A., 2012. "Flexible Connections in PESP Models for Cyclic Passenger Railway Timetabling," ERIM Report Series Research in Management ERS-2012-008-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.

    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:eee:transb:v:84:y:2016:i:c:p:124-156. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    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.