Fixed set search applied to the traveling salesman problem
This is an incremental improvement for solving combinatorial optimization problems like the traveling salesman problem.
The paper introduces the Fixed Set Search (FSS), a population-based metaheuristic that adds a learning mechanism to GRASP by focusing on common elements in high-quality solutions rather than specific solutions, applied to the traveling salesman problem, and computational experiments show it finds significantly better solutions than GRASP and the dynamic convexized method.
In this paper we present a new population based metaheuristic called the fixed set search (FSS). The proposed approach represents a method of adding a learning mechanism to the greedy randomized adaptive search procedure (GRASP). The basic concept of FSS is to avoid focusing on specific high quality solutions but on parts or elements that such solutions have. This is done through fixing a set of elements that exist in such solutions and dedicating computational effort to finding near optimal solutions for the underlying subproblem. The simplicity of implementing the proposed method is illustrated on the traveling salesman problem. Our computational experiments show that the FSS manages to find significantly better solutions than the GRASP it is based on and also the dynamic convexized method.