Effective three-phase evolutionary algorithm to handle the large-scale colorful traveling salesman problem

This paper proposes a novel evolutionary algorithm to handle the colorful traveling salesman problem. The proposed evolutionary algorithm is a three-phase algorithm and utilizes two types of a new crossover and an enhanced local search. In the first phase, quality of population is increased by applying the first crossover. After the first phase, a priority value is computed to each color, based on the best tour of the first phase. During the second phase, priority values are updated when a solution with better cost than existing solutions in population is found. Priority values are used by the second type of crossover, which is used in the second phase. After the second phase, the problem is converted to the classical traveling salesman problem ingeniously, and finally, the third phase is a hybrid genetic algorithm, for which an enhanced local search algorithm is applied. Applying the second type of crossover and updating priority values are continued in the third phase. The proposed algorithm is effective and finds new bounds for many large-scale instances and outperforms other state-of-the-art heuristic in terms of accuracy and speed. In many cases, gaps between results obtained by the proposed algorithm and the other methods are high. For some large-scale instances, proposed algorithm is 44 times faster than the other state-of-the-art competitor, which is the current most efficient algorithm.