IDEAS home Printed from https://ideas.repec.org/h/spr/isochp/978-1-4419-1665-5_4.html
   My bibliography  Save this book chapter

Scatter Search and Path-Relinking: Fundamentals, Advances, and Applications

In: Handbook of Metaheuristics

Author

Listed:
  • Mauricio G.C. Resende

    (AT&T Labs Research)

  • Celso C. Ribeiro

    (Universidade Federal Fluminense)

  • Fred Glover

    (University of Colorado and OptTek Systems, Inc.)

  • Rafael Martí

    (Universidad de Valencia)

Abstract

Scatter search is an evolutionary metaheuristic that explores solution spaces by evolving a set of reference points, operating on a small set of solutions while making only limited use of randomization. We give a comprehensive description of the elements and methods that make up its template, including the most recent elements incorporated in successful applications in both global and combinatorial optimization. Path-relinking is an intensification strategy to explore trajectories connecting elite solutions obtained by heuristic methods such as scatter search, tabu search, and GRASP. We describe its mechanics, implementation issues, randomization, the use of pools of high-quality solutions to hybridize path-relinking with other heuristic methods, and evolutionary path-relinking. We also describe the hybridization of path-relinking with genetic algorithms to implement a progressive crossover operator. Some successful applications of scatter search and of path-relinking are also reported.

Suggested Citation

  • Mauricio G.C. Resende & Celso C. Ribeiro & Fred Glover & Rafael Martí, 2010. "Scatter Search and Path-Relinking: Fundamentals, Advances, and Applications," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, chapter 0, pages 87-107, Springer.
    • Handle: RePEc:spr:isochp:978-1-4419-1665-5_4
    DOI: 10.1007/978-1-4419-1665-5_4
    as

    Download full text from publisher

    To our knowledge, this item is not available for download. To find whether it is available, there are three options:
    1. Check below whether another version of this item is available online.
    2. Check on the provider's web page whether it is in fact available.
    3. Perform a search for a similarly titled item that would be available.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Fernando Stefanello & Vaneet Aggarwal & Luciana S. Buriol & Mauricio G. C. Resende, 2019. "Hybrid algorithms for placement of virtual machines across geo-separated data centers," Journal of Combinatorial Optimization, Springer, vol. 38(3), pages 748-793, October.
    2. Ivorra, Benjamin & Mohammadi, Bijan & Manuel Ramos, Angel, 2015. "A multi-layer line search method to improve the initialization of optimization algorithms," European Journal of Operational Research, Elsevier, vol. 247(3), pages 711-720.
    3. Gambardella, L.M. & Montemanni, R. & Weyland, D., 2012. "Coupling ant colony systems with strong local searches," European Journal of Operational Research, Elsevier, vol. 220(3), pages 831-843.
    4. Benjamin C. Shelbourne & Maria Battarra & Chris N. Potts, 2017. "The Vehicle Routing Problem with Release and Due Dates," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 705-723, November.
    5. Leyman, Pieter & Vanhoucke, Mario, 2017. "Capital- and resource-constrained project scheduling with net present value optimization," European Journal of Operational Research, Elsevier, vol. 256(3), pages 757-776.
    6. Villegas, Juan G. & Prins, Christian & Prodhon, Caroline & Medaglia, Andrés L. & Velasco, Nubia, 2013. "A matheuristic for the truck and trailer routing problem," European Journal of Operational Research, Elsevier, vol. 230(2), pages 231-244.
    7. Lü, Zhipeng & Glover, Fred & Hao, Jin-Kao, 2010. "A hybrid metaheuristic approach to solving the UBQP problem," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1254-1262, December.
    8. Fred Glover & Gary Kochenberger & Moses Ma & Yu Du, 2022. "Quantum Bridge Analytics II: QUBO-Plus, network optimization and combinatorial chaining for asset exchange," Annals of Operations Research, Springer, vol. 314(1), pages 185-212, July.
    9. J. Terán-Villanueva & Héctor Fraire Huacuja & Juan Carpio Valadez & Rodolfo Pazos Rangel & Héctor Puga Soberanes & José Martínez Flores, 2015. "A heterogeneous cellular processing algorithm for minimizing the power consumption in wireless communications systems," Computational Optimization and Applications, Springer, vol. 62(3), pages 787-814, December.
    10. Qinghua Wu & Yang Wang & Fred Glover, 2020. "Advanced Tabu Search Algorithms for Bipartite Boolean Quadratic Programs Guided by Strategic Oscillation and Path Relinking," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 74-89, January.
    11. Ghaith Jaradat & Masri Ayob & Zulkifli Ahmad, 2014. "On the performance of Scatter Search for post-enrolment course timetabling problems," Journal of Combinatorial Optimization, Springer, vol. 27(3), pages 417-439, April.
    12. Benavides, Alexander J. & Ritt, Marcus & Miralles, Cristóbal, 2014. "Flow shop scheduling with heterogeneous workers," European Journal of Operational Research, Elsevier, vol. 237(2), pages 713-720.
    13. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    14. Francisco Casas & Claudio E. Torres & Ignacio Araya, 2022. "A heuristic search based on diversity for solving combinatorial problems," Journal of Heuristics, Springer, vol. 28(3), pages 287-328, June.
    15. Miguel A. González & Juan José Palacios & Camino R. Vela & Alejandro Hernández-Arauzo, 2017. "Scatter search for minimizing weighted tardiness in a single machine scheduling with setups," Journal of Heuristics, Springer, vol. 23(2), pages 81-110, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:isochp:978-1-4419-1665-5_4. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.