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

0, & \hbox{otherwise.} \end{array} \right. \end{equation

*{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).