## 3 Routing Problems
### Travelling Salesman Problem  
The _Travelling Salesman Problem_ (TSP) [8; 62] is mathematically similar to the assignment problem model, differing only in one additional constraint, but the meaning of the decision variables \(x_{ij}=0\) is different. It is formulated as follows: Given \(n\) cities and distances among them, the objective is to find a round trip through all cities with a minimum length (alternatively, with a minimum total transportation cost).  
Since the starting city 1 is fixed, the number of routes is given by the permutations of cities 2, 3, \(\ldots\), \(n\), and is therefore equal to \((n-1)!\). If there are no one-way segments anywhere in the transportation between cities, routes in reverse order of cities do not affect the length, and then we can reduce the number of routes to \((n-1)!/2\), but still the time complexity of exploring all routes is \(\mathcal{O}(n!)\).  
If we denote by \(c_{ij}\) the distance between cities \(i\) and \(j\) (alternatively, the price of transportation between cities \(i\) and \(j\)), \(x_{ij}\) a binary decision variable that takes the value 1 when city \(j\) on the route immediately follows city \(i\), otherwise it takes the value 0, \(\delta_{i}\) is the order of city \(i\) on the route, then the Travelling Salesman Problem can be formulated as follows:  
\[z=\sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}x_{ij}\rightarrow\min \tag{5}\]subject to  
\[\sum_{i=1}^{n}x_{ij}=1,\ j=1,\,\ldots,\,n \tag{6}\]  
\[\sum_{j=1}^{n}x_{ij}=1,\ i=1,\,\ldots,\,n \tag{7}\]  
\[\delta_{i}-\delta_{j}+nx_{ij}\leq n-1,\ i\
eq j,\ i=2,\,\ldots,\,n,\ j=2,\, \ldots,\,n \tag{8}\]  
\[x_{ij}\in\{0,1\},\ i=1,\,\ldots,\,n,\ j=1,\,\ldots,\,n \tag{9}\]  
Constraints (6) and (7) ensure that each city (vertex of the graph) is traversed exactly once (entered and left exactly once); the system of subtour elimination constraints (8), referred to in the English literature by [PERSON], [PERSON], and [PERSON] as _MTZ constraints_, prevents the formation of subtours, as we will show below in Theorem 1.  
Equation (8) follows from the following reasoning:  
(i) If \(x_{ij}=1\), then \(j\) is the immediate successor of \(i\), and if \(\delta_{i}=t\), then \(\delta_{j}=t+1\). Hence, \(\delta_{i}-\delta_{j}+nx_{ij}=t-(t+1)+n=n-1\).  
(ii) If \(x_{ij}=0\), then \(\delta_{i}-\delta_{j}+nx_{ij}=\delta_{i}-\delta_{j}\) and this difference in the order of the cities in the route for \(i\
eq j\) can be at most equal to \(n-1\).  
From (i) and (ii), a common conclusion \(\delta_{i}-\delta_{j}+nx_{ij}\leq n-1\) already follows, which, for all combinations of feasible values of \(i\) and \(j\), is expressed by inequality (8).  
Without the constraint (8), constraints (6) and (7) are satisfied by splitting the route into several subtours, e.g., for 15 vertices, the two conditions mentioned above are satisfied by the subtours \(1-3-7-9-12-1,2-4-10-11-13-15-2\) and \(5-6-8-14-5\).  
**Theorem 1**: ([PERSON], [PERSON], [PERSON]) _The variables \(x_{ij}\in\{0,1\},\ i=1,\,\ldots,\,n,\ j=1,\,\ldots,\,n\) satisfying constraints (6) and (7) form a Hamiltonian circle if and only if the subtour elimination constraints (8) are satisfied._  
Proof: Suppose that \(x_{ij}\) satisfies the subtour elimination constraints but does not form a Hamiltonian circle. Then \(x_{ij}\) due to (6) and (7) form at least two subtours, one containing the initial vertex \(1\) and another without it. Let \(S\) be a subtour that does not contain vertex \(1\) and let \(E(S)\) be the set of edges in \(S\). Summing the conditions over the edges of \(E(S)\) we get:  
\[\sum_{(i,j)\in E(S)}(\delta_{i}-\delta_{j}+nx_{ij})\leq(n-1)|E(S)|,\]  
since the values of \(\delta_{i}\) and \(\delta_{j}\) eliminate each other in this subtour, we get  
\[n|E(S)|\leq(n-1)|E(S)|,\]  
which is a contradiction.  
Assume now that \(x_{ij}\) forms a Hamiltonian circle. If \(1\) is the initial vertex of this circle, and for each vertex \(i\
eq 1\), \(\delta_{i}=k\), if \(i\) is the \(k\)th vertex of the Hamiltonian circle, then it is clear that the conditions (8) are satisfied.