Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

GRASP with Path-Relinking: Recent Advances and Applications

  • Chapter
Metaheuristics: Progress as Real Problem Solvers

Part of the book series: Operations Research/Computer Science Interfaces Series ((ORCS,volume 32))

  • 3733 Accesses

  • 182 Citations

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. 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.

    Google Scholar 

  2. 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.

    Article  MathSciNet  Google Scholar 

  3. 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.

    Google Scholar 

  4. 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.

    Google Scholar 

  5. 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.

    Google Scholar 

  6. E. Balas and M.J. Saltzman. An algorithm for the three-index assignment problem. Oper. Res., 39:150–161, 1991.

    Google Scholar 

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

    Google Scholar 

  8. 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.

    Article  Google Scholar 

  9. 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.

    Google Scholar 

  10. 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.

    Google Scholar 

  11. 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.

    Article  Google Scholar 

  12. 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.

    Google Scholar 

  13. G. Dahl and B. Johannessen. The 2-path network problem. Networks, 43:190–199, 2004.

    Article  Google Scholar 

  14. 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.

    Article  Google Scholar 

  15. T.A. Feo and M.G.C. Resende. Greedy randomized adaptive search procedures. Journal of Global Optimization, 6:109–133, 1995.

    Article  MathSciNet  Google Scholar 

  16. 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.

    Google Scholar 

  17. 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.

    Article  Google Scholar 

  18. 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.

    Google Scholar 

  19. 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.

    MathSciNet  Google Scholar 

  20. 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.

    Google Scholar 

  21. A.M. Frieze. Complexity of a 3-dimensional assignment problem. European Journal of Operational Research, 13:161–164, 1983.

    Article  Google Scholar 

  22. 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.

    Google Scholar 

  23. 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.

    Google Scholar 

  24. 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.

    Google Scholar 

  25. F. Glover and M. Laguna. Tabu Search. Kluwer, 1997.

    Google Scholar 

  26. F. Glover, M. Laguna, and R. Martí. Fundamentals of scatter search and path relinking. Control and Cybernetics, 39:653–684, 2000.

    MathSciNet  Google Scholar 

  27. 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.

    Article  Google Scholar 

  28. M. Laguna and R. Martí. GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS Journal on Computing, 11:44–52, 1999.

    Google Scholar 

  29. 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.

    Google Scholar 

  30. 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.

    Google Scholar 

  31. 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.

    Google Scholar 

  32. 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.

    Google Scholar 

  33. W.P. Pierskalla. The tri-subsitution method for the three-multidimensional assignment problem. CORS J., 5:71–81, 1967.

    Google Scholar 

  34. 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.

    Article  MathSciNet  Google Scholar 

  35. 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.

    Google Scholar 

  36. M.G.C. Resende. Computing approximate solutions of the maximum covering problem using GRASP. Journal of Heuristics, 4:161–171, 1998.

    Article  Google Scholar 

  37. 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.

    Article  Google Scholar 

  38. 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.

    Article  Google Scholar 

  39. 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.

    Article  Google Scholar 

  40. M.G.C. Resende and C.C. Ribeiro. A GRASP for graph planarization. Networks, 29:173–189, 1997.

    Article  Google Scholar 

  41. M.G.C. Resende and C.C. Ribeiro. A GRASP with path-relinking for private virtual circuit routing. Networks, 41:104–114, 2003.

    Article  MathSciNet  Google Scholar 

  42. 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.

    Google Scholar 

  43. 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.

    Google Scholar 

  44. 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.

    Google Scholar 

  45. M.G.C. Resende and R.F. Werneck. A hybrid heuristic for the p-median problem. Journal of Heuristics, 10:59–88, 2004.

    Article  Google Scholar 

  46. 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.

    Google Scholar 

  47. 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.

    Article  Google Scholar 

  48. 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.

    Google Scholar 

  49. 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.

    Google Scholar 

  50. 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.

    Article  MathSciNet  Google Scholar 

  51. 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.

    Google Scholar 

  52. 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.

    Google Scholar 

  53. 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.

    Google Scholar 

  54. M. B. Teitz and P. Bart. Heuristic methods for estimating the generalized vertex median of a weighted graph. Operations Research, 16:955–961, 1968.

    Google Scholar 

  55. R. Whitaker. A fast algorithm for the greedy interchange of largescale clustering and median location prolems. INFOR, 21:95–108, 1983.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Internet and Network Systems Research, AT&T Labs Research, 180 Park Avenue, Room C241, Florham Park, NJ, 07932, USA

    Mauricio G.C. Resendel

  2. Department of Computer Science, Catholic University of Rio de Janeiro, Rua Marquês de São Vicente, 225, Rio de Janeiro, RJ, 22453-900, Brazil

    Celso C. Ribeiro

Authors
  1. Mauricio G.C. Resendel
    View author publications

    Search author on:PubMed Google Scholar

  2. Celso C. Ribeiro
    View author publications

    Search author on:PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Kyoto University, Japan

    Toshihide Ibaraki , Koji Nonobe  & Mutsunori Yagiura ,  & 

Rights and permissions

Reprints 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

Publish with us

Policies and ethics