Traveling Salesman Problem

TRAVELING SALESMAN PROBLEM

Convex Hull Algorithm

(Stewart, Bodin)

The convex hull is the smallest convex polygon completely enclosing a set of points.

The concept of convex hull is illustrated in the next figure:

The convex hull algorithm is as follows:

Step 1. Form the convex hull of the set of nodes and use this as an initial sub-tour
Step 2. For each node r not in the sub-tour yet, find (i, j) such that c_ir + c_rj - c_ij is minimal
Step 3. For all (i , j, r) found in Step 2, determine (i^*, r^*, j^*) such that is minimal
Step 4. (Insertion step) Insert node r^* in sub-tour between nodes i^* and j^*.
Step 5. If all the nodes are added to the tour, stop. Else go to step 2

Worst Case Behavior:

Worst case of this algorithm in general is not known.

Number of Computations:

The convex hull insertion algorithm is

Note:

It has been shown that if the costs c_ij represent Euclidean distance and H is the convex hull of the nodes in the 2-dimensional space, then the order in which the nodes on the boundary of H appear in the optimal tour will follow the order in which they appear in H (Eilon, Watson-Gabdy, Christofides, 1971).

Considering our illustration above, the solution of the traveling salesman problem can be seen satisfying the given property: