TRAVELING SALESMAN PROBLEM
Insertion Algorithms
(Rosenkrantz, Stearns, Lewis, 1974)
Cheapest Insertion
- Step 1. Start with a sub-graph consisting of node i only.
- Step 2. Find node r such that cir
is minimal and form sub-tour i-r-i.
- Step 3. Find (i, j) in sub-tour and r
not, such that cir + crj - cij
is minimal. Insert r between i and j.
Note that the first two steps are identical to nearest insertion
Worst Case Behavior:
,(same as nearest insertion)
Number of Computations:
The cheapest insertion algorithm is
.
