Farthest Insertion to solve TSP - pgRouting/pgrouting GitHub Wiki

TRAVELING SALESMAN PROBLEM

http://www2.isye.gatech.edu/~mgoetsch/cali/VEHICLE/TSP/TSP003__.HTM

Insertion Algorithms (Rosenkrantz, Stearns, Lewis, 1974)

Farthest Insertion

This is a construction problem not an optimization problem and the results can typically be improved by adding an optimizer like simulated annealing or tabu search after initial construction.

  • Step 1. Start with a sub-graph consisting of node i only.
  • Step 2. Find node r such that cir is maximal and form sub-tour i-r-i.
  • Step 3. (Selection step) Given a sub-tour, find node r not in the sub-tour farthest from any node in the sub-tour; i.e. with maximal Crj
  • Step 4. (Insertion step) Find the arc (i, j) in the sub-tour which minimizes Cir + Crj - Cij . Insert r between i and j.
  • Step 5. If all the nodes are added to the tour, stop. Else go to step 3

Note how the bold sections differ from "nearest insertion".

Worst Case Behavior:

length_of_farthest_insertion_tour / length_of_optimal_tour <= 2*ln(n) + 0.16

Number of Computations:

The farthest insertion algorithm is O(n^2).