Genetic Algorithm for the Traveling Salesman Problem using Sequential Constructive Crossover Operator

This paper develops a new crossover operator, Sequential Constructive crossover(SCX), for a genetic algorithm that generates high quality solutions to the TravelingSalesman Problem (TSP). The sequential constructive crossover operatorconstructs an offspring from a pair of parents using better edges on the basis of theirvalues that may be present in the parents' structure maintaining the sequence ofnodes in the parent chromosomes. The efficiency of the SCX is compared asagainst some existing crossover operators; namely, edge recombination crossover(ERX) and generalized N-point crossover (GNX) for some benchmark TSPLIBinstances. Experimental results show that the new crossover operator is better thanthe ERX and GNX.