algorithms.cheapest_feasible_insertion

algorithms.cheapest_feasible_insertion(H)[source]

CFI: Cheapest Feasible Insertion Algorithm: Heuristic.

Tour production:

1. Finds a sub-tour T_o with nodes { s } U {o_1,…,o_n} (1.5-factor optimal tour),

2. Iteratively adds in nodes in N_d: {d_1,…,d_n} through cheapest feasible edge insertion, and

  1. Adds edge {s,t} to path to produce final tour P.