Travelling Salesman Problem

Travelling Salesman Problem

Suppose a salesman wants to visit certain number of cities, say, $n$. Let $c_{ij}$ be the distance from city $i$ to city $j$. Then the problem of salesman is to select such a route that starts from his home city, passes through each city once and only once, and returns to his home city in the shortest possible distance. Such a problem is known as Travelling Salesman Problem.

Formulation

Suppose $x_{ij}=1$ if the salesman goes directly from city $i$ to city $j$, and $x_{ij}=0$ otherwise. Then the objective function is to

$$ \begin{equation*} \min z= \sum_{i=1}^n\sum_{j=1}^n x_{ij}c_{ij} \end{equation*} $$
subject to
$$ \begin{equation*} \sum_{j=1}^n x_{ij} =1,\; \text{ for } i=1,2,\ldots, n \end{equation*} $$

$$ \begin{equation*} \sum_{i=1}^n x_{ij} =1,\; \text{ for } j=1,2,\ldots,n \end{equation*} $$

where

$$ \begin{align*} x_{ij}&= \begin{cases} 1, & \text{if salesman goes from } i^{th} \text{ city to } j^{th} \text{ city}; \\ 0, & \text{Otherwise}. \end{cases} \end{align*} $$

With one more restriction that no city is visited twice before the tour of all cities is completed. The salesman cannot go from city $i$ to city $i$ itself. This possibility may be avoided by adopting the convention $c_{ii} = \infty$ which insures that $x_{ii}$ can never be one.

From \ To $A_1$ $A_2$ $\cdots$ $A_j$ $\cdots$ $A_n$
$A_1$ $\infty$ $c_{12}$ $\cdots$ $c_{1j}$ $\cdots$ $c_{1n}$
$A_2$ $c_{21}$ $\infty$ $\cdots$ $c_{2j}$ $\cdots$ $c_{2n}$
$\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$
$A_i$ $c_{i1}$ $c_{i2}$ $\cdots$ $c_{ij}$ $\cdots$ $c_{in}$
$\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$
$A_n$ $c_{n1}$ $c_{n2}$ $\cdots$ $c_{nj}$ $\cdots$ $\infty$

Apply the usual Hungarian method to find the optimal route. (It should be in cyclic order, i.e., no city should be visited twice).

Hope you enjoyed reading this article on Travelling Salesman problem.

You can read about how to solve the step by step procedure of Hungarian metod to solve assignment problem with restriction.

If you have any doubt or queries feel free to post them in the comment section.

VRCBuzz co-founder and passionate about making every day the greatest day of life. Raju is nerd at heart with a background in Statistics. Raju looks after overseeing day to day operations as well as focusing on strategic planning and growth of VRCBuzz products and services. Raju has more than 25 years of experience in Teaching fields. He gain energy by helping people to reach their goal and motivate to align to their passion. Raju holds a Ph.D. degree in Statistics. Raju loves to spend his leisure time on reading and implementing AI and machine learning concepts using statistical models.

Leave a Comment