Elastic Net Method
for the Travelling Salesman Problem

Let us demonstrate the elastic net method on a simple example of solving a travelling salesman problem. The travelling salesman problem is a classical problem in the field of combinatorial optimization, concerned with efficient methods for maximizing or minimizing a function of many independent variables.

Given the positions of N cities, what is the shortest
closed tour in which each city can be visited once?

All exact methods known for determining an optimal route require a computing effort that increases exponentially with number of cities, so in practice exact solutions can be attempted only on problems involving a few hundred cities or less. The travelling salesman problem belongs to the large class of nondeterministic polynomial time complete problems.

The elastic net method has been applied to the travelling salesman problem. The essence of the method is:

Using an iterative procedure, a circular closed path is gradually elongated non-uniformly until it eventually passes sufficiently near to all the cities to define a tour.

A tour can be viewed as a mapping from a circle to the plane so that each city in the plane is mapped to by some point on the circle. We consider mappings from a circular path of points to the plane in which neighboring points on the circle are mapped as close as possible on the plane. This is a special case of the general problem of best preserving neighborhood relations when mapping between different geometrical spaces.

The algorithm is a procedure for the successive recalculation of the positions of a number of points in the plane in which the cities lie. The points describe a closed path which is initially a small circle centered on the center of the distribution of cities and is gradually elongated non-uniformly to pass eventually near all the cities and thus define a tour around them. Each point on the pass moves under the influence of two types of force:

1. the first moves it towards those cities to which it is nearest;

2. the second pulls it towards its neighbors on the path, acting to minimize the total path length.

By this means, each city becomes associated with a particular section on the path. The tightness of the association is determined by how the force contributed from a city depends on a distance, and the nature of this dependence changes as the algorithm progresses. Initially all cities have roughly equal influence on each point on the path. Subsequently, longer distance become less favored, and each city gradually becomes more specific for the points on the path closest to it.

THE TRAVELLING SALESMAN PROBLEM

---

If you were using a Java-enabled browser, you would see Travelling Salesman Problem demonstration instead of this paragraph.

---

More detailed description of the method you can find in:
R.Durbin, D. Willshaw, "An Analogue Approach to the Travelling Salesman Problem Using an Elastic Net Method", Nature, v.326, n.16, April 1987, p.689.