FLEXMAP-a neural network for the traveling salesman problem with linear time and space complexity
- 1 January 1991
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 929-934 vol.2
- https://doi.org/10.1109/ijcnn.1991.170519
Abstract
The authors present a self-organizing 'neural' network for the traveling salesman problem. It is partly based on the model of Kohonen. The proposed approach differs from former work in this direction as no ring structure with a fixed number of elements is used. Instead a small initial structure is enlarged during a distribution process. This makes it possible to replace the central search step, which normally needs time O(n), by a local procedure that needs time O(1). Since the total number of search steps that must be performed is O(n) the runtime of the model scales linearly with problem size. This is better than every known neural or conventional algorithm. The path lengths of the solutions generated are less than 10% longer than the optimum solutions of solved problems from the literature.Keywords
This publication has 9 references indexed in Scilit:
- Unsupervised clustering with growing cell structuresPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A study of the application of Kohonen-type neural networks to the Travelling Salesman ProblemBiological Cybernetics, 1991
- An improved elastic net method for the traveling salesman problemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- An analogue approach to the travelling salesman problem using an elastic net methodNature, 1987
- Optimization of a 532-city symmetric traveling salesman problem by branch and cutOperations Research Letters, 1987
- Self-organized formation of topologically correct feature mapsBiological Cybernetics, 1982
- Distribution Management-Mathematical Modelling and Practical AnalysisIEEE Transactions on Systems, Man, and Cybernetics, 1974
- An Effective Heuristic Algorithm for the Traveling-Salesman ProblemOperations Research, 1973
- A man-machine approach toward solving the traveling salesman problemCommunications of the ACM, 1971