Evolutionary divide and conquer (II) for the TSP
Christine L. Valenzuela · 1999
Results presented in recent papers demonstrate that it is possible to produce high quality solutions to TSP instances of up to several hundred cities using simple greedy heuristics when a Genetic Algorithm (GA) is used to perturb the city coordinates. The present paper extends the earlier studies to larger problems and a divide and conquer algorithm in the style of Richard Karp. Using a GA to perturb city coordinates in conjunction with a divide and conquer algorithm the feasibility of solving large problems to within a few percent of optimality is demonstrated. The exceptionally rapid execution times of Karp's algorithms together with their almost linear run-time scaling at O(nlogn) set them apart from most other heuristic algorithms. 1