A neural network algorithm for the multiple traveling salesman problem (Q1822984)

Each of N cities should be visited exactly once by one of M salesmen. By introduction of M-1 fictitious cities and suitable city-position matrix coding, the problem is reduced to the classical version of TSP. Energy function is derived, the minimization of which leads to the shortest total length and expresses admissibiity (constraint satisfaction) of the matrix code. By means of Lagrangian multipliers the minimization problem is converted to an unconstrained one; the multipliers are represented as activities of additional neurons. To ensure convergence of the gradient system, Basic Differential Multiplier Method is applied. With thes tools the problem proved to converge with up to 30 cities and 5 salesmen. As the network is not adaptive, the algorithms are relatively easy to implement in hardware.