New neurocomputational approaches for estimating road travel distances and for solving the euclidean traveling salesman problem

Abstract

Neural networks are among the most rapidly developing new scientific tools. There are numerous publications reporting their success in estimation and optimization. This work concentrates on both of these aspects and applies neural networks for solving two problems from operations research. One of the problems is the distance estimation problem, which mainly deals with the estimation of the length of the shortest road connecting two points on the earth surface. First, multilayer perceptrons have been adopted. Then, a neural clustering strategy which uses the principle of vector quantization has been utilized prior to the estimation. Thr results are superior than those reported in the literature. The other problem is the well-known Euclidean traveling salesman problem. It tries to determine the shortest tour passing throgh the cities of a given set by visiting aech city exactly once. A new adaptive scheme has been developed in order to solve this problem. The new approach incorporates explicit statistical information obtained from the city coordinates into the adaptation mechanism of Kohonen's self-organizing map. Results obtained for different problems are better than the previous ones. The new approach is then adapted to the solution of the Euclidean Hamiltonian path problem whose combination with the decomposition philosophy resulted in a highly all-neural Eulidean traveling salesman problem algorithm.