Pathlinking

Pathlinking, also known as path relinking, is a metaheuristic technique used in combinatorial optimization. It generates new candidate solutions by exploring paths in the solution space that connect two high-quality reference solutions, often elite solutions. The goal is to combine favorable attributes from both references and to diversify the search while pursuing high-quality results.

Construction method: select a pair of solutions, a starting solution and a guiding or ending solution. Identify the components that differ between them and construct a sequence of intermediate solutions by gradually replacing the differing components of the start toward the end. Depending on the implementation, this path may consider all possible stepwise replacements or sample a subset. Each intermediate solution is evaluated, and the best ones encountered along the path can be added to the elite set or used as starting points for local search.

Variants and usage: path relinking is used as a standalone strategy or as a component of larger metaheuristics, such as memetic algorithms, often in combination with local search methods like tabu search or simulated annealing. It has been applied to problems including the traveling salesman problem, vehicle routing, assignment, and scheduling. The method serves both as a diversification mechanism and as an intensified search by focusing on promising regions suggested by elite solutions.

Advantages and limitations: pathlinking leverages information from high-quality solutions to guide exploration, can produce high-quality offspring, and is adaptable to different problem encodings. Its drawbacks include computational cost from evaluating many intermediate solutions and sensitivity to the choice of reference solutions and path construction rules.

Origins and references: Path relinking originated in the work of Glover and Laguna on memory-based strategies for combinatorial optimization in the 1990s and remains a common operator in heuristic and metaheuristic frameworks.