ABSTRACT
Cheapest Insertion Algorithm 1. Start with a partial tour T consisting of three arbitrarily chosen customers. 2. For each customer v not currently on the tour, compute the length l(v) of the short-
est detour induced by the insertion of v between two consecutive customers in T. 3. Choose the customer v not currently on T that minimizes l(v) and insert v on T.
