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.