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. Alberto Caprara & Matteo Fischetti & Paolo Toth, 2002. "Modeling and Solving the Train Timetabling Problem," Operations Research, INFORMS, vol. 50(5), pages 851-861, October.
    2. 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.
    3. 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.
    4. Charles E. Clark, 1961. "Importance Sampling in Monte Carlo Analyses," Operations Research, INFORMS, vol. 9(5), pages 603-620, October.
    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. Chen-Ritzo, Ching-Hua & Ervolina, Tom & Harrison, Terry P. & Gupta, Barun, 2010. "Sales and operations planning in systems with order configuration uncertainty," European Journal of Operational Research, Elsevier, vol. 205(3), pages 604-614, September.
    2. 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.
    3. Baker, Erin & Solak, Senay, 2011. "Climate change and optimal energy technology R&D policy," European Journal of Operational Research, Elsevier, vol. 213(2), pages 442-454, September.
    4. 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.
    5. Michal Kaut & Stein Wallace, 2011. "Shape-based scenario generation using copulas," Computational Management Science, Springer, vol. 8(1), pages 181-199, April.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. Chen, Lijian, 2020. "Determine the cost of denying boarding to passengers: An optimization-based approach," International Journal of Production Economics, Elsevier, vol. 220(C).
    12. 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.
    13. 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.
    14. Albrecht, Amie & Howlett, Phil & Pudney, Peter & Vu, Xuan & Zhou, Peng, 2018. "The two-train separation problem on non-level track—driving strategies that minimize total required tractive energy subject to prescribed section clearance times," Transportation Research Part B: Methodological, Elsevier, vol. 111(C), pages 135-167.
    15. Zhanwen Shi & Erbao Cao, 2020. "Contract farming problems and games under yield uncertainty," Australian Journal of Agricultural and Resource Economics, Australian Agricultural and Resource Economics Society, vol. 64(4), pages 1210-1238, October.
    16. Jonathan Turner & Kibaek Kim & Sanjay Mehrotra & Debra DaRosa & Mark Daskin & Heron Rodriguez, 2013. "Using optimization models to demonstrate the need for structural changes in training programs for surgical medical residents," Health Care Management Science, Springer, vol. 16(3), pages 217-227, September.
    17. Yu Nie & Xing Wu & Tito Homem-de-Mello, 2012. "Optimal Path Problems with Second-Order Stochastic Dominance Constraints," Networks and Spatial Economics, Springer, vol. 12(4), pages 561-587, December.
    18. 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.
    19. Güzin Bayraksan & David P. Morton, 2011. "A Sequential Sampling Procedure for Stochastic Programming," Operations Research, INFORMS, vol. 59(4), pages 898-913, August.
    20. Halit Üster & Gökhan Memişoğlu, 2018. "Biomass Logistics Network Design Under Price-Based Supply and Yield Uncertainty," Transportation Science, INFORMS, vol. 52(2), pages 474-492, March.

    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.