The Co-Adaptive Neural Network Approach to the Euclidean Travelling Salesman Problem (with E.M. Cochrane), Neural Networks, vol.16, 2003, 1499-1525

In this paper we consider the Euclidean Travelling Salesman Problem (ETSP). This is the problem of finding the shortest tour around a number of cities where the cities correspond to points in the Euclidean plane and the distances between cities are given by the usual Euclidean distance metric.

We present a review of the literature with respect to neural network approaches for the ETSP, and the computational results that have been reported. Based upon this review we highlight two areas that are, in our judgement, currently neglected/lacking in the literature. These are:

Drawing upon our literature survey this paper presents a new Self-Organising Neural Network approach, called the Co-Adaptive Net, which involves not just unsupervised learning to train neurons, but also allows neurons to co-operate and compete amongst themselves depending on their situation. Our Co-Adaptive Net algorithm also includes a number of algorithmic mechanisms that, based upon our literature review, we consider to have contributed to the computational success of previous algorithms.

Results for 91 publicly available standard ETSP's are presented in this paper. The largest of these problems involves 85900 cities. This paper presents:

Drawing upon computational results produced as a result of the DIMACS TSP Challenge, we highlight the fact that none of the current neural network approaches for the ETSP can compete with state of the art Operations Research heuristics. We discuss why we consider continuing to study and develop neural network approaches for the ETSP to be of value.

Keywords: Euclidean Travelling Salesman Problem; Self-Organising Neural Network; Co-Adaptive Net Algorithm

J E Beasley