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

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 list-matching problem. The performance of the fixed-parameter network for the TSP is comparable to the performance of the modified formulation mentioned which the fixed-parameter 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 is 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, eliminating the necessity of modifying the internal parameters with each new set of data. This results in a substantial reduction in hardware complexity.