Abstract

The work develops a new heuristic for the Travelling Salesman Problem, that aims at improving an existing solution for a given TSP instance. We look for improvements in the neighborhood of the solution on input, solving iteratively an ILP relaxation of the TSP model modified to minimize a distance function with the input, and a 1-tree subproblem that heuristically tries to enforce the relaxated constraint. The algorithm was coded in C and successfully tested over several instances.