## 2 State of the Art  
Let \(G=(V,A)\) be a directed graph, where \(V=\{1,2,\ldots,n\}\) is a set of vertices and \(A\subseteq V\times V\) a set of arcs. With each arch \((i,j)\in A\) is associated a travel time function \(\tau_{ij}(t)\) representing the time that a vehicle, departing from \(i\) at time instant \(t\), takes to traverse the arc and finally arrive at vertex \(j\). Let \(\mathcal{T}=[0,T]\) be the time horizon (e.g., an 8-h period of a typical working day). Given a start time \(t\) and path composed by a sequence of \(k\) nodes, i.e., \(p_{n}=(i_{0},i_{1},\ldots,i_{n})\) with \(i_{k}\in V\) and \(k=0,\ldots,n\), the time needed to travel from node \(i_{0}\) to node \(i_{n}\) can be computed recursively as:  
\[z(p_{k},t)=z(p_{k-1},t)+\tau_{i_{k-1},i_{k}}(t+z(p_{k-1},t)\quad k=1,\ldots,n\]  
and initialization \(z(p_{0},t)=0\). Without loss of generality, we assume that the travel time functions are piecewise linear and satisfy the first-in-first-out (FIFO) property, i.e., the arrival time is a strictly monotonic function of the starting time. [PERSON] and [PERSON] [36] proved that any continuous piecewise linear travel time function \(\tau_{ij}(t)\), satisfying the FIFO property, can be generated from the IGP model. In the IGP model the speed of the vehicle is not constant over the entire length of arc \((i,j)\) but it changes when the boundaries between two consecutive time periods is crossed. For any arc the time horizon \(\mathcal{T}=[0,T]\) is divided into \(H_{ij}\) time slots \([T_{ijb},T_{ij(h+1)}]\), \(h=0,1,\ldots,H_{ij}-1\). Let \(v_{ijb}\) be the travel speed between node \(i\) and node \(j\) in time slot \(h\) and \(L_{ij}\) be the distance between the two vertices \(i\) and \(j\). They decomposed the travel speed for an arc \((i,j)\) as:  
\[v_{ijh}=\delta_{ijb}h_{h}u_{ij}, \tag{1}\]  
where:  
* \(u_{ij}\geq 0\) is the maximum travel speed across arc \((i,j)\in A\) in all times.
* \(0<b_{h}\leq 1\) is the best congestion factor during interval \(h\) (\([T_{h},T_{h+1}]\));
* \(0<\delta_{ijb}\leq 1\) is the degradation of the congestion factor of arc \((i,j)\) in time slot \(h\).  
The Time-Dependent Travelling Salesman Problem amounts to find a Hamiltonian tour of least total duration on a given time-dependent graph. [PERSON] et al. [19] proposed a lower bound for the TDTSP based on the IGP model. In particular, they proved that when \(\Delta=\min\limits_{i,j,h}\delta_{ijh}=1\) solving the time-dependent problem is equivalent to solve its time-invariant counterpart. In [36], the authors pointed out that in IGP model the relationship among travel speeds \(v_{ij}(t)\), times \(\tau_{ij}(t)\) and lengths \(L_{ij}\) can be expressed as follows:  
\[L_{ij}=\int_{t}^{t+\tau_{ij}(t)}v_{ij}(\mu)d\mu, \tag{2}\]  
where it is worth noting that the IGP parameters, \(L_{ij}\) and \(v_{ij}(t)\), can be multiplied by any positive common factor without changing the travel time functions \(\tau_{ij}(t)\). This implies that \(L_{ij}\) can be any positive number and, consequently, the speed factorization (1) is not uniquely defined. Indeed, Ref. [21] proved that there exists a different speed factorization for each value of \(u_{ij}\) such that \(u_{ij}\geq\max\limits_{h}v_{ijh}\). [PERSON] et al. [37] generalize all these considerations in order to improve the previous lower bounds.