A Lagrangian relaxation approach for expansion of a highway network

Eusebio Angulo (), Ricardo García-Ródenas () and José Luis Espinosa-Aranda ()
Additional contact information
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

Annals of Operations Research, 2016, vol. 246, issue 1, No 7, 126 pages

Abstract: 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.

Keywords: Highway corridor location; Multicommodity network design; Network expansion; Lagrangian relaxation; Demand covering (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-014-1682-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:246:y:2016:i:1:d:10.1007_s10479-014-1682-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-014-1682-7

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().