Return to the (TSP) instance of Exercise 15-5(b). This time construct an approximately optimal tour by the Greedy Insertion strategy used on the KI Truck Routing application in Figure 15.1. Specifically begin with a 2-point tour 1–5–1.

Then at each iteration insert to unvisited point closest to the average of coordinates for nodes included so far.

(a) Justify the greedy standard of the algorithm to insert the nearest unvisited point.

(b) Compare your results to the optimum of Exercise 15-5

(b) and the heuristic solution 15-5(c).

(c) Discuss the advantages and disadvantages of employing a Greedy Insertion constructive method versus the tour extension strategy of Nearest Neighbor.