Skip to main content
Log in

A neural network algorithm for the multiple traveling salesmen problem

  • Published:
Biological Cybernetics Aims and scope Submit manuscript

Abstract

We developed an efficient neural network algorithm for solving the Multiple Traveling Salesmen Problem (MTSP). A new transformation of the N-city M-salesmen MTSP to the standard Traveling Salesmen Problem (TSP) is introduced. The transformed problem is represented by an expanded version of Hopfield-Tank's neuromorphic city-position map with (N + M-1)-cities and a single fictitious salesmen. The dynamic model associated with the problem is based on the Basic Differential Multiplier Method (BDMM) [26] which evaluates Lagrange multipliers simultaneously with the problem's state variables. The algorithm was successfully tested on many problems with up to 30 cities and five salesmen. In all test cases, the algorithm always converged to valid solutions. The great advantage of this kind of algorithm is that it can provide solutions to complex decision making problems directly by solving a system of ordinary differential equations. No learning steps, logical if statements or adjusting of parameters are required during the computation. The algorithm can therefore be implemented in hardware to solve complex constraint satisfaction problems such as the MTSP at the speed of analog silicon VLSI devices or possibly future optical neural computers.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Angel RD, Candle WL, Noonan R, Whinston A (1972) Computer assisted school bus scheduling. Manag Sci 18:279–288

    Google Scholar 

  2. Orloff DS (1974) Routing a fleet of M vehicles to/from a central facility. Networks 4:147–162

    Google Scholar 

  3. Christofides N, Eilon S (1969) An algorithm for vehicle dispatching problems. Oper Res Quart 20:309–318

    Google Scholar 

  4. Gavish B (1982) Topological design of centralized computer networks — formulations and algorithms. Networks 12:355–377

    Google Scholar 

  5. Gavish B (1983) Formulations and algorithms for capacitated minimal directed tree problems. J Assoc Comput Mach 30:118–132

    Google Scholar 

  6. Gavish B, Srikanth KN (1979) Mathematical formulations for the dial-a-ride problem. Graduate School of Management, University of Rochester (working paper, March 1979)

  7. Hopfield JJ, Tank DW (1985) “Neural” computation of decision in optimization problems. Biol Cybern 52:141–152

    MathSciNet  MATH  Google Scholar 

  8. Davis GW, Ansari A (1986) Sensitivity analysis of Hopfield neural net. IEEE First Conf Neural Networks 3:325–329

    Google Scholar 

  9. Bagherzadeh N, Kerola T, Leddy B, Brice R (1986) Parallel execution of the Traveling Salesman Problem. First Int Conf Neural Networks 3:317–325

    Google Scholar 

  10. Parsi Behzad, Behroog Kamangar-Parsi (1986) An efficient neural network for optimization. IEEE First Int Conf Neural Networks 3:785–790

    Google Scholar 

  11. Cervants JH, Hildebrant RR (1986) Comparison of three neuron-based computation schemes. IEEE First Int Conf Neural Networks 3:657–671

    Google Scholar 

  12. Simmes SD (1986) Program parallel computers using energy minimization algorithms. IEEE First Int Conf Neural Networks, 3

  13. Wilson GW, Pawley GS (1988) On the stability of the Traveling Salesman Problem algorithm of Hopfield and Tank. Biol Cybern 58:63–70

    Google Scholar 

  14. Toomarian N (1988) A concurrent neural network algorithm for the Traveling Salesman Problem. Third Conf Hypercube Concurrent Comput Appl Pasadena, CA (January 19–20, 1988) (submitted for publication)

  15. Posner E (1987) Workshop on Neural Network Devices and Applications, Jet Propulsion Laboratory, Pasadena, CA (February 18–19, 1987)

    Google Scholar 

  16. Denker JS (eds) (1986) Neural networks for computing. Am Inst Phys Conf Proc NY 151

  17. Mead CA (1988) Analog VLSI and neural systems. Addison-Wesley, Reading, Mass: (to be published)

    Google Scholar 

  18. Kirkpatrick S, Toulause G (1988) Configuration space analysis of Traveling Salesman Problems. J Phys 46:1277–1292

    CAS  PubMed  Google Scholar 

  19. Skiscim CC, Golden BL (1983) Optimization by simulated annealing: a preliminary computational study for the TSF. S. Roberts, J. Banks, B. Schneiser (eds) Proc 1983 Winter Simul Conf

  20. Cerny V, Dreyfus SG (1988) Thermodynamical approach to the Traveling Salesman Problem: an efficient simulation algorithm. J Opt Theor Appl 1(45) 1988

    Google Scholar 

  21. Bonomi E, Lutton J (1984) The N-city Traveling Salesman Problem: statistical mechanics and the metropolis algorithm. SIAM Rev 4(26) (October 1984)

  22. Spurlas N (1986) Statistical mechanics and the Traveling Salesman Problem. Europhys Lett 12:919–923

    Google Scholar 

  23. Felten E, Karlin S, Otto SW (1985) The Traveling Salesmen Problem on a hypercube MIMD computer. Proceedings of the 1985 Conference on Parallel Processing

  24. Szu H (1986) Fast simulated annealing. In: Denker J (eds) Neural networks for computing. American Institute of Physics, New York, pp 420–425

    Google Scholar 

  25. Hestenes MR (1975) Optimization theory. Wiley, New York

    Google Scholar 

  26. Platt JC, Barr AH (1988) Constrained differential optimization. Proceedings of the IEEE 1987 NIPS Conference: (to be published)

  27. Hopfield JJ (1984) Neurons with graded response have collective computational properties like those of two-state neurons. Proc Natl Acad Sci 31:3088–3092

    Google Scholar 

  28. Cohen MA, Grossberg S (1983) Absolute stability of global pattern formulation and parallel memory storage by competitive neural networks. IEEE Trans SMC 13:815–826

    Google Scholar 

  29. Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wacholder, E., Han, J. & Mann, R.C. A neural network algorithm for the multiple traveling salesmen problem. Biol. Cybern. 61, 11–19 (1989). https://doi.org/10.1007/BF00204755

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00204755

Keywords

Navigation