A neural network for solving the travelling salesman problem on the basis of city adjacency in the tour

A neural network for solving the traveling salesman problem (TSP) is proposed. The network is a modified version of the network suggested by J.J. Hopfield and O.W. Tank (1985) In the network of Hopfield and Tank, a neuron U_x,i denotes city x occupying position i in the tour. This results in a network that, in general, is incapable of performing a shift in position for a number of adjacent cities, since this would temporarily increase the energy of the system. In the proposed network, a neuron U_{x, y} indicates whether or not cities x and y are adjacent in the tour. An extra layer is added for the detection and elimination of closed subtours. This approach seems to have four major advantages: (a) computer simulations show a faster and more natural convergence of the network towards a configuration that represents a solution; (b) larger instances of the TSP can be solved readily; (c) the energy function is simplified; and (d) a general hardware implementation is possible because the distance terms occur only in the external inputs