Alternative networks for solving the traveling salesman problem and the list-matching problem

Publisher Website
Google Scholar
Abstract
The authors demonstrate that Hopfield-type networks can find reasonable solutions to the traveling salesman problem (TSP) and the optimal list-matching problem (LMP). They show how to avoid the difficulties encountered by G.V. Wilson and G.S. Pawley (1988) by using a modified energy functional which yields better solutions to the TSP than J.J. Hopfield and D.W. Tank's (1985) original formulation. In addition, two fixed-parameter networks are described, one for the TSP and the other for the LMP. The performance of the network for the TSP is comparable to the performance of the modified energy functional formulation, while the network for the list-matching problem is shown to perform better than a simple heuristic method. A major feature of these two networks is that the problem-dependent cost data are contained entirely in the linear term of the energy functional-the quadratic part contains only constraint information. This feature has the advantage that all costs can be presented to the network as inputs rather than as connection weights, much reducing hardware complexity.