A neural network algorithm for the multiple traveling salesman problem
type: Item
instance of: scholarly article
title: A neural network algorithm for the multiple traveling salesman problem
zbMATH Open document ID: 0679.68108
DOI: 10.1007/BF00204755
author: Yanyan Li
published in: Biological Cybernetics
publication date: 1989-01-01T00:00:00Z
review text: 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.
reviewed by: J.Horejs
Mathematics Subject Classification ID: 68Q80
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 49M99
zbMATH DE Number: 4114032
zbMATH Keywords: neural network
zbMATH Keywords: optimization
zbMATH Keywords: dynamic models
zbMATH Keywords: Hopfield network
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 4114032