Scatter Search and Path Relinking : A Tutorial on the Linear Arrangement Problem

1. Introduction

Scatter search (SS) was first introduced in Glover (1977) as a heuristic approach for general integer programming problems. SS systematically generates and updates a set of reference points that includes good solutions obtained by prior problem-solving efforts together with solutions that are screened to add diversity to the reference set. Path relinking (PR) was subsequently proposed in Glover (1989) and Glover and Laguna (1993) as an analog making use of neighborhood spaces in place of Euclidean spaces. Interesting relationships exist between the SS/PR approaches and the more recent particle swarm optimization methodology introduced by Kennedy and Eberhart (1995).

The SS and PR template (Glover, 1997) has served as a foundation for most of the SS and PR implementations to date, underscoring processes to take advantage of the flexibility of the SS and PR methodologies. Through these processes, each of the basic components can be implemented in a variety of ways and degrees of sophistication, and hence can be adapted conveniently to a variety of different problem settings. Advanced options derive from the way that five pivotal elements of the methods are implemented. We can find a large number of papers on both the SS method and the PR method and their applications. Glover and Laguna (1997) provide overviews and a variety of references on these methods and the monographic book on Scatter Search (Laguna & Martí, 2003) together with the feature cluster of the European Journal of Operational Research (Martí, 2006), which includes 19 papers, provide the reader with the elements to design successful SS implementations. A recent survey of SS and PR methods appears in Resende et al. (2010).

The following principles summarize the foundations of the scatter search and path relinking methodologies as evolved from its origins:

• ⁃

  Useful information about the form (or location) of optimal solutions is typically contained in a suitably diverse collection of elite solutions.

• ⁃

  When solutions are combined as a strategy for exploiting such information, it is important to provide mechanisms capable of constructing combinations that extrapolate beyond the regions spanned by the solutions considered.

• ⁃

  The manner of combining solutions may be viewed as forming paths between (and beyond) them (using Euclidean spaces in SS and neighborhood spaces in PR). Each path results in introducing attributes of one elite solution into another, by a process where the trajectory for a given solution is influenced by the guidance of other solutions.

• ⁃

  It is likewise important to incorporate heuristic processes to map combined solutions into new solutions. The purpose of these combination mechanisms is to incorporate both diversity and quality.

• ⁃

  Taking account of multiple solutions simultaneously, as a foundation for creating combinations, enhances the opportunity to exploit information contained in the union of elite solutions.

A connection between the SS & PR approaches and particle swarm optimization (PSO) arises through the SS & PR strategy of combining solutions in a manner that may be interpreted as generating trajectories of selected elite solutions by reference to directions determined by other elite solutions (called guiding solutions in path relinking). In contrast to PSO, the solutions guided by SS & PR are initially generated and subsequently updated after the combination process by the application of associated heuristic or metaheuristic processes. PSO methods characteristically guide the progress of solutions in different streams of search by reference to the personal best of each stream and the global best overall streams.