Groupe d’études et de recherche en analyse des décisions


Band: New Tour Improvement Heuristics for the TSP in the Euclidian Plane


New tour improvement heuristics are described and studied from the point of view of their performance on random and real instances. They are compared to the popular 2-opt method and shown to equal or surpass the latter both in accuracy and in running time. The new heuristics are based on a novel idea for defining point re-insertions; they are particularly effective when used on initial tours created with the space filling curve algorithm. The combination of space filling curve initial tours and BAND seems very effective in finding good, very fast tours over large problems for which the 2-opt heuristic is prohibitively slow and less effective.

, 18 pages