A Fast Evolutionary Algorithm for Traveling Salesman Problem

In this paper we proposed a new algorithm based on Inver-over operator, for traveling salesman problems (TSP). Inver-over is based on simple inversion; however, knowledge taken from other individuals in the population influences its action. In the new algorithm we use some new strategies including selection operator, replace operator and some new control strategy, which have been proved to be very efficient to accelerate the converge speed. We also use this approach to solve dynamic TSP. A dynamic TSP is harder than a general TSP, which is a NP-hard problem, because the city number and the cost matrix of a dynamic TSP are time varying, the algorithm to solve the dynamic TSP problem, which is the hybrid of EN and Inver-Over algorithm. Through the experiment, the new algorithm shows great efficiency in solving the static TSP and dynamic TSP.