Traveling Salesperson Problem
Instructor: An industrial engineering master’s student working for me says that this
exercise is a classic in his major. IE people specialize in scheduling. I asked him to explain
it to you. This is what he said about the exercise. NOTE: this explanation is for your
background only. It does NOT apply to this exercise.
The Traveling Salesperson Problem (TSP) is a deceptively simple combinatorial problem. It can
be stated very simply. A salesperson spends his time visiting “n” cities (or nodes) cyclically. In
one tour, he visits each city just once, and finishes up where he started. In what order should he
visit them to minimize the distance traveled?
You are a salesperson, and you must visit 20 cities spread across North America. You must visit
each city once and only once. The question is this: In what order should you visit them to
minimize the total distance that you have to travel?
The answer is that there is no simple answer. Reasonable people will make a reasonable choice
and accept a reasonably short path.
However, there is only one way to find the absolute shortest path, and that is to write down every
possible ordering of cities, compute the distance for each of those orderings, and pick the
shortest one.
How many orderings are there? They can be counted this way: