A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem

This paper presents a genetic algorithm (GA) for solving the traveling salesman problem (TSP). To construct a powerful GA, we use edge assembly crossover (EAX) and make substantial enhancements to it: (i) localization of EAX together with its efficient implementation and (ii) the use of a local search procedure in EAX to determine good combinations of building blocks of parent solutions for generating even better offspring solutions from very high‐quality parent solutions. In addition, we develop (iii) an innovative selection model for maintaining population diversity at a negligible computational cost. Experimental results on well‐studied TSP benchmarks demonstrate that the proposed GA outperforms state‐of‐the‐art heuristic algorithms in finding very high‐quality solutions on instances with up to 200,000 cities. In contrast to the state‐of‐the‐art TSP heuristics, which are all based on the Lin–Kernighan (LK) algorithm, our GA achieves top performance without using an LK‐based algorithm.