A multiple heuristic search algorithm for solving traveling salesman problem

This research was carried out to solve the traveling salesman problem (TSP) using a multiple heuristic search algorithm. Two main operations of complete 2-opt (C2Opt) and smallest square (SS) were combined in a genetic algorithm (GA) and applied to the TSP. The C2Opt is based on the 2-Opt heuristic search, which can remove all crossed edges in the tour if the repeat times are sufficient. The SS selects the shorter edges than the C2Opt. The problem of the SS is that the city orders of the original tour were changed while the SS was applied, hence the crossed edges could not be removed completely. However, a reasonable result is presented by combining the C2Opt and the SS in the GA for the TSP in our experiment. Another two operations the deletion (DL) and the best part collector (BPC) are discussed. The DL was used for removing the duplicates from the population and the BPC was used for collecting the best part among the individuals to the elite individual.