Skip to main content

Advertisement

SpringerLink
Log in

Path-relinking intensification methods for stochastic local search algorithms

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

Path-relinking is major enhancement to heuristic search methods for solving combinatorial optimization problems, leading to significant improvements in both solution quality and running times. We review its fundamentals and implementation strategies, as well as advanced hybridizations with more elaborate metaheuristic schemes such as tabu search, GRASP, genetic algorithms and scatter search. Numerical examples are discussed and algorithms compared based on their run time distributions.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Aiex, R.M., Resende, M.G.C.: Parallel strategies for GRASP with path-relinking. In: Ibaraki, T., Nonobe, K., Yagiura, M. (eds.) Metaheuristics: Progress as Real Problem Solvers, pp. 301–331. Springer, Berlin (2005)

    Google Scholar 

  • Aiex, R.M., Resende, M.G.C., Ribeiro, C.C.: Probability distribution of solution time in GRASP: An experimental investigation. J. Heuristics 8, 343–373 (2002)

    Article  MATH  Google Scholar 

  • Aiex, R.M., Binato, S., Resende, M.G.C.: Parallel GRASP with path-relinking for job shop scheduling. Parallel Comput. 29, 393–430 (2003)

    Article  MathSciNet  Google Scholar 

  • Aiex, R.M., Pardalos, P.M., Resende, M.G.C., Toraldo, G.: GRASP with path-relinking for three-index assignment. INFORMS J. Comput. 17, 224–247 (2005)

    Article  MathSciNet  Google Scholar 

  • Aiex, R.M., Resende, M.G.C., Ribeiro, C.C.: TTTPLOTS: A perl program to create time-to-target plots. Optim. Lett. 1, 355–366 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  • Andrade, D.V., Resende, M.G.C.: GRASP with path-relinking for network migration scheduling. In: Proceedings of the International Network Optimization Conference (2007a)

    Google Scholar 

  • Andrade, D.V., Resende, M.G.C.: GRASP with evolutionary path-relinking. Technical report, AT&T Labs Research, Florham Park (2007b)

  • Armentano, V.A., Shiguemoto, A.L., Løkketangen, A.: Tabu search with path relinking for an integrated production-distribution problem. Comput. Oper. Res. 38, 1199–1209 (2010)

    Article  Google Scholar 

  • Bastos, M.P., Ribeiro, C.C.: Reactive tabu search with path-relinking for the Steiner problem in graphs. In: Ribeiro, C.C., Hansen, P. (eds.) Essays and Surveys in Metaheuristics, pp. 39–58. Kluwer Academic, Norwell (2002)

    Chapter  Google Scholar 

  • Canuto, S.A., Resende, M.G.C., Ribeiro, C.C.: Local search with perturbations for the prize-collecting Steiner tree problem in graphs. Networks 38, 50–58 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  • Faria Jr., H., Binato, S., Resende, M.G.C., Falcão, D.J.: Transmission network design by a greedy randomized adaptive path relinking approach. IEEE Trans. Power Syst. 20, 43–49 (2005)

    Article  Google Scholar 

  • Feo, T.A., Resende, M.G.C., Smith, S.H.: A greedy randomized adaptive search procedure for maximum independent set. Oper. Res. 42, 860–878 (1994)

    Article  MATH  Google Scholar 

  • Festa, P., Resende, M.G.C.: An annotated bibliography of GRASP, Part I: Algorithms. Int. Trans. Oper. Res. 16, 1–24 (2009a)

    Article  MathSciNet  MATH  Google Scholar 

  • Festa, P., Resende, M.G.C.: An annotated bibliography of GRASP, Part II: Applications. Int. Trans. Oper. Res. 16, 131–172 (2009b)

    Article  MathSciNet  MATH  Google Scholar 

  • Festa, P., Pardalos, P.M., Resende, M.G.C., Ribeiro, C.C.: Randomized heuristics for the max-cut problem. Optim. Methods Softw. 6, 1033–1058 (2002)

    Article  MathSciNet  Google Scholar 

  • Festa, P., Pardalos, P.M., Pitsoulis, L.S., Resende, M.G.C.: GRASP with path-relinking for the weighted MAXSAT problem. ACM J. Exp. Algorithmics 11, 1–16 (2006)

    MathSciNet  Google Scholar 

  • Ghosh, J.B.: Computational aspects of the maximum diversity problem. Oper. Res. Lett. 19, 175–181 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  • Glover, F.: Heuristics for integer programming using surrogate constraints. Decision Sci. 8, 156–166 (1977)

    Article  Google Scholar 

  • Glover, F.: Tabu search and adaptive memory programing—advances, applications and challenges. In: Barr, R.S., Helgason, R.V., Kennington, J.L. (eds.) Interfaces in Computer Science and Operations Research, pp. 1–75. Kluwer Academic, Norwell (1996)

    Google Scholar 

  • Glover, F.: A template for scatter search and path relinking. Lect. Notes Comput. Sci. 1363, 13–54 (1998)

    Google Scholar 

  • Glover, F.: Scatter search and path relinking. In: Corne, D., Dorigo, M., Glover, F. (eds.) New Ideas in Optimization, pp. 297–316. McGraw-Hill, New York (1999)

    Google Scholar 

  • Glover, F.: Multi-start and strategic oscillation methods—Principles to exploit adaptive memory. In: Laguna, M., Gonzáles-Velarde, J.L. (eds.) Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research, pp. 1–24. Kluwer Academic, Norwell (2000)

    Chapter  Google Scholar 

  • Glover, F., Laguna, M.: Tabu Search. Kluwer Academic, Norwell (1997)

    Book  MATH  Google Scholar 

  • Glover, F., Laguna, M., Martí, R.: Fundamentals of scatter search and path relinking. Control Cybern. 39, 653–684 (2000)

    Google Scholar 

  • Glover, F., Laguna, M., Martí, R.: Scatter search. In: Ghosh, A., Tsutsui, S. (eds.) Advances in Evolutionary Computation: Theory and Applications, pp. 519–537. Springer, Berlin (2003)

    Google Scholar 

  • Glover, F., Laguna, M., Martí, R.: Scatter search and path relinking: Foundations and advanced designs. In: Onwubolu, G.C., Babu, B.V. (eds.) New Optimization Techniques in Engineering. Studies in Fuzziness and Soft Computing, vol. 141, pp. 87–100. Springer, Berlin (2004)

    Google Scholar 

  • Hansen, P., Mladenović, N.: Developments of variable neighborhood search. In: Ribeiro, C.C., Hansen, P. (eds.) Essays and Surveys in Metaheuristics, pp. 415–439. Kluwer Academic, Norwell (2002)

    Chapter  Google Scholar 

  • Ho, S.C., Gendreau, M.: Path relinking for the vehicle routing problem. J. Heuristics 12, 55–72 (2006)

    Article  MATH  Google Scholar 

  • Holland, J.H.: Adaptation in Natural and Artificial Systems. University of Michigan Press, East Lansing (1975)

    Google Scholar 

  • Hoos, H.H., Stützle, T.: Evaluation of Las Vegas algorithms—Pitfalls and remedies. In: Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence, pp. 238–245 (1998)

    Google Scholar 

  • Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum, New York (1972)

    Google Scholar 

  • Kincaid, R.K.: Good solutions to discrete noxious location problems via metaheuristics. Ann. Oper. Res. 40, 265–281 (1992)

    Article  MATH  Google Scholar 

  • Kirkpatrick, S., Gelatt Jr., C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  • Laguna, M., Martí, R.: GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS J. Comput. 11, 44–52 (1999)

    Article  MATH  Google Scholar 

  • Laguna, M., Martí, R.: Scatter search: Methodology and implementations in C. Operations Research. Computer Science Interfaces Series, Kluwer Academic, Boston (2003)

    Google Scholar 

  • Martí, R.: Feature cluster on scatter search methods for optimization. Eur. J. Oper. Res., 169, 351–698 (2006)

    Article  MATH  Google Scholar 

  • Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24, 1097–1100 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  • Oliveira, C.A., Pardalos, P.M., Resende, M.G.C.: GRASP with path-relinking for the quadratic assignment problem. Lect. Notes Comput. Sci. 3059, 356–368 (2004)

    Article  Google Scholar 

  • Ranjbar, M., Kianfar, F., Shadrokh, S.: Solving the resource availability cost problem in project scheduling by path relinking and genetic algorithm. Appl. Math. Comput. 196, 879–888 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  • Reghioui, M., Prins, C., Labadi, N.: GRASP with path relinking for the capacitated arc routing problem with time windows. Lect. Notes Comp. Sci. 4448, 722–731 (2007)

    Article  Google Scholar 

  • Resende, M.G.C., Ribeiro, C.C., Glover, F., Martí, R.: Scatter search and path-relinking: Fundamentals, advances, and applications. In: Gendreau, M., Potvin, J.-Y. (eds.) Handbook of Metaheuristics, 2nd. edn., pp. 87–107. Springer, Berlin (2010a)

    Chapter  Google Scholar 

  • Resende, M.G.C., Ribeiro, C.C.: Greedy randomized adaptive search procedures. In: Glover, F., Kochenberger, G. (eds.) Handbook of Metaheuristics, pp. 219–242. Kluwer Academic, Norwell (2003a)

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • Resende, M.G.C., Ribeiro, C.C.: GRASP with path-relinking: Recent advances and applications. In: Ibaraki, T., Nonobe, K., Yagiura, M. (eds.) Metaheuristics: Progress as Real Problem Solvers, pp. 29–63. Springer, Berlin (2005)

    Chapter  Google Scholar 

  • Resende, M.G.C., Ribeiro, C.C.: Greedy randomized adaptive search procedures: Advances, hybridizations, and applications. In: Gendreau, M., Potvin, J.-Y. (eds.) Handbook of Metaheuristics, 2nd edn. Springer, Berlin (2010)

    Google Scholar 

  • Resende, M.G.C., Ribeiro, C.C.: GRASP. In: Burke, E.K., Kendall, G. (eds.) Search Methodologies, 2nd edn. Springer, Berlin (2011)

    Google Scholar 

  • Resende, M.G.C., Werneck, R.F.: A hybrid heuristic for the p-median problem. J. Heuristics 10, 59–88 (2004)

    Article  MATH  Google Scholar 

  • Resende, M.G.C., Werneck, R.F.: A hybrid multistart heuristic for the uncapacitated facility location problem. Eur. J. Oper. Res. 174, 54–68 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  • Resende, M.G.C., Martí, R., Gallego, M., Duarte, A.: GRASP and path relinking for the max-min diversity problem. Comput. Oper. Res. 37, 498–508 (2010b)

    Article  MathSciNet  MATH  Google Scholar 

  • Ribeiro, C.C., Rosseti, I.: Efficient parallel cooperative implementations of GRASP heuristics. Parallel Comput. 33, 21–35 (2007)

    Article  MathSciNet  Google Scholar 

  • Ribeiro, C.C., Rosseti, I.: Exploiting run time distributions to compare sequential and parallel stochastic local search algorithms. In: Proceedings of the VIII Metaheuristics International Conference, Hamburg (2009)

    Google Scholar 

  • Ribeiro, C.C., Vianna, D.S.: A genetic algorithm for the phylogeny problem using an optimized crossover strategy based on path-relinking. In: Anais do II Workshop Brasileiro de Bioinformática, Macaé, pp. 97–102 (2003)

    Google Scholar 

  • Ribeiro, C.C., Vianna, D.S.: A hybrid genetic algorithm for the phylogeny problem using path-relinking as a progressive crossover strategy. Int. Trans. Oper. Res. 16, 641–657 (2009)

    Article  Google Scholar 

  • Ribeiro, C.C., Uchoa, E., Werneck, R.F.: A hybrid GRASP with perturbations for the Steiner problem in graphs. INFORMS J. Comput. 14, 228–246 (2002)

    Article  MathSciNet  Google Scholar 

  • Ribeiro, C.C., Rosseti, I., Vallejos, R.: On the use of run time distributions to evaluate and compare stochastic local search algorithms. Lect. Notes Comput. Sci. 5752, 16–30 (2009)

    Article  MathSciNet  Google Scholar 

  • Rubinstein, R.Y., Kroese, D.P.: The Cross Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Machine Learning. Springer, Berlin (2004)

    MATH  Google Scholar 

  • Scaparra, M., Church, R.: A GRASP and path relinking heuristic for rural road network development. J. Heuristics 11, 89–108 (2005)

    Article  MATH  Google Scholar 

  • Vallada, E., Ruiz, R.: Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem. Omega 38, 57–67 (2010)

    Article  Google Scholar 

  • Zhang, G.Q., Lai, K.K.: Combining path relinking and genetic algorithms for the multiple-level warehouse layout problem. Eur. J. Oper. Res. 169, 413–425 (2006)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Universidade Federal Fluminense, Rua Passo da Pátria 156, Niterói, RJ, 24210-240, Brazil

    Celso C. Ribeiro

  2. Algorithms and Optimization Research Department, AT&T Labs Research, 180 Park Avenue, Room C241, Florham Park, NJ, 07932, USA

    Mauricio G. C. Resende

Authors
  1. Celso C. Ribeiro
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mauricio G. C. Resende
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Celso C. Ribeiro.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ribeiro, C.C., Resende, M.G.C. Path-relinking intensification methods for stochastic local search algorithms. J Heuristics 18, 193–214 (2012). https://doi.org/10.1007/s10732-011-9167-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10732-011-9167-1

Keywords

Search

Navigation