# A QUBO Model for the Traveling Salesman Problem with Time Windows
## 3 The Classical Formulation of the TSPTW  
In this section, we give the formal definition of the classical TSPTW. Our presentation follows [PERSON] and [PERSON] [75], which is pretty much standard in the relative literature.  
Definition 1: Let \(G=(N,A)\) be a directed graph, where \(N=\{0,1,\ldots,n\}\) is the finite set of nodes or, more commonly referred to in this context as _customers_, and \(A=N\times N\) is the set of arcs connecting the customers. For every pair \((u,v)\) of customers, there exists an arc in \(A\). \(A\) tour _is defined by the order in which the customers are visited._  
A couple of assumptions facilitate the formulation of the TSPTW.  
Definition 2: Let customer 0 denote the depot and assume that every tour _begins_ and _ends_ at the depot. Each of the remaining \(n\) customers appears exactly once in the tour. We denote a tour as an ordered list \(\mathcal{P}=(p_{0},p_{1},\ldots,p_{n},p_{n+1})\), where \(p_{i}\) is the index of the customer in the \(i\)th position of the tour. According to our previous assumption, \(p_{0}=p_{n+1}=0\).  
**Definition 3**.: _For every pair \((u,v)\) of customers \(u,v\in N\), there is a cost \(c_{u,v}\), for traversing the arc \((u,v)\). This cost of traversing the arc from \(u\) to \(v\) generally consists of any service time at customer \(U\) plus the travel time from customer \(u\) to customer \(v\)._  
**Definition 4**.: _To each customer \(v\in N\), there is an associated time window \([e_{v},l_{v}]\), during which the customer \(v\) must be visited. We assume that waiting is permitted; a vehicle is allowed to reach customer \(v\) before the beginning of its time window, \(e_{v}\), but the vehicle cannot depart from customer \(v\) before \(e_{v}\)._  
_A tour is feasible if it satisfies the time window of each customer._  
In the literature, two primary TSPTW objective functions are usually considered  
* minimize the sum of the arc traversal costs along the tour; and
* minimize the time to return to the depot.  
In a way, the difficulty of the TSPTW stems from the fact that it is two problems in one: a traveling salesman problem and a scheduling problem. The TSP alone is one of the most famous NP-hard optimization problems, while the scheduling part, with release and due dates, adds considerably to the already existing difficulty. To verify that the tour is feasible, i.e., it satisfies the time windows, it is expedient to introduce the **arrival time** at the \(i\)th customer and the time at which **service** starts at the \(i\)th customer, which are denoted by \(A_{p_{i}}\) and \(D_{p_{i}}\), respectively. At this point, we make the important observation that \(D_{p_{i}}\) is the **departure time** from the \(i\)th customer in the case of **zero service time**. The assumption of zero service time is widely used in the literature in order to simplify the problem, and, thus, we too follow this assumption in our presentation.  
The classical formulation of the TSPTW can be summarized by the next relations (see also [75]).  
\[\min\sum_{i=1}^{n+1}c_{p_{i-1},p_{i}} \tag{1}\]  
In Equation (1), we assume that \((p_{0},p_{1},\ldots,p_{n},p_{n+1})\) is a feasible tour. This means that, besides the assumptions previously outlined, the following hold.  
\[D_{p_{0}}=0. \tag{2}\]  
\[A_{p_{i}}=D_{p_{i-1}}+c_{p_{i-1},p_{i}}\quad(1\leq i\leq n+1). \tag{3}\]  
\[D_{p_{i}}=\max\{A_{p_{i}},e_{p_{i}}\}\quad(1\leq i\leq n). \tag{4}\]