Sheet 8: Local Search Heuristics for TSP

1. In a 3-opt local search algorithm for the TSP how many possible ways are there to add three new edges once three edges have been removed in order to re-obtain an Hamiltonian tour? Justify your answer.

2. Consider the traveling salesman problem defined on an incomplete graph. How could we encode the problem such that we can approach it with the construction heuristics and local search algorithms implemented for the complete graph version of the problem?

3. Consider the asymmetric TSP. How can we encode this problem into a symmetric TSP, such that we can approach it with the construction heuristics and local search algorithms implemented for the symmetric version of the problem?

4. In the code available in the git repository you find a file local_search.py, which contains an implementation of a 2 opt local search. Study the implementation and test the results when the local search is executed after different construction heuristics. Is the local search implemented in that file a first improvement or a best improvement? Does the 2-opt algorithm improve the results of the construction heuristics? How many steps (changes in the solutions) are executed? Which combination construction_heuristic + 2_opt leads to the best results (including a random initial solution)?

5. Compare the results of a first improvement 2-opt against those of a best improvement 2-opt procedure. Is the comparison the same across different initial solutions attained by different construction heuristics (including a random solution and a canonical sequence)?

6. Try to improve the 2-opt implementation from the previous point. Start by adding random choices. Then, improve its execution time by adopting some of the techniques explained in class.