Share Email Print
cover

Proceedings Paper

Summary of the neural centroid TSP
Author(s): William J. Wolfe; Frank A. Duca
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

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.

Paper Details

Date Published: 25 March 1998
PDF: 7 pages
Proc. SPIE 3390, Applications and Science of Computational Intelligence, (25 March 1998); doi: 10.1117/12.304856
Show Author Affiliations
William J. Wolfe, Univ. of Colorado/Denver (United States)
Frank A. Duca, Univ. of Colorado/Denver (United States)


Published in SPIE Proceedings Vol. 3390:
Applications and Science of Computational Intelligence
Steven K. Rogers; David B. Fogel; James C. Bezdek; Bruno Bosacchi, Editor(s)

© SPIE. Terms of Use
Back to Top