In this video, I’ll talk about how to formulate
the traveling salesman problem and its applications. An example of the typical traveling salesman
problem is described as follows. Joe owns business in 5 Cities.
At the end of each year he must take a tour to visit each of these cities exactly once
and come back to the city he starts. We want to find the best order of visiting
so that the total distance traveled will be minimized.
The traveling salesman problem is a combinatorial optimization problem and it has a finite number
of feasible solutions. Here is the distance matrix.
For example, from city 1 to city 2, the distance is c12=132 miles; from city 1 to city 3 the
distance is c13=217 miles, and so on. From city 1 to city 1, the distance c11=0.
However, we don’t want to make unnecessary travels from one city directly to itself because
we may get trapped in this city forever when we are trying to solve this problem. So we
assign a large positive number M, which represents a large penalty, to this element in the distance
matrix. The distance matrix is also called the cost
matrix sometimes and the elements represent the relevant traveling cost from one city
to another. A TSP is symmetric if the distance or cost
from i to j is equal to the distance or cost from j to i.
Otherwise, the problem is asymmetric. This situation may happen if from city i to city
j is just a one way road, and the returning trip has to take a different route.
We can formulate the TSP as a IP problem. Let’s defined the decision variables.
xij=1 if Joe travels from city i to city j; xij=0 otherwise, for i ≠ j, i, j=1,
2, …, N. N is the number of the cities. We also need to define an auxiliary variable
ui for each city i. This is a minimization problem. The objective
function is the total distance traveled. So it is the sum of the distance for each section
of the tour. The first constraint ensures that we must
arrive at a city just once. The second constraint ensures that we must
leave a city just once. The last constraint ensures there is no subtour.
An example of a subtour in a 5-city TSP is that we start from city 1, we go to city 2
and city 3, then we come back to city 1 without covering cities 4 or 5 at all.
For a TSP with N cities, the number of decision variables xij is N times N.
This equation will generate N equality constraints, so is this equation. This one will generate
(N-1) times (N-1) inequality constraints because we need to enumerate i and j from 2 to N.
Therefore, this formulation is very difficult to solve using the branch and bound method
because it involves a large number of decision variables and constraints when N is large.
I’ll introduce two more efficient methods to solve it in later videos.
One direct application of the TSP is to plan your trip to different cities.
There are some online tools that can help you do this.
One such tool can be found at this website, http://gebweb.net/optimap.
You can choose different cities and find the tour with the shortest traveling distance.
For example, I’m trying to find the best tour for seven cities: New York City, Pittsburgh,
Chicago, Washington DC, Boston, Atlanta, and Detroit.
The current order is obviously not optimal because it involves traveling back and forth
from east to west and from north to south. Using this online tool, I find that the best
solution is this: New York City, Boston, Pittsburgh, Detroit, Chicago, Atlanta, Washington DC,
and back to New York City. The duration is 1 day 21 hours and 17 minutes. The total length
is 2946.8 miles. Of course I can also go in the reverse direction
because this is approximately a symmetric TSP.
Another application of the TSP actually has nothing to do with salesmen.
Printed circuit boards have many small holes through which chips and other components are
wired. These holes are required to be made as rapidly
as possible by a moving drill. Finding the most efficient drilling sequence
is a TSP. Okay, that is how to formulate the TSP and
some applications. Thanks for watching.