# Dynamic Shortest Paths Methods for the Time-Dependent TSP
## Appendix A Time-Dependent Spanning Trees  
Relaxations play an important role in integer programming in general and the TSP in particular. They provide lower bounds which can be used to obtain quality guarantees for solutions. The prevalent relaxation of combinatorial problems formulated as integer programs is given by their fractional relaxations. In several cases however, it is possible to derive purely combinatorial relaxations. In case of the symmetric traveling salesman problem, a popular combinatorial relaxation is given by one-trees [31]. A one-tree with respect to a graph \(G=(V,E)\) with \(V=\{1,\ldots,n\}\) consists of a spanning tree together with an additional edge joining vertex \(s\): \(=1\) to another vertex \(v\in V\). Since every tour is a one-tree, the one-tree of minimum cost provides a lower bound on the cost of a tour. The computation of such a one-tree in the static case involves the computation of a minimum spanning tree (MST), which can be carried out efficiently. The approach generalizes to the ATSP, in which case the one-tree corresponds to an arborescence with root \(s\) together with a single arc entering \(s\) from another vertex \(v\). An important question to ask is whether these approaches carry over to the time-dependent case. We begin by generalizing the definition of spanning trees to the time-dependent case. To this end, we assume throughout this subsection that \(D\) is bidirected, corresponding to an undirected graph \(G_{D}\), and that the time-dependent cost function \(c\) is symmetric, i.e., \(c_{uv}(\theta)=c_{uu}(\theta)\) holds for all \((u,v)\in A\), \(\theta\in\Theta\), making the cost function \(c\) correspond to the undirected edges of \(G_{D}\). We consider a spanning tree \(T=(V,F)\) of \(G_{D}\). For each vertex \(v\in V\), there exists a unique \((s,v)\)-path \(P_{v}\) in \(T\), enabling us to define an arrival time \(\theta_{T}^{\text{arr}}(u)\) induced by \(T\) via \(P_{u}\) for each \(u\in V\). Based on these arrival times we define the following:  
**Definition A1**. : _A time-dependent minimum spanning tree (TDMST) is a spanning tree \(T\) of \(G_{D}\) minimizing \(c(T)\), which is defined as_  
\[c(T)\coloneqq\sum_{\{u,v\}\in F}c_{uv}(\theta_{T}^{\text{arr}}(u)).\]  
The corresponding optimization problem asks for the value of a TDMST for an instance \((G_{D},c,s)\). As was the case before, any tour becomes a spanning tree once we remove its last arc, the arrival time of the resulting path at its target coinciding with the cost of the tree. Consequently, the optimal value of the corresponding TDTSP instance is bounded from below by the cost of any minimum spanning tree. Unfortunately, approximating the TDMST is an \(\mathcal{NP}\)-hard problem itself:  
**Theorem A1**. : _There is no \(\alpha\)-approximation algorithm for any \(\alpha>1\) for the TDMST problem unless \(\mathcal{P}=\mathcal{NP}\)._  
Proof. : Consider an instance of the 3 Sat problem (see [29] (p. 391)), given in terms of a set \(X\): \(=\{x_{1},\ldots,x_{n}\}\) of Boolean variables and a set \(\mathcal{Z}\): \(=\{Z_{1},\ldots,Z_{m}\}\) of clauses, each clause consisting of exactly three literals in \(X\cup\overline{X}\). We construct a suitable instance of the TDMST problem using a number of components. First we define a component \(A_{i}\) for each variable \(x_{i}\in X\). The component is shown in Figure 0(a), the edges being annotated with their (constant) travel times. We define a component \(B_{i}\) for each clause \(Z_{i}\in\mathcal{Z}\). To this end, let \(x_{i1}\), \(x_{i2}\), \(x_{i3}\) denote the variables whose literals appear in \(Z_{i}\) and \(M\geq 2n+6m+1\). The edges in the component have the following travel times:  
1. The edges \(\{w_{1},w_{i2}\}\) and \(\{w_{2},w_{i3}\}\) have a constant travel time of 1. 2. The edge \(\{v_{i1},w_{i1}\}\) has a travel time of \[c_{v_{i1}w_{i1}}(\theta)\coloneqq \begin{cases}1&\text{ if }\theta\leq 2 \text{, and}\\ M&\text{ otherwise.}\end{cases} \] The same holds true for the edges \(\{v_{i2},w_{i2}\}\) and \(\{v_{i3},w_{i3}\}\). 3.