×

A GRASP and path relinking heuristic for rural road network development. (English) Zbl 1122.90417

Summary: This paper presents a model for rural road network design that involves two objectives: maximize all season road connectivity among villages in a region and maximize route efficiency, while allocating a fix budget among a number of possible road projects. The problem is modeled as a bicriterion optimization problem and solved heuristically through a greedy randomized adaptive search procedure (GRASP) in conjunction with a path relinking procedure. The implementation of GRASP and path relinking includes two novel modifications, a new form of reactive GRASP and a new form of path relinking. Overall, the heuristic approach is streamlined through the incorporation of advanced network flow reoptimization techniques. Results indicate that this implementation outperforms both GRASP as well as a straightforward form of GRASP with path relinking. For small problem instances, for which optimality could be verified, this new, modified form of GRASP with path relinking solved all but one known instance optimally.

MSC:

90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdulaal, M. and L.J. LeBlanc. (1979). ”Continuous equilibrium network design models.” Transportation Research B 13B, 19–32. · Zbl 0398.90042
[2] Aiex, R.M., M.G.C. Resende, P.M. Pardalos, and G. Toraldo. (2003). ”GRASP with path relinking for the three-index assignment problem.” INFORMS J. on Computing (to appear). · Zbl 1239.90087
[3] Antunes, A., A. Seco, and N. Pinto. (2003). ”An accessibility-maximization approach to road network planning.” Computer-Aided Civil and Infrastructure Engineering 18, 224–240. · doi:10.1111/1467-8667.00312
[4] Boyce, D.E., A. Farhi, and R. Weischedel. (1973). ”Optimal network problem: A branch-and-bound algorithm.” Environmental and Planning 5, 519–533. · doi:10.1068/a050519
[5] Church, R.L. and M.P. Scaparra. (2003). A mixed integer programming formulation for a bi-objective rural road development problem. Working paper.
[6] Current, J. and H. Min. (1986). ”Multiobjective design of transportation networks: Taxonomy and annotation.” European Journal of Operational Research 26, 187–201. · doi:10.1016/0377-2217(86)90180-3
[7] Dionne, R. and M. Florian. (1979). ”Exact and approximate algorithms for optimal network design.” Networks 9, 37–59. · Zbl 0397.94024 · doi:10.1002/net.3230090104
[8] Dreyfus, S.E. (1969). ”An appraisal of some shortest path algorithms.” Operations Research 17, 395–412. · Zbl 0172.44202 · doi:10.1287/opre.17.3.395
[9] Feng, C. and J.Y. Wu. (2003). ”Highway investment planning model for equity issues.” Journal of Urban Planning and Development 129(3), 161–176. · doi:10.1061/(ASCE)0733-9488(2003)129:3(161)
[10] Feo, T.A. and M.G.C. Resende. (1989). ”A probabilistic heuristic for a computationally difficult set covering problem.” Operations Research Letters 8, 67–71. · Zbl 0675.90073 · doi:10.1016/0167-6377(89)90002-3
[11] Feo, T.A. and M.G.C. Resende. (1995). ”Greedy randomized adaptive search procedures.” Journal of Global Optimization 6, 109–133. · Zbl 0822.90110 · doi:10.1007/BF01096763
[12] Festa, P. and M.G.C. Resende. (2001). ”GRASP: An annotated bibliography.” In C.C. Ribeiro and P. Hansen (eds.), Essays and Surveys in Metaheuristics, Kluwer Academic Publishers, pp. 325–367. · Zbl 1017.90001
[13] Gallo, G. (1980). ”Reoptimization procedures in shortest paths problems.” Riv. Mat. Sci. Econom. Social. 3, 3–13. · Zbl 0512.90094
[14] Glover, F. (1996). ”Tabu search and adaptive memory programming–Advances, applications and challenges.” In R.S. Barr, R.V. Helgason, and J.L. Kennington (eds.), Interfaces in Computer Science and Operations Research, Boston: Kluwer, pp. 1–24. · Zbl 0882.90111
[15] Glover, F. (1999). ”Scatter search and path relinking.” In D. Corne, M. Dorigo, and F. Glover (eds.), New Ideas in Optimisation. Wiley. · Zbl 0983.90077
[16] Glover, F. and M. Laguna. (1997). Tabu Search. Boston: Kluwer Academic Publishers. · Zbl 0930.90083
[17] Glover, F., M. Laguna, and R. Martì. (2000). ”Fundamentals of scatter search and path relinking”. Control and Cybernetics 39, 653–684. · Zbl 0983.90077
[18] Johnson, D.S., J.K. Lenstra, and A.H.G. Rinnooy Kan. (1978). ”The complexity of the network design problem.” Networks 8, 279–285. · Zbl 0395.94048 · doi:10.1002/net.3230080402
[19] Koski, J. (1985). ”Defectiveness of weighting method in multicriteria optimization of structures.” Communications in Applied Numerical Methods 1, 333–337. · Zbl 0586.73148 · doi:10.1002/cnm.1630010613
[20] Laguna, M. and R. Martì. (1999). ”GRASP and path relinking for the 2-layer straight line crossing minimization.” INFORMS Journal on Computing 11, 44–52. · Zbl 1092.90544 · doi:10.1287/ijoc.11.1.44
[21] Magnanti, T.L. and R.T. Wong. (1984). ”Network design and transportation planning: Models and algorithms.” Transportation Science 18(1), 1–55. · doi:10.1287/trsc.18.1.1
[22] Meng, Q. and H. Yang. (2002). ”Benefit distribution and equity in road network design.” Transportation Research Part B 36, 19–35. · doi:10.1016/S0191-2615(00)00036-9
[23] Pallottino, S. and M.G. Scutellà. (1997). ”Dual algorithms for the shortest path tree problem.” Networks 29, 125–133. · Zbl 0889.90148 · doi:10.1002/(SICI)1097-0037(199703)29:2<125::AID-NET7>3.0.CO;2-L
[24] Pallottino, S. and M.G. Scutellà. (2003). ”A new algorithm for reoptimizing shortest paths when the arc costs change.” Operations Research Letters 31, 149–160. · Zbl 1041.90062 · doi:10.1016/S0167-6377(02)00192-X
[25] Prais, M. and C.C. Ribeiro. (2000). ”Reactive GRASP: An application to a Matrix Decomposition Problem in TDMA traffic assignment.” INFORMS Journal on Computing 12(3), 164–176. · Zbl 1040.90504 · doi:10.1287/ijoc.12.3.164.12639
[26] Resende, M.G.C. (1998). ”Computing approximate solutions of the maximum covering problem using GRASP.” Journal of Heuristics 4, 161–171. · Zbl 0913.90202 · doi:10.1023/A:1009677613792
[27] Resende, M.G.C. and C.C. Ribeiro. (2002). ”Greedy randomized adaptive search procedures.” In F. Glover and G. Kochenberger (eds.), State-of-the-Art Handbook of Metaheuristics, Kluwer Academic Publishers, pp. 219–249. · Zbl 1102.90384
[28] Resende, M.G.C. and C.C. Ribeiro. (2003). ”GRASP with path-relinking for private virtual circuit routing.” Networks 41, 104–114. · Zbl 1028.90502 · doi:10.1002/net.10065
[29] Resende, M.G.C. and R.F. Werneck. (2002). ”A GRASP with path-relinking for the p-median problem.” Technical Report, AT&T Labs Research, Florham Park, NJ.
[30] Ribeiro, C.C., E. Uchoa, and R.F. Werneck. (2002). ”A hybrid GRASP with perturbations for the Steiner problem in graphs.” INFORMS Journal on Computing 14, 228–246. · Zbl 1238.90117 · doi:10.1287/ijoc.14.3.228.116
[31] Sheffi, Y. (1985). Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods, Englewood Cliffs, NJ: Prentice-Hall.
[32] Yang, H. and M.G.H. Bell. (1998). ”Models and algorithms for road network design: A review and some new development.” Transportation Reviews 18(3), 257–258. · doi:10.1080/01441649808717016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.