Reference no: EM132389563
Question :
1. For any complete graph G=(N, E), consider c(S) to be the optimal TSP tour length for any subset of nodes S ⊂ N (where S≠ Ø). Suppose triangular inequality holds. Prove that for any subset of nodes S,
c(N)≥c(s)+(1/m) Σi∈N/Sqi(S)
where m |N/S|and qi(s) min j,k∈s{tji +tik - tjk} for ∀i∉ S .
2. In class we discussed the savings heuristic. Explain why the following constraints can or cannot be incorporated into the algorithm.
a) Distance constraint: each route must be at most L miles long;
b) Route size constraint: each route must visit at least m customers;
c) Mixed customer constraint: if some customers are labeled "odd" and the others labeled "even," customers with different labels cannot be visited on the same route.
3. The attached Excel file "data15points.xls" contains the x- and y-coordinates of 20 points in a 10-by-10 square. The distance between any two points can be measured by the Euclidean metric.
Use the MST-based heuristic (NOT the Christofide's algorithm) to solve the TSP problem for these 15 points. Please report the intermediate results and the TSP tour found. Hint: For this simple problem you may solve every step of the heuristic (e.g., finding the MST) manually.
4. The attached Excel file "data150cities.xls" contains the latitude and longitude information of the 150 largest U.S. cities. Complete the following tasks.
a. Determine a suitable way to compute the travel distance between any pair of cities. Explain your definition, and report the distances among Cities 1-10.
b. Implement a suitable solution algorithm (e.g., one of the insertion heuristics or an MST- based heuristic) to solve a TSP problem for these 150 cities. You may use any programming language of your choice (e.g., C++, C#, MATLAB, VBA). Please report the best TSP tour found, the computation time, and the computer platform used. Please also submit your algorithm source code by email.