A Greedy-Genetic Local-Search Heuristic for the Traveling Salesman Problem

The Travelling Salesman Problem (TSP) is one of the typical combinatorial optimization problems that is easy to describe but hard to solve. In this work, we present a novel solution that integrates a genetic algorithm, local-search heuristics, and a greedy algorithm. For the genetic algorithm we keep the evolutionary technique to generate children from parents, which uses operators like mutation, selection of the most fitted element, and crossover, but the latter is enhanced with a local-search heuristic. We also use the local search heuristic for its strong climbing ability, as well as to find local optima efficiently in the TSP space. The greedy algorithm is used to generate new greedy children from parents. The experimental evaluation shows that the optimization algorithm presented provides higher quality solutions for TSP with respect to previous genetic algorithms, within reasonable computational time.