Exploring GRASP-based Metaheuristics to solve the Traveling Salesman Problem

Exploring GRASP-based Metaheuristics to solve the Traveling Salesman Problem.

Daniel Tuyttens, Mohand Mezmaz, Gautier Vaillant, Nouredine Melab

In this work we consider the GRASP metaheuristic and the classical Traveling Salesman Problem. The paper proposes three variants of the GRASP method. These variants can be seen as a generalization of the construction phase used in GRASP. A first variant adds elements at the beginning and at the end of a partial solution unlike GRASP's construction phase which adds elements only at the beginning. The second variant builds group of partial solutions simultaneously unlike GRASP's construction phase which builds them separately. In a the third variant, a bound evaluates a partial solution like in a Branch-and-Bound procedure. Experiments on standard instances of the TSP show that some combinations of the variants improve, on average, the obtained results compared with the classical GRASP method. As a future work, we plan to test these variants on other optimization problems.