Abstract: A new hybrid Path Relinking(PR) algorithm is presented. The algorithm combining the solution construction mechanism of Greedy Randomized Adaptive Search Procedure(GRASP) into PR is designed. It considers both solution quality and diversification. The process of the path relinking phase is to introduce progressively attributes of the guiding solution into the initial solution to obtain the high quality solution as quickly as possible. Moreover, the algorithm adopts the dynamic updating strategy of the reference set to accelerate the convergence towards high-quality regions of the search space. Experimental results show that the method is very efficient and competitive compared with the best existing methods in terms of solution quality.
Traveling Salesman Problem(TSP),
Greedy Randomized Adaptive Search Procedure(GRASP),
Restricted Candidate List(RCL),