Abstract
Path-relinking is a major enhancement to the basic greedy randomized adaptive search procedure (GRASP), leading to significant improvements in solution time and quality. Path-relinking adds a memory mechanism to GRASP by providing an intensification strategy that explores trajectories connecting GRASP solutions and the best elite solutions previously produced during the search. This paper reviews recent advances and applications of GRASP with path-relinking. A brief review of GRASP is given. This is followed by a description of path-relinking and how it is incorporated into GRASP. Several recent applications of GRASP with path-relinking are reviewed. The paper concludes with a discussion of extensions to this strategy, concerning in particular parallel implementations and applications of path-relinking with other metaheuristics.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
R.M. Aiex. Uma investigação experimental da distribuição de probabilidade de tempo de solução em heurísticas GRASP e sua aplicação na análise de implementações paralelas. PhD thesis, Department of Computer Science, Catholic University of Rio de Janeiro, Rio de Janeiro, Brazil, 2002.
R.M. Aiex, S. Binato, and M.G.C. Resende. Parallel GRASP with path-relinking for job shop scheduling. Parallel Computing, 29:393–430, 2003.
R.M. Aiex, M.G.C. Resende, P.M. Pardalos, and G. Toraldo. GRASP with path relinking for the three-index assignment problem. Technical report, AT&T Labs Research, Florham Park, NJ 07733, 2000. To appear in INFORMS J. on Computing.
R.M. Aiex, M.G.C. Resende, and C.C. Ribeiro. Probability distribution of solution time in GRASP: An experimental investigation. Journal of Heuristics, 8:343–373, 2002.
D.J. Aloise, D. Aloise, C.T.M. Rocha, C.C. Ribeiro, José C. Ribeiro Filho, and Luiz S.S. Moura. Scheduling workover rigs for onshore oil production. Discrete Applied Mathematics, to appear.
E. Balas and M.J. Saltzman. An algorithm for the three-index assignment problem. Oper. Res., 39:150–161, 1991.
S. Binato, H. Faria Jr., and M.G.C. Resende. Greedy randomized adaptive path relinking. In J.P. Sousa, editor, Proceedings of the IV Metaheuristics International Conference, pages 393–397, 2001.
R.E. Burkard, R. Rudolf, and G.J. Woeginger. Three-dimensional axial assignment problems with decomposible cost coefficients. Discrete Applied Mathematics, 65:123–139, 1996.
S.A. Canuto, M.G.C. Resende, and C.C. Ribeiro. Local search with perturbation for the prize-collecting Steiner tree problems in graphs. Networks, 38:50–58, 2001.
G. Cornuejols, M. L. Fisher, and G. L. Nemhauser. Location of bank accounts to optimize float: An analytical study of exact and approximate algorithms. Management Science, 23:789–810, 1977.
Y. Crama and F.C.R. Spieksma. Approximation algorithms for three-dimensional assignment problems with triangle inequalities. European Journal of Operational Research, 60:273–279, 1992.
V.-D. Cung, S.L. Martins, C.C. Ribeiro, and C. Roucairol. Strategies for the parallel implementation of metaheuristics. In C.C. Ribeiro and P. Hansen, editors, Essays and Surveys in Metaheuristics, pages 263–308. Kluwer Academic Publishers, 2002.
G. Dahl and B. Johannessen. The 2-path network problem. Networks, 43:190–199, 2004.
T.A. Feo and M.G.C. Resende. A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters, 8:67–71, 1989.
T.A. Feo and M.G.C. Resende. Greedy randomized adaptive search procedures. Journal of Global Optimization, 6:109–133, 1995.
T.A. Feo, M.G.C. Resende, and S.H. Smith. A greedy randomized adaptive search procedure for maximum independent set. Operations Research, 42:860–878, 1994.
P. Festa, P.M. Pardalos, M.G.C. Resende, and C.C. Ribeiro. Randomized heuristics for the max-cut problem. Optimization Methods and Software, 7:1033–1058, 2002.
P. Festa and M.G.C. Resende. GRASP: An annotated bibliography. In C.C. Ribeiro and P. Hansen, editors, Essays and surveys on metaheuristics, pages 325–367. Kluwer Academic Publishers, 2002.
C. Fleurent and F. Glover. Improved constructive multistart strategies for the quadratic assignment problem using adaptive memory. INFORMS Journal on Computing, 11:198–204, 1999.
B. Fortz and M. Thorup. Internet traffic engineering by optimizing ospf weights. In Proc. IEEE INFOCOM 2000 — The Conference on Computer Communications, pages 519–528, 2000.
A.M. Frieze. Complexity of a 3-dimensional assignment problem. European Journal of Operational Research, 13:161–164, 1983.
M.R. Garey and D.S. Johnson. Computers and intractability — A guide to the theory of NP-completeness. W.H. Freeman and Com-pany, 1979.
F. Glover. Tabu search and adaptive memory programing — Advances, applications and challenges. In R.S. Barr, R.V. Helgason, and J.L. Kennington, editors, Interfaces in Computer Science and Operations Research, pages 1–75. Kluwer, 1996.
F. Glover. Multi-start and strategic oscillation methods — Principles to exploit adaptive memory. In M. Laguna and J.L. Gonzáles-Velarde, editors, Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research, pages 1–24. Kluwer, 2000.
F. Glover and M. Laguna. Tabu Search. Kluwer, 1997.
F. Glover, M. Laguna, and R. Martí. Fundamentals of scatter search and path relinking. Control and Cybernetics, 39:653–684, 2000.
O. Kariv and L. Hakimi. An algorithmic approach to nework location problems, Part II: The p-medians. SIAM Journal of Applied Mathematics, 37:539–560, 1979.
M. Laguna and R. Martí. GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS Journal on Computing, 11:44–52, 1999.
Y. Li, P.M. Pardalos, and M.G.C. Resende. A greedy randomized adaptive search procedure for the quadratic assignment problem. In P.M. Pardalos and H. Wolkowicz, editors, Quadratic assignment and related problems, volume 16 of DIMACS Series on Discrete Mathematics and Theoretical Computer Science, pages 237–261. American Mathematical Society, 1994.
S.L. Martins, P.M. Pardalos, M.G.C. Resende, and C.C. Ribeiro. Greedy randomized adaptive search procedures for the steiner problem in graphs. In P.M. Pardalos, S. Rajasekaran, and J. Rolim, editors, Randomization methods in algorithmic design, volume 43 of DIMACS Series on Discrete Mathematics and Theoretical Computer Science, pages 133–145. American Mathematical Society, 1999.
S.L. Martins, C.C. Ribeiro, and I. Rosseti. Applications and parallel implementations of metaheuristics in network design and routing. Lecture Notes in Computer Science, 3285:205–213, 2004.
C.A. Oliveira, P.M. Pardalos, and M.G.C. Resende. GRASP with path-relinking for the QAP. In Toshihide Ibaraki and Yasunari Yoshitomi, editors, Proceedings of the Fifth Metaheuristics International Conference, pages 57-1–57-6, 2003.
W.P. Pierskalla. The tri-subsitution method for the three-multidimensional assignment problem. CORS J., 5:71–81, 1967.
M. Prais and C.C. Ribeiro. Reactive GRASP: An application to a matrix decomposition problem in TDMA traffic assignment. INFORMS Journal on Computing, 12:164–176, 2000.
M. G. C. Resende and R. F. Werneck. On the implementation of a swap-based local search procedure for the p-median problem. In R. E. Ladner, editor, Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments (ALENEX’03), pages 119–127. SIAM, 2003.
M.G.C. Resende. Computing approximate solutions of the maximum covering problem using GRASP. Journal of Heuristics, 4:161–171, 1998.
M.G.C. Resende, T.A. Feo, and S.H. Smith. Algorithm 787: Fortran subroutines for approximate solution of maximum independent set problems using GRASP. ACM Transactions on Mathematical Software, 24:386–394, 1998.
M.G.C. Resende, P.M. Pardalos, and Y. Li. Algorithm 754: Fortran subroutines for approximate solution of dense quadratic assignment problems using GRASP. ACM Transactions on Mathematical Software, 22:104–118, 1996.
M.G.C. Resende, L.S. Pitsoulis, and P.M. Pardalos. Fortran subroutines for computing approximate solutions of MAX-SAT problems using GRASP. Discrete Applied Mathematics, 100:95–113, 2000.
M.G.C. Resende and C.C. Ribeiro. A GRASP for graph planarization. Networks, 29:173–189, 1997.
M.G.C. Resende and C.C. Ribeiro. A GRASP with path-relinking for private virtual circuit routing. Networks, 41:104–114, 2003.
M.G.C. Resende and C.C. Ribeiro. GRASP and path-relinking: Recent advances and applications. In Toshihide Ibaraki and Yasunari Yoshitomi, editors, Proceedings of the Fifth Metaheuristics International Conference, pages T6-1–T6-6, 2003.
M.G.C. Resende and C.C. Ribeiro. Greedy randomized adaptive search procedures. In F. Glover and G. Kochenberger, editors, Handbook of Metaheuristics, pages 219–249. Kluwer Academic Publishers, 2003.
M.G.C. Resende and R.F. Werneck. A GRASP with path-relinking for the p-median problem. Technical Report TD-5E53XL, AT&T Labs Research, 2002.
M.G.C. Resende and R.F. Werneck. A hybrid heuristic for the p-median problem. Journal of Heuristics, 10:59–88, 2004.
M.G.C. Resende and R.F. Werneck. A hybrid multistart heuristic for the uncapacitated facility location problem. European Journal of Operational Research, to appear.
C.C. Ribeiro and M.G.C. Resende. Algorithm 797: Fortran subroutines for approximate solution of graph planarization problems using GRASP. ACM Transactions on Mathematical Software, 25:341–352, 1999.
C.C. Ribeiro and I. Rosseti. A parallel GRASP for the 2-path network design problem. Lecture Notes in Computer Science, 2004:922–926, 2002.
C.C. Ribeiro and I. Rosseti. Efficient parallel cooperative implementations of GRASP heuristics. Technical report, Catholic University of Rio de Janeiro, Rio de Janeiro, Brazil, 2005.
C.C. Ribeiro, E. Uchoa, and R.F. Werneck. A hybrid GRASP with perturbations for the Steiner problem in graphs. INFORMS Journal on Computing, 14:228–246, 2002.
C.C. Ribeiro and D.S. Vianna. A genetic algorithm for the phylogeny problem using an optimized crossover strategy based on path-relinking. Revista Tecnologia da Informação, 3(2):67–70, 2003.
I. Rosseti. Heurísticas para o problema de síntese de redes a 2-caminhos. PhD thesis, Department of Computer Science, Catholic University of Rio de Janeiro, Rio de Janeiro, Brazil, July 2003.
M.C. Souza, C. Duhamel, and C.C. Ribeiro. A GRASP with path-relinking heuristic for the capacitated minimum spanning tree problem. In M.G.C. Resende and J. Souza, editors, Metaheuristics: Computer Decision Making, pages 627–658. Kluwer Academic Publishers, 2003.
M. B. Teitz and P. Bart. Heuristic methods for estimating the generalized vertex median of a weighted graph. Operations Research, 16:955–961, 1968.
R. Whitaker. A fast algorithm for the greedy interchange of largescale clustering and median location prolems. INFOR, 21:95–108, 1983.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer Science+Business Media, Inc.
About this chapter
Cite this chapter
Resendel, M.G., Ribeiro, C.C. (2005). GRASP with Path-Relinking: Recent Advances and Applications. In: Ibaraki, T., Nonobe, K., Yagiura, M. (eds) Metaheuristics: Progress as Real Problem Solvers. Operations Research/Computer Science Interfaces Series, vol 32. Springer, Boston, MA. https://doi.org/10.1007/0-387-25383-1_2
Download citation
DOI: https://doi.org/10.1007/0-387-25383-1_2
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-25382-4
Online ISBN: 978-0-387-25383-1
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)