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.
