25 March 1998 Summary of the neural centroid TSP
Author Affiliations +
This paper summarizes a new interpretation of the Hopfield- Tank model as it applies to the Planar Traveling Salesman Problem (TSP). We demonstrate that the network solves the TSP in a 'centroidal' manner, that is, it provides tours that are similar to those obtained by the traditional centroid algorithm. The traditional centroid algorithm computes the center of mass of the cities and then orders the cities by the corresponding central angles. This algorithm gives excellent results on near-circular city configurations, and abysmal results on near-linear city configurations. We demonstrate that for up to 30 randomly generated cities the centroid results are very competitive with well known heuristics, such as the nearest city and 2-opt, but after about 40 cities the centroid algorithm produces poor results in comparison. We claim that this effect is inherent to the Hopfield-Tank model and explains why such networks do not scale up.
© (1998) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
William J. Wolfe, Frank A. Duca, "Summary of the neural centroid TSP", Proc. SPIE 3390, Applications and Science of Computational Intelligence, (25 March 1998); doi: 10.1117/12.304856; https://doi.org/10.1117/12.304856

Back to Top