The Traveling Salesman Problem (TSP) is a fascinating optimization problem in which a salesman wishes to visit each of N cities exactly once and return to the city of departure, attempting to minimize the overall distance traveled. For the symmetric problem where distance (cost) from city A to city B is the same as from B to A, the number of possible paths to consider is given by (N-1)!/2. The exhaustive search for the shortest tour becomes very quickly impossible to conduct. Why? Because, assuming that your computer can evaluate the length of a billion tours per second, calculations would last 40 years in the case of twenty cities and would jump to 800 years if you added one city to the tour [1]. These numbers give meaning to the expression "combinatorial explosion". Consequently, we must settle for an approximate solutions, provided we can compute them efficiently. In this worksheet, we will compare two approximation algorithms, a simple-minded one (nearest neighbor) and one of the best (Lin-Kernighan 2-opt).