IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v169y2009i1p35-5310.1007-s10479-008-0388-0.html
   My bibliography  Save this article

Urban rapid transit network design: accelerated Benders decomposition

Author

Listed:
  • Ángel Marín
  • Patricia Jaramillo

Abstract

This paper presents an urban rapid transit network design model, which consists of the location of train alignments and stations in an urban traffic context. The design attempts to maximize the public transportation demand using the new infrastructure, considering a limited budget and number of transit lines. The location problem also incorporates the fact that users can choose their transportation mode and trips. In real cases, this problem is complex to solve because it has thousands of binary variables and constraints, and cannot be solved efficiently by Branch and Bound. For this reason, some algorithms based on Benders decomposition have been defined in order to solve it. These algorithms have been compared in test networks. Copyright Springer Science + Business Media, LLC 2009

Suggested Citation

  • Ángel Marín & Patricia Jaramillo, 2009. "Urban rapid transit network design: accelerated Benders decomposition," Annals of Operations Research, Springer, vol. 169(1), pages 35-53, July.
    • Handle: RePEc:spr:annopr:v:169:y:2009:i:1:p:35-53:10.1007/s10479-008-0388-0
    DOI: 10.1007/s10479-008-0388-0
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-008-0388-0
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-008-0388-0?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. Gutierrez, Genaro J. & Kouvelis, Panagiotis & Kurawarwala, Abbas A., 1996. "A robustness approach to uncapacitated network design problems," European Journal of Operational Research, Elsevier, vol. 94(2), pages 362-376, October.
    2. Mesa, Juan A. & Brian Boffey, T., 1996. "A review of extensive facility location in networks," European Journal of Operational Research, Elsevier, vol. 95(3), pages 592-603, December.
    3. Gilbert Laporte & Juan Mesa & Francisco Ortega & Ignacio Sevillano, 2005. "Maximizing Trip Coverage in the Location of a Single Rapid Transit Alignment," Annals of Operations Research, Springer, vol. 136(1), pages 49-63, April.
    4. Bruno, Giuseppe & Ghiani, Gianpaolo & Improta, Gennaro, 1998. "A multi-modal approach to the location of a rapid transit line," European Journal of Operational Research, Elsevier, vol. 104(2), pages 321-332, January.
    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. Egging, Ruud, 2013. "Benders Decomposition for multi-stage stochastic mixed complementarity problems – Applied to a global natural gas market model," European Journal of Operational Research, Elsevier, vol. 226(2), pages 341-353.
    2. Laporte, G. & Mesa, J.A. & Ortega, F.A. & Perea, F., 2011. "Planning rapid transit networks," Socio-Economic Planning Sciences, Elsevier, vol. 45(3), pages 95-104, September.
    3. Philipp Heyken Soares, 2021. "Zone-based public transport route optimisation in an urban network," Public Transport, Springer, vol. 13(1), pages 197-231, March.
    4. Dimitrios Tsiotas & Serafeim Polyzos, 2015. "Introducing a new centrality measure from the transportation network analysis in Greece," Annals of Operations Research, Springer, vol. 227(1), pages 93-117, April.
    5. Hugo M. Repolho & António P. Antunes & Richard L. Church, 2013. "Optimal Location of Railway Stations: The Lisbon-Porto High-Speed Rail Line," Transportation Science, INFORMS, vol. 47(3), pages 330-343, August.
    6. Ashkan Fakhri & Mehdi Ghatee, 2013. "Solution of preemptive multi-objective network design problems applying Benders decomposition method," Annals of Operations Research, Springer, vol. 210(1), pages 295-307, November.

    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. Eusebio Angulo & Ricardo García-Ródenas & José Luis Espinosa-Aranda, 2016. "A Lagrangian relaxation approach for expansion of a highway network," Annals of Operations Research, Springer, vol. 246(1), pages 101-126, November.
    2. Elisangela Martins de Sá & Ivan Contreras & Jean-François Cordeau & Ricardo Saraiva de Camargo & Gilberto de Miranda, 2015. "The Hub Line Location Problem," Transportation Science, INFORMS, vol. 49(3), pages 500-518, August.
    3. Hugo M. Repolho & António P. Antunes & Richard L. Church, 2013. "Optimal Location of Railway Stations: The Lisbon-Porto High-Speed Rail Line," Transportation Science, INFORMS, vol. 47(3), pages 330-343, August.
    4. Lari, Isabella & Ricca, Federica & Scozzari, Andrea, 2008. "Comparing different metaheuristic approaches for the median path problem with bounded length," European Journal of Operational Research, Elsevier, vol. 190(3), pages 587-597, November.
    5. Seyed Sina Mohri & Meisam Akbarzadeh, 2019. "Locating key stations of a metro network using bi-objective programming: discrete and continuous demand mode," Public Transport, Springer, vol. 11(2), pages 321-340, August.
    6. An, Kun & Lo, Hong K., 2016. "Two-phase stochastic program for transit network design under demand uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 84(C), pages 157-181.
    7. An, Kun & Lo, Hong K., 2015. "Robust transit network design with stochastic demand considering development density," Transportation Research Part B: Methodological, Elsevier, vol. 81(P3), pages 737-754.
    8. Laporte, G. & Mesa, J.A. & Ortega, F.A. & Perea, F., 2011. "Planning rapid transit networks," Socio-Economic Planning Sciences, Elsevier, vol. 45(3), pages 95-104, September.
    9. Canca, David & De-Los-Santos, Alicia & Laporte, Gilbert & Mesa, Juan A., 2019. "Integrated Railway Rapid Transit Network Design and Line Planning problem with maximum profit," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 127(C), pages 1-30.
    10. Luis Cadarso & Ángel Marín, 2017. "Improved rapid transit network design model: considering transfer effects," Annals of Operations Research, Springer, vol. 258(2), pages 547-567, November.
    11. Martins de Sá, Elisangela & Contreras, Ivan & Cordeau, Jean-François, 2015. "Exact and heuristic algorithms for the design of hub networks with multiple lines," European Journal of Operational Research, Elsevier, vol. 246(1), pages 186-198.
    12. Laporte, Gilbert & Mesa, Juan A. & Ortega, Francisco A., 2000. "Optimization methods for the planning of rapid transit systems," European Journal of Operational Research, Elsevier, vol. 122(1), pages 1-10, April.
    13. Zhizhu Lai & Qun Yue & Zheng Wang & Dongmei Ge & Yulong Chen & Zhihong Zhou, 2022. "The min-p robust optimization approach for facility location problem under uncertainty," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1134-1160, September.
    14. Samanta, Sutapa & Jha, Manoj K., 2011. "Modeling a rail transit alignment considering different objectives," Transportation Research Part A: Policy and Practice, Elsevier, vol. 45(1), pages 31-45, January.
    15. Mark Rozanov & Arie Tamir, 2018. "The nestedness property of location problems on the line," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 26(2), pages 257-282, July.
    16. De Rosa, Vincenzo & Gebhard, Marina & Hartmann, Evi & Wollenweber, Jens, 2013. "Robust sustainable bi-directional logistics network design under uncertainty," International Journal of Production Economics, Elsevier, vol. 145(1), pages 184-198.
    17. Nagy, Gabor & Salhi, Said, 2007. "Location-routing: Issues, models and methods," European Journal of Operational Research, Elsevier, vol. 177(2), pages 649-672, March.
    18. Mathias Michaelis & Anita Schöbel, 2009. "Integrating line planning, timetabling, and vehicle scheduling: a customer-oriented heuristic," Public Transport, Springer, vol. 1(3), pages 211-232, August.
    19. Lamb, John D., 2012. "Variable neighbourhood structures for cycle location problems," European Journal of Operational Research, Elsevier, vol. 223(1), pages 15-26.
    20. Häntsch, Marius & Huchzermeier, Arnd, 2016. "Transparency of risk for global and complex network decisions in the automotive industry," International Journal of Production Economics, Elsevier, vol. 175(C), pages 81-95.

    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:spr:annopr:v:169:y:2009:i:1:p:35-53:10.1007/s10479-008-0388-0. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.