A faster elastic-net algorithm for the traveling salesman problem

The elastic-net algorithm of R. Durbin and D. Willshaw (Nature, vol.326, p.689-91, 1987) for the traveling salesman problem works by deforming an elastic band as some of its points are attracted toward the cities. In each iteration, the influence of all cities on all points of the band is computed and the points displaced accordingly. A filtering mechanism is proposed. It is called the γ-filter for γ ε (0, 1), and allows points to be displaced under the attraction of only those cities that exert a significant influence on them, with performance advantages for both sequential and distributed parallel implementations. Experimental results are provided for instances of up to 1000 cities, revealing that the filtering mechanism does accelerate the elastic-net algorithm, without compromising the quality of its solutions. Results are compared with the Lin-Kernighan heuristic for the traveling salesman problem