Traveling Salesman Problem

TRAVELING SALESMAN PROBLEM

The Traveling Salesman Problem is one of the most well known problems in operations research, computer science, and mathematics. The basic idea is basically trying to find the shortest cycle in a network such that all the nodes are visited and the minimum total distance is traveled. A more "technical" definition follows (Golden, Bodin, Doyle, Stewart, 1980):

" Let a network G = [N, A, C] be defined with N the set of nodes, A the set of branches, and C = [ c_ij] the matrix of costs. That is, c_ij is the cost of moving or the distance from node i to node j. The traveling salesman problem requires the Hamiltonian cycle in G of minimal cost (Hamiltonian cycle is a cycle passing through each node i in N exactly once). "

The terms that will be used frequently throughout this section are illustrated in the next figure:

Many algorithms have been proposed for the solution of this problem.

A typical solution process has several stages, where first an initial tour is constructed, then any remaining points are inserted, and then the existing tour is successively improved. There exist many possible algorithms for each step.

Create an initial sub-tour
- convex hull, sweep, nearest neighbor algorithms
Insert remaining free points
- cheapest, farthest insertion algorithms
Improve existing tour
- two, three, or Or exchange algorithms

The heuristics for the traveling salesman problem fall into the following classes:

Tour construction algorithms (creating an initial sub-tour and / or inserting remaining points if necessary)
Tour improvement algorithms (improving the existing tour)

Most of the time, a combination of algorithms from both of these classes is used. These are called composite procedures.

Below some of the most popular algorithms used will be explained. In each, we assume that

the cost is proportional to the Euclidean distance between two nodes of the network, thus the costs of arcs satisfy the triangle inequality, and the costs of arcs are symmetric

A detailed discussion of these algorithms can be found in (Golden, Bodin, Doyle, Stewart, 1980)