# A QUBO Model for the Traveling Salesman Problem with Time Windows
## 4 A QUBO Formulation for the TSPTW  
We begin this section by recalling that in the QUBO model we aim to minimize or maximize an expression of the form  
\[x^{T}Qx\quad\text{ or, in Dirac notation,}\quad\left\langle x\right|Q\left|x\right\rangle\, \tag{5}\]  
where \(x\) is an \(n\)-dimensional column vector of _binary decision_ variables, \(x^{T}\) is the transpose of \(x\), and \(Q\) is an \(n\times n\) square matrix containing constants. In the literature, the typical QUBO formulation of the standard TSP involves the use of a set of binary variables (see [33]). They are characterized as binary in the sense that they can take only the \(0\) or \(1\) value. Typically, they are denoted by \(x_{v,i}\), and their meaning is the following:  
\[x_{v,i}= \begin{cases}1,&\text{ customer $v$ is at position $i$ in the tour}\\ 0,&\text{otherwise}\end{cases} . \tag{6}\]  
In the case of the TSPTW, we have discovered it to be more advantageous to use binary variables parameterized by three integers: \(u,v\) and \(i\). A similar suggestion for the Vehicle Routing Problem can be found in [39]. Hence, in the rest of our analysis, we use the binary variables \(x_{u,v}^{i}\) defined next  
\[x_{u,v}^{i}= \begin{cases}1,&\text{ customers $u$ and $v$ are at consecutive positions $i-1$ and $i$ in the tour}\\ 0,&\text{otherwise}\end{cases} . \tag{7}\]  
As explained in the previous section, a feasible tour has the form \(\{p_{0},p_{1},\ldots,p_{n},p_{n+1}\}\). In this enumeration, \(p_{i}\) is the customer in the \(i\)th position of the tour. We always take for granted that \(p_{0}=p_{n+1}=0\) and each other customer appears exactly once. We recall the assumption of _zero service time_ at each customer, and, without loss of generality, we adopt another assumption that greatly reduces the final clutter of our QUBO expressions: for each customer \(v\), where \(0\leq v\leq n\), \(e_{v}=0\). With this understanding, we see that the parameters \(u\) and \(v\) range from \(0\) to \(n\) and the parameter \(i\) ranges from \(1\) to \(n+1\). Therefore, we can assert that:  
* For each \(i\), \(1\leq i\leq n+1\), exactly one of the binary variables \(x_{u,v}^{i}\) is \(1\), where \(u\) and \(v\) range freely from \(0\) to \(n\), with the proviso that \(u\
eq v\). As a matter of fact, when \(i=1\) and \(i=n+1\), we can be more precise. In the former case, exactly one of the binary variables \(x_{0,v}^{1}\) is \(1\), where \(v\) ranges from \(1\) to \(n\), and, in the latter case, exactly one of the binary variables \(x_{v,0}^{n+1}\) is \(1\), where \(v\) ranges from \(1\) to \(n\). * In addition to the above constraints, for each \(u\), \(1\leq u\leq n\), exactly one of the binary variables \(x_{u,v}^{i}\) is \(1\), where \(i\) ranges from \(2\) to \(n+1\) and \(v\) ranges from \(1\) to \(n\). Obviously, when \(i=n+1\), the only relevant decision variable is \(x_{u,0}^{n+1}\). * Symmetrically, we also have the constraint that for every \(v\), \(1\leq v\leq n\), exactly one of the binary variables \(x_{u,v}^{i}\) is \(1\), where \(i\) ranges from \(1\) to \(n\) and \(u\) ranges from \(1\) to \(n\). Again, we point out that, in case \(i=1\), the only relevant decision variable is \(x_{0,v}^{1}\). These constraints are encoded in the Hamiltonian \(H_{c}\). \[H_{c} =B\left(1-\sum_{v=1}^{n}x_{0,v}^{1}\right)^{2}+B\sum_{i=2}^{n}\left( 1-\sum_{u=1}^{n}\sum_{ \begin{subarray}{c}v=1\\ v\
eq u\end{subarray} }^{n}x_{u,v}^{i}\right)^{2}+B\left(1-\sum_{v=1}^{n}x_{v,0 }^{n+1}\right)^{2}\] \[+B\sum_{u=1}^{n}\left(1-\left(x_{u,0}^{n+1}+\sum_{i=2}^{n}\sum_{ \begin{subarray}{c}v=1\\ v\
eq u\end{subarray} }^{n}x_{u,v}^{i}\right)\right)^{2} \tag{8}\] \[+B\sum_{v=1}^{n}\left(1-\left(x_{0,v}^{1}+\sum_{i=2}^{n}\sum_{ \begin{subarray}{c}u=1\\ u\
eq v\end{subarray} }^{n}x_{u,v}^{i}\right)\right)^{2}\]  
Using the \(x_{u,v}^{i}\) binary variables, the requirement that the tour be minimal can be encoded by the following Hamiltonian \(H_{m}\). \[H_{m}=C\sum_{i=1}^{n+1}\sum_{u=0}^{n}\sum_{ \begin{subarray}{c}v=0\\ v\
eq u\end{subarray} }^{n}x_{u,v}^{i}c_{u,v}\;.