Using decomposition in large-scale highway network design with a quasi-optimization heuristic

Rajendra S. Solanki, Jyothi K. Gorti and Frank Southworth

Transportation Research Part B: Methodological, 1998, vol. 32, issue 2, 127-140

Abstract: The highway network design problem deals with the selection of links from a base network to facilitate the flow of vehicles from origins to destinations. A proper selection of links requires a balance between minimization of travel costs from origins to destinations and minimization of costs incurred in building or improving links in the network. Link construction costs are usually minimized as a part of the objective or constrained by budget availability. National or regional highway network design problems require excessive amounts of computing time, if solved to optimality. This paper presents a variation of the Modified Quasi-Optimization (MQO) heuristic developed by Dionne and Florian (1979). The proposed algorithm solves a large network design problem by decomposing it in a sequence of smaller problems. Additional savings in computation time are achieved by limiting the search in the MQO heuristic to a well-designed set of paths for each OD pair. These paths are generated to suit the network design problem and differ from the K-shortest paths for the OD pairs. The combined use of decomposition and a limited set of paths allows the proposed heuristic to address realistic network design problems. Numerical experience with a problem involving 6563 nodes and 9800 two-ways links is reported.

Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191-2615(97)00020-9
Full text for ScienceDirect subscribers only

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:eee:transb:v:32:y:1998:i:2:p:127-140

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().