# Dynamic Shortest Paths Methods for the Time-Dependent TSP
### Related Work  
Several generalizations of the ATSP have been considered in the literature, such as the TSP with time windows [10; 11], or the class of vehicle routing problems (VRPs) [12]. An interesting novel approach to the TSP and its variant is related to path-based formulations--the flow conservation constraints of the TSP ensure that every solution corresponds to a set of cycles in the underlying graph, making it possible to reformulate the problem in terms of path variables and solving it using a Branch-Cut-and-Price framework [13]. The same holds for the VRP [14] and other TSP-related problems [15]. By itself, this reformulation is not stronger than the original formulation due to [PERSON] et al. [16]. It is, however, possible to restrict the set of path variables in order to exclude paths which are not tours. Of course, any such modification alters the pricing problem, generally having an adverse effect on its computational tractability, requiring a balance between the quality of the relaxation and the computational effort required to solve the pricing problem. Promising approaches include the generation of \(k\)-cycle-free [17], as well as so-called ng paths [18].  
An early extension of the TSP to incorporate time-dependency, due to [PERSON] and [PERSON] [19], generalizes the travel time of an arc \((i,j)\in A\) to be sequence-dependent, i.e., a function \(c_{ij}(k)\) (\(k=1,\ldots,n\)). This sequence-dependent variant of the TSP, which we refer to as the SDTSP, has since been studied both theoretically [15] and experimentally [19; 20]. Notably, there is a correspondence between this sequence-dependent generalization of the TSP and the Minimum Latency Problem (MLP), which asks for a tour minimizing the sum of waiting times of customers. The correspondence has inspired some mixed-integer programming (MIP) formulations [21] for the MLP. The SDTSP is also closely related to identical machine scheduling, in particular \(P||\sum w_{i}T_{i}\) (see [22]).  
Some attempts have been made [23; 24] to solve the TDTSP itself using Branch-and-Cut algorithms, with the focus of exploiting a special structure of the time-dependent cost functions. Specifically, the travel-time model introduced in [25] assumes that travel times are determined by a piecewise constant travel speed function, leading to a three-index formulation where the total number of variables depends on the complexity of the travel speed functions in terms of the number of their break points. While the approach seems successful for highly structured travel speed functions, the computational tractability apparently degrades for more irregular instances (see, for instance, the computational results in [23]). Another approach, going by the name of Dynamic Discretization Discovery, has been proposed [26; 27] specifically for the TDTSP with time windows, which relies on iteratively refining a discretization of the time horizon according to optimal solutions of coarser discretizations determined during previous stages. The approach essentially substitutes one large integer program with several well-chosen smaller ones, exploiting the combination of time-dependent travel times and time windows. Conversely, we pursue an approach that does not rely on any special condition for the travel times.  
A preliminary version of this paper [28] explored the (ultimately unsuccessful) usage of machine-learning techniques in order to solve the TDTSP.