IDEAS home Printed from https://ideas.repec.org/a/taf/transp/v29y2005i1p25-42.html
   My bibliography  Save this article

Adapting a Search Algorithm for the Spanish Railway Network

Author

Listed:
  • J. Macías-Guarasa
  • R. San-Segundo
  • J.M. Montero
  • J. Ferreiros
  • R. Córdoba
  • F. Fernández
  • L.F. D'Haro
  • J.M. Pardo

Abstract

This article describes a search algorithm adapted to the Spanish Railway Network for generating as many traveling options as possible between two railway stations. This algorithm (Warshall's algorithm) uses connecting matrices to find all possible railway journeys. The Spanish Railway Company has imposed severe restrictions: less than 1 second per query in a 600Mhz processor PC with 32Mb RAM and 150Mb hard disk free memory. The final average time for a simple query is around 0.25 seconds and the whole memory consumption is 127Mb. The final implementation has been divided into 3 modules. In the first module, we store additional information in the connecting matrices to accelerate the later search, proposing several strategies for reducing thier size. The journey option calculation module accesses the matrix information and composes the traveling options. Finally, in the filtering module we describe the selection criteria considering the algorithm embedded in a general information service.

Suggested Citation

  • J. Macías-Guarasa & R. San-Segundo & J.M. Montero & J. Ferreiros & R. Córdoba & F. Fernández & L.F. D'Haro & J.M. Pardo, 2005. "Adapting a Search Algorithm for the Spanish Railway Network," Transportation Planning and Technology, Taylor & Francis Journals, vol. 29(1), pages 25-42, December.
    • Handle: RePEc:taf:transp:v:29:y:2005:i:1:p:25-42
    DOI: 10.1080/03081060600585145
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1080/03081060600585145
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1080/03081060600585145?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. Jean-François Cordeau & Paolo Toth & Daniele Vigo, 1998. "A Survey of Optimization Models for Train Routing and Scheduling," Transportation Science, INFORMS, vol. 32(4), pages 380-404, November.
    2. Jean-François Cordeau & François Soumis & Jacques Desrosiers, 2001. "Simultaneous Assignment of Locomotives and Cars to Passenger Trains," Operations Research, INFORMS, vol. 49(4), pages 531-548, August.
    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. Ruf, Moritz & Cordeau, Jean-François, 2021. "Adaptive large neighborhood search for integrated planning in railroad classification yards," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 26-51.
    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. Camilo Ortiz-Astorquiza & Jean-François Cordeau & Emma Frejinger, 2021. "The Locomotive Assignment Problem with Distributed Power at the Canadian National Railway Company," Transportation Science, INFORMS, vol. 55(2), pages 510-531, March.
    4. van den Berg, B.W.V. & Kroon, L.G. & Salomon, M. & Abbink, E.J.W., 2002. "Allocation of Railway Rolling Stock for Passenger Trains," ERIM Report Series Research in Management ERS-2002-47-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.
    5. Frisch, Sarah & Hungerländer, Philipp & Jellen, Anna & Primas, Bernhard & Steininger, Sebastian & Weinberger, Dominic, 2021. "Solving a real-world Locomotive Scheduling Problem with Maintenance Constraints," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 386-409.
    6. Abbink, E. & van den Berg, B. & Kroon, L.G. & Salomon, M., 2002. "Allocation of Railway Rolling Stock for Passenger Trains," Other publications TiSEM 9d73e0e8-2463-4694-b85b-4, Tilburg University, School of Economics and Management.
    7. Scheffler, Martin & Neufeld, Janis S. & Hölscher, Michael, 2020. "An MIP-based heuristic solution approach for the locomotive assignment problem focussing on (dis-)connecting processes," Transportation Research Part B: Methodological, Elsevier, vol. 139(C), pages 64-80.
    8. Belgacem Bouzaiene-Ayari & Clark Cheng & Sourav Das & Ricardo Fiorillo & Warren B. Powell, 2016. "From Single Commodity to Multiattribute Models for Locomotive Optimization: A Comparison of Optimal Integer Programming and Approximate Dynamic Programming," Transportation Science, INFORMS, vol. 50(2), pages 366-389, May.
    9. Abbink, E. & van den Berg, B. & Kroon, L.G. & Salomon, M., 2002. "Allocation of Railway Rolling Stock for Passenger Trains," Discussion Paper 2002-43, Tilburg University, Center for Economic Research.
    10. Xu, Xiaoming & Li, Chung-Lun & Xu, Zhou, 2018. "Integrated train timetabling and locomotive assignment," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 573-593.
    11. Erwin Abbink & Bianca van den Berg & Leo Kroon & Marc Salomon, 2004. "Allocation of Railway Rolling Stock for Passenger Trains," Transportation Science, INFORMS, vol. 38(1), pages 33-41, February.
    12. Albrecht, Amie & Howlett, Phil & Pudney, Peter & Vu, Xuan & Zhou, Peng, 2016. "The key principles of optimal train control—Part 1: Formulation of the model, strategies of optimal type, evolutionary lines, location of optimal switching points," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 482-508.
    13. Jin, Jian Gang & Zhao, Jun & Lee, Der-Horng, 2013. "A column generation based approach for the Train Network Design Optimization problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 50(C), pages 1-17.
    14. 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.
    15. Gianmarco Garrisi & Cristina Cervelló-Pastor, 2019. "Train-Scheduling Optimization Model for Railway Networks with Multiplatform Stations," Sustainability, MDPI, vol. 12(1), pages 1-25, December.
    16. Shuaian Wang & Dan Zhuge & Lu Zhen & Chung-Yee Lee, 2021. "Liner Shipping Service Planning Under Sulfur Emission Regulations," Transportation Science, INFORMS, vol. 55(2), pages 491-509, March.
    17. Li, Feng & Gao, Ziyou & Li, Keping & Yang, Lixing, 2008. "Efficient scheduling of railway traffic based on global information of train," Transportation Research Part B: Methodological, Elsevier, vol. 42(10), pages 1008-1030, 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. Canca, David & Barrena, Eva, 2018. "The integrated rolling stock circulation and depot location problem in railway rapid transit systems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 115-138.
    20. Ricardo Saraiva de Camargo & Gilberto de Miranda & Henrique Pacca L. Luna, 2009. "Benders Decomposition for Hub Location Problems with Economies of Scale," Transportation Science, INFORMS, vol. 43(1), pages 86-97, February.

    More about this item

    Statistics

    Access and download statistics

    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:taf:transp:v:29:y:2005:i:1:p:25-42. 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 Longhurst (email available below). General contact details of provider: http://www.tandfonline.com/GTPT20 .

    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.