# A QUBO Model for the Traveling Salesman Problem with Time Windows
## 4 A QUBO Formulation for the TSPTW
: _To explain how Equations (13) and (14) can be used in practice, we examine the network \(G_{2}\)._  
_Equation (13) becomes_  
\[A_{p_{1}}=x_{0,1}^{1}c_{0,1}+x_{0,2}^{1}c_{0,2}+x_{0,3}^{1}c_{0,3}+x_{0,4}^{1} c_{0,4} \tag{15}\]  
_Equation (14) gives the following series of equations._  
\[ \begin{split} A_{p_{2}}&=\ \left(\underbrace{x_{0,1}^{1}c_{0,1}+x_{0,2}^{1}c_{0,2}+x_{0, 3}^{1}c_{0,3}+x_{0,4}^{1}c_{0,4}}_{A_{p_{1}}}\right)\\ &+x_{1,2}^{2}c_{1,2}+x_{1,3}^{2}c_{1,3}+x_{1,4}^{2}c_{1,4}+x_{2, 1}^{2}c_{2,1}+x_{2,3}^{2}c_{2,3}+x_{2,4}^{2}c_{2,4}\\ &+x_{3,1}^{2}c_{3,1}+x_{3,2}^{2}c_{3,2}+x_{3,4}^{2}c_{3,4}+x_{4, 1}^{2}c_{4,1}+x_{4,2}^{2}c_{4,2}+x_{4,3}^{2}c_{4,3}\end{split}  \tag{16}\]  
\[ \begin{split} A_{p_{3}}&=\ \bigg{(}\left(x_{0,1}^{1}c_{0,1}+x_{0,2}^{1}c_{0,2}+x_{0, 3}^{1}c_{0,3}+x_{0,4}^{1}c_{0,4}\right)\\ &+x_{1,2}^{2}c_{1,2}+x_{1,3}^{2}c_{1,3}+x_{1,4}^{2}c_{1,4}+x_{2, 1}^{2}c_{2,1}+x_{2,3}^{2}c_{2,3}+x_{2,4}^{2}c_{2,4}\\ &+x_{3,1}^{2}c_{3,1}+x_{3,2}^{2}c_{3,2}+x_{3,4}^{2}c_{3,4}+x_{4, 1}^{2}c_{4,1}+x_{4,2}^{2}c_{4,2}+x_{4,3}^{2}c_{4,3}\bigg{)}\\ &+x_{1,2}^{3}c_{1,2}+x_{1,3}^{3}c_{1,3}+x_{1,4}^{3}c_{1,4}+x_{2, 1}^{3}c_{2,1}+x_{2,3}^{3}c_{2,3}+x_{2,4}^{3}c_{2,4}\\ &+x_{3,1}^{3}c_{3,1}+x_{3,2}^{3}c_{3,2}+x_{3,4}^{3}c_{3,4}+x_{4, 1}^{3}c_{4,1}+x_{4,2}^{3}c_{4,2}+x_{4,3}^{3}c_{4,3}\end{split}  \tag{17}\]  
\[ \begin{split} A_{p_{4}}&=x_{0,1}^{1}c_{0,1}+x_{0,2}^{1 }c_{0,2}+x_{0,3}^{1}c_{0,3}+x_{0,4}^{1}c_{0,4}\\ &+x_{1,2}^{2}c_{1,2}+x_{1,3}^{2}c_{1,3}+x_{1,4}^{2}c_{1,4}+x_{2, 1}^{2}c_{2,1}+x_{2,3}^{2}c_{2,3}+x_{2,4}^{2}c_{2,4}\\ &+x_{3,1}^{2}c_{3,1}+x_{3,2}^{2}c_{3,2}+x_{3,4}^{2}c_{3,4}+x_{4, 1}^{2}c_{4,1}+x_{4,2}^{2}c_{4,2}+x_{4,3}^{2}c_{4,3}\\ &+x_{1,2}^{3}c_{1,2}+x_{1,3}^{3}c_{1,3}+x_{1,4}^{3}c_{1,4}+x_{2, 1}^{3}c_{2,1}+x_{2,3}^{3}c_{2,3}+x_{2,4}^{2}c_{2,4}\\ &+x_{3,1}^{4}c_{3,1}+x_{3,2}^{3}c_{3,2}+x_{3,4}^{3}c_{3,4}+x_{4, 1}^{4}c_{4,1}+x_{4,2}^{4}c_{4,2}+x_{4,3}^{4}c_{4,3}\end{split}  \tag{18}\]  
_The above equations demonstrate that, in every case, \(A_{p_{i}}\) can be expressed as a sum of terms, where each term is the product of an input variable \(c_{u,v}\) and exactly one binary decision variable \(x_{u,v}^{i}\)._  
The simplifying assumption of zero service time enables us to express the constraints imposed by the time windows of every customer as follows:  
\[A_{p_{1}}\leq\sum_{p=1}^{n}x_{0,p}^{1}l_{v}\, \tag{19}\]for the special case where \(i=1\), and  
\[A_{p_{i}}\leq\sum_{u=1}^{n}\sum_{ \begin{subarray}{c}v=1\\ v\
eq u\end{subarray} }^{n}x^{i}_{u,v}l_{v}\quad(2\leq i\leq n)\, \tag{20}\]  
for the general case where \(2\leq i\leq n\). The above expression may seem a little complicated, but, unfortunately, while \(A_{p_{i}}\) tells us the arrival time at the customer in the \(i\)th position of the tour, it does not tell us _which is_ this particular customer. We have to resort to the binary variables \(x^{i}_{u,v}\) to indirectly obtain this information. Inequality constraints such as these in Equations (19) and (20) are notoriously difficult to express within the QUBO framework. For an extensive analysis, we refer the interested reader to [29; 64; 76]. The approach which is most commonly used in the literature is to employ auxiliary binary variables, such as the binary variables \(t_{k,i}\) previously defined, to convert the inequality into an equality, and then proceed, as usual, by squaring the equality constraint. In our case, the first step is to express the inequalities in Equations (19) and (20) as  
\[A_{p_{1}}+\sum_{k=1}^{K}kt_{k,1}=\sum_{v=1}^{n}x^{1}_{0,v}l_{v}\, \tag{21}\]  
and  
\[A_{p_{i}}+\sum_{k=1}^{K}kt_{k,i}=\sum_{u=1}^{n}\sum_{ \begin{subarray}{c}v=1\\ v\
eq u\end{subarray} }^{n}x^{i}_{u,v}l_{v}\quad(2\leq i\leq n)\, \tag{22}\]  
respectively. In the above equalities, \(K\) is a positive constant appropriately chosen taking into consideration the specific time windows. A valid possible choice could be \(K=\max_{1\leq p\leq n}\{l_{v}\}\). Such a choice, while valid, would be unnecessarily big in most practical cases.