Lesson 2

The Traveling Salesman Problem is another classic problem in combinatorial optimization. In it, a weighted graph is given, and the task is to find the shortest (or lightest) Hamiltonian cycle or path. It is convenient to assume that the graph is complete (if some edge is missing, we can assume it exists with a very large weight). Many problems that require finding an optimal order (i.e., permutation) of objects can be naturally formulated in terms of the Traveling Salesman Problem.

• Delivery.  A courier needs to deliver goods to several locations. In what order should they visit these locations to minimize total distance (or travel time)?

  



• Travel.  You want to visit several cities and know the flight costs between each pair. How can you spend the least amount of money?


• Holes in a circuit board.  A robot needs to drill many holes in a given circuit board. In what order should the drill visit the hole locations to complete the task as quickly as possible?
  

  



• Processing parts.  A machine needs to process \(n\) parts. To process part \(j\) after part \(i\), a reconfiguration time of \(t_{ij}\) units is required. What is the optimal processing order for all parts?