Consider a complete undirected graph G = (V,E), where V = {1,2,3,4,5,6}, and arc costs given in the table below satisfy the triangle-inequality. Use this information to answer questions 1 through 5 below.
From/To
1
2
3
4
5
6
1
0
19
85
57
84
66
2
19
0
71
53
65
49
3
85
71
0
47
57
68
4
57
53
47
0
89
83
5
84
65
57
89
0
24
6
66
49
68
83
24
0
1. Suppose, during some iteration of a construction heuristic for finding a TSP tour, the current tour is T={4-1-5-4}. Identify the node to insert next according to each of the following heuristics, and show your work (show what data you must use to make the decision how you make the decision based on the data).
a) Farthest insertion
b) Nearest insertion
2. Suppose, during some iteration of a construction heuristic for finding a TSP tour, the current tour is T={2-3-4-2} and node 1 has been identified as the node to insert next. Determine the minimum cost insertion location for node 1 in the current tour. Show the work required to identify this location.
3. Suppose, during some iteration of a construction heuristic for finding a TSP tour, the current tour is T={2-3-1-4-2}. The cost of this tour is c(T) = 266. Use cheapest insertion to determine which node should be inserted next, and where it should be inserted. Show all work required to identify this location. Additionally, provide the tour that will result once the insertion is performed, and its cost.
4. Determine the cost of tour {2,5,6,4,3,1,2}.
5. Suppose you wish to use the nearest neighbor heuristic to find a TSP tour on this graph and you initialize the path with the minimum cost edge in the network, edge (1,2) with cost 18. Then, the path is P={1-2} and the cost of the path is c(P) = 18. Show the next two iterations of nearest neighbor (that is, run the heuristic until a total of 4 nodes are in the path). Be sure to show all of your work at each step, along with the current path and its cost.
6. Recall that most TSP heuristics require a graph that is complete and undirected with arc costs that satisfy the triangle-inequality. We learned in Lecture – Traveling Salesman Problem that a graph that is connected and symmetric can be converted to one that is complete and undirected with arc costs that satisfy the triangle-inequality. Suppose you have the graph below as a starting point. Determine: (i) what edges need to be added to it, in order for it to be complete, and (ii) what should the cost on those new edges be, in order for the edge costs to satisfy the triangle-inequality?
7. Using the underlying graph from question 6, show that it is possible to conduct a 2-exchange on the tour below that is both feasible and improving, where edges (3,5) and (2,4) are the ones removed. You will need to specify what edges are added, the resulting tour, and the savings associated with the 2-exchange.
Read less
USA 
India