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

Mauricio G.C. Resende (), Celso C. Ribeiro (), Fred Glover () and Rafael Martí ()
Additional contact information
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

Chapter Chapter 4 in Handbook of Metaheuristics, 2010, pp 87-107 from Springer

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

Keywords: Path Relinking; Scatter Search (SS); Exploring Trajectories Connecting Elite Solutions; Intensification Strategies; Subset Generation Method (search for similar items in EconPapers)
Date: 2010
References: Add references at CitEc
Citations: View citations in EconPapers (15)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:isochp:978-1-4419-1665-5_4

Ordering information: This item can be ordered from
http://www.springer.com/9781441916655

DOI: 10.1007/978-1-4419-1665-5_4

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().