Summary of the neural centroid TSP

William J. Wolfe; Frank A. Duca

doi:10.1117/12.304856

25 March 1998 Summary of the neural centroid TSP

William J. Wolfe, Frank A. Duca

Proceedings Volume 3390, Applications and Science of Computational Intelligence; (1998) https://doi.org/10.1117/12.304856
Event: Aerospace/Defense Sensing and Controls, 1998, Orlando, FL, United States

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.

Citation Download Citation

William J. Wolfe and Frank A. Duca "Summary of the neural centroid TSP", Proc. SPIE 3390, Applications and Science of Computational Intelligence, (25 March 1998); https://doi.org/10.1117/12.304856

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available