A neural network for solving the travelling salesman problem on the basis of city adjacency in the tour
A. Joppe, H. R. A. Cardon, Jan C. Bioch · 1990
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 Ux,idenotes cityxoccupying positioniin 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 Ux,yindicates whether or not citiesxandyare 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