Development of a novel crossover of hybrid genetic algorithms for large-scale traveling salesman problems

This article proposes a novel crossover operator of hybrid genetic algorithms (HGAs) with a Lin-Kernighan (LK) heuristic for solving large-scale traveling salesman problems (TSPs). The proposed crossover, tentatively named sub-tour recombination crossover (SRX), collects many short sub-tours from both parents under some set of rules, and reconnects them to construct a new tour of the TSP. The method is evaluated from the viewpoint of tour quality and CPU time for ten well-known benchmarks, e.g., dj38, qa194, …, ch71009.tsp, in the TSP website of the Georgia Institute of Technology. We compare the SRX with three conventional crossover operators, a variant of the maximal preservative crossover operator (MPX3), a variant of the greedy sub-tour crossover operator (GSX2), and a variant of the edge recombination crossover operator (ERX6), and show that the SRX succeeded in finding a better solution and running faster than the conventional methods mentioned above.