An efficient and scalable algorithm for the traveling salesman problem

This paper presents a genetic algorithm based on dynamic programming for solving large-scale instance of the Traveling Salesman Problem (TSP) to optimality. First, an improved dynamic programming algorithm is described to deal with large-scale data, and then it is used as crossover and mutation operator in the genetic algorithm. Simulation results show that this novel method with good stability can solve TSP with very-large-scale, effectively reduce the error rate, and improve the solution precision while keeping computational complexity relatively low.