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-ofthe-art
competitor, which is the current most efficient algorithm.