# A QUBO Model for the Traveling Salesman Problem with Time Windows
## 4 A QUBO Formulation for the TSPTW
Equality constraints such as Equations (21) and (22) are typically treated in QUBO by converting them into squared expressions. Hence, Equation (21) gives rise to the first time window constraint, denoted by \(W_{1}\) and given by  
\[W_{1}=\left(A_{p_{1}}+\sum_{k=1}^{K}kt_{k,i}-\sum_{v=1}^{n}x^{1}_{0,v}l_{v} \right)^{2}\, \tag{23}\]  
while Equation (22) gives rise to the \(i\)th time window constraint, denoted by \(W_{i}\) and given by  
\[W_{i}=\left(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}\right)^{2}\quad(2\leq i\leq n). \tag{24}\]  
If we replace \(A_{p_{1}}\) and \(A_{p_{i}}\) in the above equations by Equations (13) and (14), we derive the expanded forms of \(W_{1}\) and \(W_{i}\), \(2\leq i\leq n\), respectively. \[W_{1}=\left(\sum_{v=1}^{n}x^{1}_{0,v}c_{0,v}+\sum_{k=1}^{K}kt_{k,i}-\sum_{v=1 }^{n}x^{1}_{0,v}l_{v}\right)^{2}. \tag{25}\]  
\[W_{i}=\left(\sum_{d=1}^{i}\sum_{u=1}^{n}\sum_{ \begin{subarray}{c}v=1\\ v\
eq u\end{subarray} }^{n}x^{d}_{u,v}c_{u,v}+\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}\right)^{2}\quad(2\leq i\leq n). \tag{26}\]At this point, it is important to pause and confirm that the constraints in Equations (25) and (26) conform to the QUBO formulation requirements, in the sense that, after the expansion of the square, we get a sum of terms, where each term is the product of input data such as \(c_{u,v}\) or \(l_{v}\) and _at most two_ binary decision variables. The last time constraint concerns the binary variables \(t_{k,i}\). For each \(i\), \(1\leq i\leq n\), exactly one of the binary variables \(t_{k,i}\) is 1, where \(k\) ranges from 1 to \(K\). The meaning of this constraint is obvious: in every position of a feasible tour the time margin should be unique. Expressing this constraint is also straightforward:  
\[M_{i}=\left(1-\sum_{k=1}^{K}t_{k,i}\right)^{2}\quad(1\leq i\leq n)\;. \tag{27}\]  
Putting all the time constraints together results in the Hamiltonian \(H_{t}\):  
\[H_{t}=T(W_{1})+T\sum_{i=2}^{n}TWC_{i}+T\sum_{i=1}^{n}M_{i}\;. \tag{28}\]  
Therefore, to solve the TSPTW in the QUBO framework we must use the Hamiltonian \(H\) given below:  
\[H=H_{c}+H_{m}+H_{t}\;. \tag{29}\]  
As noted above, the constants \(B\), \(C\) and \(T\) appearing in the Hamiltonians are positive constants, which must be chosen according to our requirements. For instance, by setting \(C<B\), so as to ensure that the constraints of \(H_{c}\) are respected; similarly, setting \(T<B\) prioritizes the time windows constraints over the minimality of the tour. To show the form of the time windows constraints when the square is expanded, we apply the constraint in Equation (25) to network \(G_{2}\). We point out that for binary variables the following hold:  
\[(x_{u,p}^{i})^{2}=x_{u,p}^{i}\quad\text{and}\quad(t_{k,i})^{2}=t_{k,i}\;. \tag{30}\]  
We also recall the identity: \((a+b-c)^{2}=a^{2}+b^{2}+c^{2}+2 ab-2 ac-2 bc\). We use this identity to expand Equation (25), setting \(a=\sum_{o=1}^{n}x_{0,o}^{1}c_{0,p}\), \(b=\sum_{k=1}^{K}kt_{k,1}\), and \(c=\sum_{o=1}^{n}x_{0,o}^{1}l_{o}\). In our example, \(n=4\) and, to simplify somewhat the calculations, we take \(K=2\). With this understanding, we use Equation (15) to derive the formulas given below. Note that to improve the readability of the equations in this example, we have written in green color those terms that involve exactly one binary variable and in blue color those terms that involve exactly two binary variables. \[