# A QUBO Model for the Traveling Salesman Problem with Time Windows
## 4 A QUBO Formulation for the TSPTW
\tag{9}\]  
In the above Hamiltonians, \(B\) and \(C\) are positive constants, which must be appropriately chosen, i.e., \(C<B\), so as to ensure that the constraints of \(H_{c}\) are respected (see also [33]). Obviously, \(c_{u,v}\) is the cost for traversing the arc \((u,v)\). **Example 1**. : _To see the form of Equations (8) and (9) in the QUBO framework, we revisit our first example, the network \(\mathcal{G}_{1}\)._  
_First, we point out that for binary variables the following holds:_  
\[(x_{u,v}^{i})^{2}=x_{u,v}^{i}\;. \tag{10}\]  
_We also recall the identity: \((a-b-c-d)^{2}=a^{2}+b^{2}+c^{2}+d^{2}-2 ab-2 ac-2 ad+2 bc+2 bd+2 cd\). The expression \(\left(1-\sum_{v=1}^{3}x_{0,v}^{1}\right)^{2}\) in this case can be expanded as_  
\[\left(1-\sum_{v=1}^{3}x_{0,v}^{1}\right)^{2}=(1-x_{0,1}^{1}-x_{0,2}^{1}-x_{0,3}^{1})^{2}\]  
\[=1+(x_{0,1}^{1})^{2}+(x_{0,2}^{1})^{2}+(x_{0,3}^{1})^{2}-2x_{0,1}^{1}-2x_{0,2 }^{1}-2x_{0,3}^{1}+2x_{0,1}^{1}x_{0,2}^{1}+2x_{0,1}^{1}x_{0,3}^{1}+2x_{0,2}^{ 1}x_{0,3}^{1}\]  
\[=1+x_{0,1}^{1}+x_{0,2}^{1}+x_{0,3}^{1}-2x_{0,1}^{1}-2x_{0,2}^{1}-2x_{0,3}^{1}+ 2x_{0,1}^{1}x_{0,2}^{1}+2x_{0,1}^{1}x_{0,3}^{1}+2x_{0,2}^{1}x_{0,3}^{1}\]  
\[=1-x_{0,1}^{1}-x_{0,2}^{1}-x_{0,3}^{1}+2x_{0,1}^{1}x_{0,2}^{1}+2x_{0,1}^{1}x_{0,3}^{1}+2x_{0,2}^{1}x_{0,3}^{1}\]  
_In a similar way, we derive the following facts._  
\[\sum_{i=2}^{3}\left(1-\sum_{u=1}^{3}\sum_{ \begin{subarray}{c}v=1\\ v\
eq u\end{subarray} }^{3}x_{u,v}^{i}\right)^{2}\]  
\[=2-x_{1,2}^{2}-x_{1,3}^{2}-x_{2,1}^{2}-x_{2,3}^{2}-x_{3,1}^{2}-x_{3,2}^{3}-x_{ 1,2}^{3}-x_{1,3}^{3}-x_{2,1}^{3}-x_{2,3}^{3}-x_{3,1}^{3}-x_{3,2}^{3}\]  
\[+2x_{1,2}^{2}x_{1,3}^{2}+2x_  
_be the column vector with the binary decision variables, the column vector of the coefficients of the linear terms, and the square matrix of the coefficients of the quadratic terms, respectively. Then, the Hamiltonian \(H_{c}\) can be written more succinctly as \(H_{c}=10+L^{T}X+X^{T}\mathcal{Q}X\). \(L\) and \(Q\) contains the qubit biases and the coupling strengths to be used in a future execution of this example on the \(D\)-Wave computer._  
The above Hamiltonians are certainly not the end of the story in the case of the TSPTW, as, in their essence, they just encode the minimal cost of the Hamiltonian circuit. There are a lot more difficult time constraints to tackle in order to satisfy the time window of every customer. To this end, besides the binary variables \(x^{i}_{u,v}\), it will be necessary to use a second type of binary variables, denoted by \(t_{n,i}\), in order to express the _time margin_ of every customer. **Definition 5**. : _Given a feasible tour \(p_{0},p_{1},\ldots,p_{n},p_{n+1}\), suppose that the customer at position \(i\), where \(1\leq i\leq n\), is \(v\) with time window \([e_{v},l_{v}]\). We say that the **time margin** of the customer at position \(i\) is \(l_{v}-A_{p_{i}}\)._  
Clearly, for a feasible tour, the time margin for every position of the tour is non negative. We can now define the binary variables \(t_{k,i}\) as follows:  
\[t_{k,i}= \begin{cases}1,&\text{the time margin of the customer at position $i$ in the tour is $k$}\\ 0,&\text{otherwise}\end{cases} . \tag{12}\]  
We recall that, in the formulation of the TSPTW, the arrival time at the customer in the \(i\)th position of the tour, denoted \(A_{p_{i}}\), plays an important role (see [75]). Thus, we begin our analysis by showing how to express \(A_{p_{i}}\). Obviously, \(A_{p_{0}}=0\), thus it is only necessary to give the formula for \(A_{p_{i}}\), \(1\leq i\leq n\). We first observe that the customer at position \(0\) is always the depot (customer \(0\)), which results in the following, relatively simple, formula, for \(A_{p_{1}}\). \[A_{p_{1}}=\sum_{v=1}^{n}x^{1}_{0,v}c_{0,v}\;. \tag{13}\]The general case, i.e., when \(2\leq i\leq n\), is taken care by the next equation. \[A_{p_{i}}=\sum_{d=1}^{i}\sum_{u=1}^{n}\sum_{ \begin{subarray}{c}v=1\\ v\
eq u\end{subarray} }^{n}x_{u,v}^{d}c_{u,v}\quad(2\leq i\leq n). \tag{14}\]  
**Example 2**.