# Operations Research 09E: Traveling Salesman Problem – Integer Programming

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.

so, what you mean is that we have to create 2 auxiliary variables, Ui and Uj right?

What is N?

Solving TSP in Excel : https://www.youtube.com/watch?v=fQLBn6p6dp4

SOLVING LINEAR PROGRAMMING PROBLEMS IN EXCEL STEP BY STEP : https://www.youtube.com/watch?v=b2TM2ubAfbo

Hi Guys, please comment and let me know what you think about this Operations Research Open Course. Your feedback is really appreciated. If you enjoy the video, please subscribe and share. All my replies here are only related to the content in my own videos. I am afraid I won't be able to answer other questions. Thanks for your understanding.

What would be the values of Ui and Uj in the situation you mentioned of Traveling until city 3 and then return to 1?

Why the inecuation is not right?