TRAVELING SALESMAN PROBLEM
Tour Construction Algorithms
Clark and Wright Savings
(Golden, 1977)
- Step 1. Select any node as the central node and index it as
1.
- Step 2. Compute savings sij = c1i
+ c1j - cij for i, j =2, 3,
..., n.
- Step 3. Order the savings from largest to smallest.
- Step 4. Starting at the top of the savings list and moving
downward, form larger sub-tours by linking appropriate nodes i
and j. Repeat until a tour is formed.
Worst Case Behavior:
Worst case of this algorithm in general is not known; however
for a modified version where at each step the best savings from
the last node added to the sub-tour is selected, the worst case
ratio is bounded by a linear function in 
(Golden, 1977).
Number of Computations:
The Clark and Wright savings algorithm is 
.
Note:
A modified application of Clark and Wright Savings Algorithm is
starting from each of the nodes in order, and seeing which starting
node gives the best result. However, this modified algorithm
is
.
