Article Preview
Top1. Introduction
Path relinking (PR) creates combinations of solutions by a process of generating paths between selected points in neighborhood space. The approach, as first suggested in Glover (1989) and then formalized and given the path relinking name in Glover and Laguna (1993), takes advantage of the path interpretation of solution combinations as a foundation for numerous applications in combinatorial optimization, as illustrated in the work of Reeves and Yamada (1998), Laguna and Marti (1999), Laguna and Marti (2003), Piñana et al. (2004), Ghamlouche, Crainic, and Gendreau (2004), James, Rego and Glover (2005), Glover, Ho and Gendreau (2006), Zhang and Lai (2006), Yagiura, Ibaraki and Glover (2006), Yagiura et al. (2007), Resende et al. (2010), Vallada and Ruiz (2010), Marti et al. (2011), Marinakis and Marinaki (2012), Ribeiro and Resende (2012), Wang et al. (2012), Marti and Sandoy (2012), Lai et al. (2013), Duarte, Martí and Gortazar (2013), Rahimi-Vahed et al. (2013), and Marti, Resende and Ribeiro (2013).
However, the principles of path relinking are somewhat broader than those employed in most of its implementations, and offer strategies for combinatorial and non-linear optimization that have not been fully examined. To clarify these aspects of PR we begin by reviewing a few observations from Glover (1996) that express the basic themes of path relinking and at the same time highlight the relevance of strategies that to date remain unexplored.
The character of paths generated by PR is easily specified by reference to attribute-based memory, as used in tabu search. In particular, it is only necessary to select moves in a neighborhood space that perform the following simple function: upon starting from an initiating solution, the moves must progressively introduce attributes contributed by a guiding solution (or reduce the distance between attributes of the initiating and guiding solutions). The process invites variation by interchanging the roles of the initiating and guiding solutions, inducing each to move simultaneously toward the other as a way of generating combinations. (When the goal for combining the solutions can be expressed as an optimization model, algorithmic processes may appropriately be incorporated to generate the moves.)