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

Fast Approaches to Improve the Robustness of a Railway Timetable

Author

Listed:
  • Matteo Fischetti

    (Department of Information Engineering, University of Padova, 1 35131-Padova, Italy)

  • Domenico Salvagnin

    (Department of Pure and Applied Mathematics, University of Padova, 1 35121-Padova, Italy)

  • Arrigo Zanette

    (Department of Pure and Applied Mathematics, University of Padova, 1 35121-Padova, Italy)

Abstract

The train timetabling problem (TTP) consists of finding a train schedule on a railway network that satisfies some operational constraints and maximizes some profit function that accounts for the efficiency of the infrastructure usage. In practical cases, however, the maximization of the objective function is not enough, and one calls for a robust solution that is capable of absorbing, as much as possible, delays/disturbances on the network. In this paper we propose and computationally analyze four different methods to improve the robustness of a given TTP solution for the aperiodic (noncyclic) case. The approaches combine linear programming (LP) and ad hoc stochastic programming/robust optimization techniques. We computationally compare the effectiveness and practical applicability of the four techniques under investigation on real-world test cases from the Italian railway company Trenitalia. The outcome is that two of the proposed techniques are very fast and provide robust solutions of comparable quality with respect to the standard (but very time consuming) stochastic programming approach.

Suggested Citation

  • Matteo Fischetti & Domenico Salvagnin & Arrigo Zanette, 2009. "Fast Approaches to Improve the Robustness of a Railway Timetable," Transportation Science, INFORMS, vol. 43(3), pages 321-335, August.
    • Handle: RePEc:inm:ortrsc:v:43:y:2009:i:3:p:321-335
    DOI: 10.1287/trsc.1090.0264
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1090.0264
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1090.0264?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. Jeff Linderoth & Alexander Shapiro & Stephen Wright, 2006. "The empirical behavior of sampling methods for stochastic programming," Annals of Operations Research, Springer, vol. 142(1), pages 215-241, February.
    2. Charles E. Clark, 1961. "Importance Sampling in Monte Carlo Analyses," Operations Research, INFORMS, vol. 9(5), pages 603-620, October.
    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. Kroon, L.G. & Dekker, R. & Vromans, M.J.C.M., 2005. "Cyclic Railway Timetabling: a Stochastic Optimization Approach," ERIM Report Series Research in Management ERS-2005-051-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.
    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. Michael Freimer & Jeffrey Linderoth & Douglas Thomas, 2012. "The impact of sampling methods on bias and variance in stochastic linear programs," Computational Optimization and Applications, Springer, vol. 51(1), pages 51-75, January.
    2. Zéphyr, Luckny & Lang, Pascal & Lamond, Bernard F. & Côté, Pascal, 2017. "Approximate stochastic dynamic programming for hydroelectric production planning," European Journal of Operational Research, Elsevier, vol. 262(2), pages 586-601.
    3. Alexandre Forel & Martin Grunow, 2023. "Dynamic stochastic lot sizing with forecast evolution in rolling‐horizon planning," Production and Operations Management, Production and Operations Management Society, vol. 32(2), pages 449-468, February.
    4. Wang, Dian & D’Ariano, Andrea & Zhao, Jun & Zhong, Qingwei & Peng, Qiyuan, 2022. "Integrated rolling stock deadhead routing and timetabling in urban rail transit lines," European Journal of Operational Research, Elsevier, vol. 298(2), pages 526-559.
    5. de Lima, Vinícius L. & Alves, Cláudio & Clautiaux, François & Iori, Manuel & Valério de Carvalho, José M., 2022. "Arc flow formulations based on dynamic programming: Theoretical foundations and applications," European Journal of Operational Research, Elsevier, vol. 296(1), pages 3-21.
    6. Chen, Lijian, 2020. "Determine the cost of denying boarding to passengers: An optimization-based approach," International Journal of Production Economics, Elsevier, vol. 220(C).
    7. Laurent Daudet & Frédéric Meunier, 2020. "Minimizing the waiting time for a one-way shuttle service," Journal of Scheduling, Springer, vol. 23(1), pages 95-115, February.
    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. Güzin Bayraksan & David P. Morton, 2011. "A Sequential Sampling Procedure for Stochastic Programming," Operations Research, INFORMS, vol. 59(4), pages 898-913, August.
    10. Li, Jiajie & Bai, Yun & Chen, Yao & Yang, Lingling & Wang, Qian, 2022. "A two-stage stochastic optimization model for integrated tram timetable and speed control with uncertain dwell times," Energy, Elsevier, vol. 260(C).
    11. Emelogu, Adindu & Chowdhury, Sudipta & Marufuzzaman, Mohammad & Bian, Linkan & Eksioglu, Burak, 2016. "An enhanced sample average approximation method for stochastic optimization," International Journal of Production Economics, Elsevier, vol. 182(C), pages 230-252.
    12. Xiaotie Chen & David L. Woodruff, 2024. "Distributions and bootstrap for data-based stochastic programming," Computational Management Science, Springer, vol. 21(1), pages 1-21, June.
    13. Miao Bai & Bjorn Berg & Esra Sisikoglu Sir & Mustafa Y. Sir, 2023. "Partially partitioned templating strategies for outpatient specialty practices," Production and Operations Management, Production and Operations Management Society, vol. 32(1), pages 301-318, January.
    14. Huang, Yeran & Yang, Lixing & Tang, Tao & Gao, Ziyou & Cao, Fang, 2017. "Joint train scheduling optimization with service quality and energy efficiency in urban rail transit networks," Energy, Elsevier, vol. 138(C), pages 1124-1147.
    15. Coviello, Nicola, 2015. "Modelling periodic operations on single track lines: Timetable design and stability evaluation," Research in Transportation Economics, Elsevier, vol. 54(C), pages 2-14.
    16. Halit Üster & Sung Ook Hwang, 2017. "Closed-Loop Supply Chain Network Design Under Demand and Return Uncertainty," Transportation Science, INFORMS, vol. 51(4), pages 1063-1085, November.
    17. Fei, Xin & Gülpınar, Nalân & Branke, Jürgen, 2019. "Efficient solution selection for two-stage stochastic programs," European Journal of Operational Research, Elsevier, vol. 277(3), pages 918-929.
    18. Löhndorf, Nils, 2016. "An empirical analysis of scenario generation methods for stochastic optimization," European Journal of Operational Research, Elsevier, vol. 255(1), pages 121-132.
    19. Shi, Qingxin & Li, Fangxing & Dong, Jin & Olama, Mohammed & Wang, Xiaofei & Winstead, Chris & Kuruganti, Teja, 2022. "Co-optimization of repairs and dynamic network reconfiguration for improved distribution system resilience," Applied Energy, Elsevier, vol. 318(C).
    20. Zhan, Shuguang & Wang, Pengling & Wong, S.C. & Lo, S.M., 2022. "Energy-efficient high-speed train rescheduling during a major disruption," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 157(C).

    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:43:y:2009:i:3:p:321-335. 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.