Study on a New Heuristic Crossover for the Traveling Salesman Problem

When the genetic algorithms were applied to practical problems, the use of heuristic genetic operators which appropriately incorporated the problem-specific knowledge could improve the performance of the algorithms. A new heuristic crossover operator for the traveling salesman problem was proposed. This crossover realized the construction of the offspring by inheriting the shortest edge which does not cause a cycle from the parents and producing the shortest edge. In this way, the length of offspring tour was usually shorter than their parents. The numerical simulations on geometric and random traveling salesman problems demonstrated that this heuristic crossover operator outperformed the order crossover operator and enhanced edge recombination crossover operator.