Reference no: EM132289645

Assignment -

Table 1: Distances between major cities in Georgia (assumed to be symmetric).

Q1. Find a feasible traveling salesman tour using each of the following heuristics:

(a) Double tree;

(b) Christofides;

(c) Nearest neighbor (starting from Atlanta);

(d) Nearest insertion (starting from tour Atlanta - Savannah - Atlanta); and

(e) Savings method (using Atlanta as "depot").

In each case, show your workings, draw the tour, and report the length of the tour.

Q2. Find a lower bound on the length of an optimal traveling salesman tour using each of the following relaxations:

(a) Assignment Problem;

(b) Minimum Spanning Tree; and

(c) Minimum 1-Tree (with Atlanta as the special city).

In each case, draw the edges in the relaxation, and report the value of the lower bound.

Q3. Consider the following feasible solution: Atlanta - Columbus - Valdosta - Augusta - Savannah - Macon. Using the 2-exchange neighborhood, find a locally optimum tour.

Q4. Consider an instance of the TSP with n cities labeled 1, . . . , n. Let d_ij denote the distance between city i and city j, i = 1, . . . ,n; j = 1, . . . , n; i ≠ j. For every city i, let

D_i = min_{j= 1,. . . , n; j ≠ i}  d_ij, i = 1, . . . , n.

(a) Prove that the length of an optimal tour is at least as large as _i=1∑ⁿD_i.

(b) Compute the value of this lower bound (for the instance above).

Note - Need the assignment to show all work.