# Dynamic Shortest Paths Methods for the Time-Dependent TSP
###### Abstract  
The time-dependent traveling salesman problem (TDTSP) asks for a shortest Hamiltonian tour in a directed graph where (asymmetric) arc-costs depend on the time the arc is entered. With traffic data abundantly available, methods to optimize routes with respect to time-dependent travel times are widely desired. This holds in particular for the traveling salesman problem, which is a corner stone of logistic planning. In this paper, we devise column-generation-based IP methods to solve the TDTSP in full generality, both for arc- and path-based formulations. The algorithmic key is a time-dependent shortest path problem, which arises from the pricing problem of the column generation and is of independent interest--namely, to find paths in a time-expanded graph that are acyclic in the underlying (non-expanded) graph. As this problem is computationally too costly, we price over the set of paths that contain no cycles of length \(k\). In addition, we devise--tailored for the TDTSP--several families of valid inequalities, primal heuristics, a propagation method, and a branching rule. Combining these with the time-dependent shortest path pricing we provide--to our knowledge--the first elaborate method to solve the TDTSP in general and with fully general time-dependence. We also provide for results on complexity and approximability of the TDTSP. In computational experiments on randomly generated instances, we are able to solve the large majority of small instances (20 nodes) to optimality, while closing about two thirds of the remaining gap of the large instances (40 nodes) after one hour of computation.  
integer programming; traveling salesman problem; shortest path problem +
Footnote †: journal: _Algorithms_  
0000-0001-  
As for the planning of time-dependent tours, several extensions of the ATSP have been examined in the literature (see below). The resulting formulations are, however, generally focused on the structure of the time-dependent cost functions rather than that of the underlying network itself. Conversely, we study the time-dependent TSP (TDTSP for short) focusing on paths through the network, leading to different Branch-Cut-and-Price formulations with time-dependent shortest path problems being solved during the column generation.  
The TSP is very versatile in applications. For solving TSP, specialized IP methods have proven particularly fruitful. The importance of time-dependent cost functions is obvious at least for logistic applications. Thus, development of specialized IP methods for the TDTSP in full generality, with fully general time-dependence of the arc lengths, is of fundamental importance. To this end, we develop both arc- and path-based formulations for the TDTSP. Both formulations naturally lead to a high number of variables, naturally lending themselves to be solved by a column generation approach. It turns out that a pivotal step in this approach is the pricing problem, which yields a time-dependent shortest path problem of independent interest. This problem is to find and price paths in the time expansion of a graph \(G\), which are acyclic when projected in the underlying graph \(G\).