# Dynamic Shortest Paths Methods for the Time-Dependent TSP
## 5 Conclusions and Future Work  
In this paper, we have discussed several theoretical and empirical properties of the TDTSP. Since the TDTSP is a generalization of the ATSP, many of the complexity-specific theoretical results, such as \(\mathcal{NP}\)-hardness and inapproximability, carry over to the TDTSP.  
Unfortunately, several positive results regarding the ATSP are not retained in the TDTSP. Specifically, the TDTSP remains inapproximable even if a generalized triangle  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline  & \multicolumn{3}{c}{**Running Time [s]**} & \multicolumn{3}{c}{**Relative Gap**} \\ \cline{2-5}  & \multicolumn{1}{c}{**Small**} & **Large** & **Small** & **Large** \\ \hline
**Original** & & 1.14 & 18.57 & 0.43 & 0.57 \\ \hline \multirow{3}{*}{**Heuristic**} & Compound value & 2.53 & 47.93 & 0.30 & 0.53 \\  & Inverted travel time & 2.34 & 45.22 & 0.37 & 0.53 \\ \cline{1-1}  & Variable value & 1.99 & 46.38 & 0.37 & 0.50 \\ \hline \hline \end{tabular}
\end{table}
Table 4: Running time and relative gap for different heuristics.  
\begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \multirow{2}{*}{**Instance**} & \multicolumn{  
inequality is satisfied. Furthermore, even simple relaxations, such as time-dependent trees, cannot be used to determine combinatorial lower bounds on the TDISP.  
From a practitioner's point of view, the increase in problem size poses significant problems when trying to solve even moderate-sized instances of the TDISP. The authors of [15] conclude that there are challenging instances of the SDTSP with less than 100 vertices. While the results date back some years, the increase in computational complexity is apparent even in the case of the SDTSP.  
To be able to tackle the TDISP, a sophisticated pricing routine is necessary. It is apparent that generating columns according to time-dependent paths is superior to generating columns for individual arcs. More recent advances regarding specialized shortest path variants facilitate the solution process by achieving improved dual bounds. Further improvements in this area will likely benefit the TDISP as well.  
The connection between TDISP and ATSP yields a variety of feasible classes of inequalities which help to significantly improve dual bounds. Unfortunately, the generalizations of SDTSP-type inequalities do not perform equally well in comparison. Objective value propagation and primal heuristics decrease the gap even further. The primal heuristics profit from the connection to the ATSP, significantly outperforming the heuristics built into the solver itself.  
We have focused on developing an algorithm capable of solving instances with fairly arbitrary travel times. It may be worth investigating the performance on instances with more regular travel time functions by conducting a computational study. Similarly, the existing formulations can be extended to incorporate time windows, suggesting further comparative experiments.  
Conceptualization, C.H. and I.J. and S.S.; software, C.H.; investigation, C.H.; writing--original draft preparation, C.H. and I.J.; writing--review and editing, C.H. and I.J. and S.S.; funding acquisition, I.J. and S.S. All authors have read and agreed to the published version of the manuscript.  
We acknowledge support by the German Research Foundation and the Open Access Publication Funds of Technische Universitat Braunschweig. The second author was partly funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany's Excellence Strategy--EXC 2163/1--Sustainable and Energy Efficient Aviation--Project-ID 390881007.  
The implementation of the algorithm as well as the generator for all random instances is available at [[https://github.com/chrhansk/time-dependent-tsp](https://github.com/chrhansk/time-dependent-tsp)]([https://github.com/chrhansk/time-dependent-tsp](https://github.com/chrhansk/time-dependent-tsp)).  
The authors declare no conflict of interest.