## 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.

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{equation} x_{ij}=\left{ \begin{array}{ll} 1, & \hbox{if salesman goes from i^{th} city to j^{th} city;} 0, & \hbox{otherwise.} \end{array} \right. \end{equation }$$ 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).