Rs. Solanki et al., USING DECOMPOSITION IN LARGE-SCALE HIGHWAY NETWORK DESIGN WITH A QUASI-OPTIMIZATION HEURISTIC, Transportation research. Part B: methodological, 32(2), 1998, pp. 127-140
Citations number
18
Categorie Soggetti
Transportation,"Operatione Research & Management Science","Engineering, Civil
The highway network design problem deals with the selection of links f
rom a base network to facilitate the flow of vehicles from origins to
destinations. A proper selection of links requires a balance between m
inimization of travel costs from origins to destinations and minimizat
ion of costs incurred in building or improving links in the network. L
ink construction costs are usually minimized as a part of the objectiv
e or constrained by budget availability. National or regional highway
network design problems require excessive amounts of computing time, i
f solved to optimality. This paper presents a variation of the Modifie
d 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 heu
ristic to a well-designed set of paths for each OD pair. These paths a
re 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 reali
stic network design problems. Numerical experience with a problem invo
lving 6563 nodes and 9800 two-ways links is reported. (C) 1998 Elsevie
r Science Ltd. All rights reserved.