Self-organizing neural networks and various Euclidian traveling salesman problems

Algorithms to find excellent approximate solutions in various Euclidian traveling salesman problems are presented. The method is based on learning and self-organization of neural networks. The solutions are obtained by the evolution of closed curves where neurons are placed. The position of each city is fed into the learning mechanism one by one. This process has a relationship to neighborhood search and pattern clustering. The USA-532 set is used for the main benchmarking. This city set is extremely nonuniform. The exact solution requires a linear programming package and hours of supercomputer run time. But, the presented method here is very intuitive and simple. All computation is executable by a conventional workstation. Obtained solutions are less than 4% excess of the true optima. This is a better result than the simulated annealing. Further extended problems which have not been tried by traditional combinatorial methods are discussed. The cases include the N-person traveling salesman problem with city qualification on the same benchmark set. Even for such complicated problems, no structural change on the basic algorithm is needed. [In Japanese.]