IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v246y2016i1d10.1007_s10479-014-1682-7.html
   My bibliography  Save this article

A Lagrangian relaxation approach for expansion of a highway network

Author

Listed:
  • Eusebio Angulo

    (Universidad de Castilla La Mancha)

  • Ricardo García-Ródenas

    (Universidad de Castilla La Mancha)

  • José Luis Espinosa-Aranda

    (Universidad de Castilla La Mancha)

Abstract

This paper deals with the problem of improving an existing road network in the context of strategic planning through the creation of new highway corridors. To address this problem we analyse three mixed integer programming models. The so-called [P1] is the classical capacitated multicommodity network design model. The model named [P2] imposes on [P1] the location of a single (main path) highway corridor in the road network and [P3] adds to [P2] a set of sub-tour breaking constraints. The stated goal is to minimize the total travel time for a known origin-destination demand matrix with a given budget. In this paper we propose an efficient method for [P3], based on a Lagrangian relaxation, to obtain easily-solved sub-problems. A cutting-plane method for solving the Lagrangian sub-problems is proposed. This method generates valid cuts until an optimal solution is found. The Lagrangian dual problem is solved using the sub-gradient optimization method. A case study has been carried out for the region of Castilla-La Mancha (Spain). Computational comparisons between the proposed method and a state-of-the-art mixed-integer code are presented. The Lagrangian relaxation approach is found to be capable of generating good feasible solutions to the case study within a reasonable computational time.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:annopr:v:246:y:2016:i:1:d:10.1007_s10479-014-1682-7
    DOI: 10.1007/s10479-014-1682-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-014-1682-7
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-014-1682-7?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. Current, J. R. & Re Velle, C. S. & Cohon, J. L., 1985. "The maximum covering/shortest path problem: A multiobjective network design and routing formulation," European Journal of Operational Research, Elsevier, vol. 21(2), pages 189-199, August.
    2. Konak, Abdullah, 2012. "Network design problem with relays: A genetic algorithm with a path-based crossover and a set covering formulation," European Journal of Operational Research, Elsevier, vol. 218(3), pages 829-837.
    3. 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.
    4. Duin, Cees & Volgenant, Anton, 1989. "Reducing the hierarchical network design problem," European Journal of Operational Research, Elsevier, vol. 39(3), pages 332-344, April.
    5. Contreras, Ivan & Fernández, Elena, 2012. "General network design: A unified view of combined location and network design problems," European Journal of Operational Research, Elsevier, vol. 219(3), pages 680-697.
    6. L. Escudero & S. Muñoz, 2009. "An approach for solving a modification of the extended rapid transit network design problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 17(2), pages 320-334, December.
    7. Solanki, Rajendra S. & Gorti, Jyothi K. & Southworth, Frank, 1998. "Using decomposition in large-scale highway network design with a quasi-optimization heuristic," Transportation Research Part B: Methodological, Elsevier, vol. 32(2), pages 127-140, February.
    8. Hasan Pirkul & John Current & V. Nagarajan, 1991. "The Hierarchical Network Design Problem: A New Formulation and Solution Procedures," Transportation Science, INFORMS, vol. 25(3), pages 175-182, August.
    9. 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.
    10. Teodor Gabriel Crainic & Michel Gendreau & Judith M. Farvolden, 2000. "A Simplex-Based Tabu Search Method for Capacitated Network Design," INFORMS Journal on Computing, INFORMS, vol. 12(3), pages 223-236, August.
    11. 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.
    12. Current, John & Marsh, Michael, 1993. "Multiobjective transportation network design and routing problems: Taxonomy and annotation," European Journal of Operational Research, Elsevier, vol. 65(1), pages 4-19, February.
    13. Current, John R. & ReVelle, Charles S. & Cohon, Jared L., 1986. "The hierarchical network design problem," European Journal of Operational Research, Elsevier, vol. 27(1), pages 57-66, October.
    14. John Current & Hasan Pirkul & Erik Rolland, 1994. "Efficient Algorithms for Solving the Shortest Covering Path Problem," Transportation Science, INFORMS, vol. 28(4), pages 317-327, November.
    15. Erdemir, Elif Tokar & Batta, Rajan & Spielman, Seth & Rogerson, Peter A. & Blatt, Alan & Flanigan, Marie, 2008. "Location coverage models with demand originating from nodes and paths: Application to cellular network design," European Journal of Operational Research, Elsevier, vol. 190(3), pages 610-632, November.
    16. Brian Boffey & Subhash Narula, 1998. "Models for multi-path covering-routing problems," Annals of Operations Research, Springer, vol. 82(0), pages 331-342, August.
    17. 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.
    18. Kaj Holmberg & Di Yuan, 2000. "A Lagrangian Heuristic Based Branch-and-Bound Approach for the Capacitated Network Design Problem," Operations Research, INFORMS, vol. 48(3), pages 461-481, June.
    19. Sancho, N. G. F., 1997. "The hierarchical network design problem with multiple primary paths," European Journal of Operational Research, Elsevier, vol. 96(2), pages 323-328, January.
    20. 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.
    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. 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.
    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. 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. Gollowitzer, Stefan & Gouveia, Luis & Ljubić, Ivana, 2013. "Enhanced formulations and branch-and-cut for the two level network design problem with transition facilities," European Journal of Operational Research, Elsevier, vol. 225(2), pages 211-222.
    5. 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.
    6. J. Beasley & E. Nascimento, 1996. "The Vehicle Routing-Allocation Problem: A unifying framework," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 4(1), pages 65-86, June.
    7. Timothy J. Niblett & Richard L. Church, 2016. "The Shortest Covering Path Problem," International Regional Science Review, , vol. 39(1), pages 131-151, January.
    8. 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.
    9. 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.
    10. Á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.
    11. Matisziw, Timothy C. & Murray, Alan T. & Kim, Changjoo, 2006. "Strategic route extension in transit networks," European Journal of Operational Research, Elsevier, vol. 171(2), pages 661-673, June.
    12. Marie Schmidt & Anita Schöbel, 2014. "Location of speed-up subnetworks," Annals of Operations Research, Springer, vol. 223(1), pages 379-401, December.
    13. 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.
    14. Curtin, Kevin M. & Biba, Steve, 2011. "The Transit Route Arc-Node Service Maximization problem," European Journal of Operational Research, Elsevier, vol. 208(1), pages 46-56, January.
    15. López-de-los-Mozos, M.C. & Mesa, Juan A. & Schöbel, Anita, 2017. "A general approach for the location of transfer points on a network with a trip covering criterion and mixed distances," European Journal of Operational Research, Elsevier, vol. 260(1), pages 108-121.
    16. Obreque, Carlos & Donoso, Macarena & Gutiérrez, Gabriel & Marianov, Vladimir, 2010. "A branch and cut algorithm for the hierarchical network design problem," European Journal of Operational Research, Elsevier, vol. 200(1), pages 28-35, January.
    17. Eduardo Álvarez-Miranda & Ivana Ljubić & S. Raghavan & Paolo Toth, 2015. "The Recoverable Robust Two-Level Network Design Problem," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 1-19, February.
    18. Murawski, Lisa & Church, Richard L., 2009. "Improving accessibility to rural health services: The maximal covering network improvement problem," Socio-Economic Planning Sciences, Elsevier, vol. 43(2), pages 102-110, June.
    19. 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.
    20. Ilfat Ghamlouche & Teodor Gabriel Crainic & Michel Gendreau, 2003. "Cycle-Based Neighbourhoods for Fixed-Charge Capacitated Multicommodity Network Design," Operations Research, INFORMS, vol. 51(4), pages 655-667, August.

    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:246:y:2016:i:1:d:10.1007_s10479-014-1682-7. 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.