Multiple phase neighborhood Search—GRASP based on Lagrangean relaxation, random backtracking Lin–Kernighan and path relinking for the TSP |
| |
Authors: | Yannis Marinakis Athanasios Migdalas Panos M Pardalos |
| |
Institution: | (1) Decision Support Systems Laboratory, Department of Production Engineering and Management, Technical University of Crete, 73100 Chania, Greece;(2) Department of Industrial and Systems Engineering, Center for Applied Optimization, University of Florida, Gainesville, FL 32611, USA |
| |
Abstract: | In this paper, a new modified version of Greedy Randomized Adaptive Search Procedure (GRASP), called Multiple Phase Neighborhood
Search—GRASP (MPNS-GRASP), is proposed for the solution of the Traveling Salesman Problem. In this method, some procedures
have been included to the classical GRASP algorithm in order to improve its performance and to cope with the major disadvantage
of GRASP which is that it does not have a stopping criterion that will prevent the algorithm from spending time in iterations
that give minor, if any, improvement in the solution. Thus, in MPNS-GRASP a stopping criterion based on Lagrangean Relaxation
and Subgradient Optimization is proposed. Also, a different way for expanding the neighborhood search is used based on a new
strategy, the Circle Restricted Local Search Moves strategy. A new variant of the Lin-Kernighan algorithm, called Random Backtracking
Lin-Kernighan that helps the algorithm to diversify the search in non-promising regions of the search space is used in the
Expanding Neighborhood Search phase of the algorithm. Finally, a Path Relinking Strategy is used in order to explore trajectories
between elite solutions. The proposed algorithm is tested on numerous benchmark problems from TSPLIB with very satisfactory
results. |
| |
Keywords: | TSP GRASP ENS Metaheuristics Lagrangean relaxation and subgradient optimization |
本文献已被 SpringerLink 等数据库收录! |
|