# Dynamic Shortest Paths Methods for the Time-Dependent TSP
## 3 A Branch-and-Price Algorithm
### An Arc-Based Formulation  
We formulate the TDTSP based on binary variables for each arc of \(D^{\mathcal{T}}\) similar to the SDTSP formulation in [19]. The formulation has two kinds of constraints: A number of covering constraints ensures that each vertex in \(V\) has exactly one outgoing arc in \(D^{\mathcal{T}}\)  
Figure 1: A directed graph \(D\) and its time-expansion \(D^{\mathcal{T}}\). (**a**) The directed graph \(D\); (**b**) The time-expansion \(D^{\mathcal{T}}\) of \(D\) with time horizon \(\theta^{\text{max}}=6\).  
while flow conservation constraints guarantee that any feasible solution consists of a single \((s_{0},s_{\theta})\)-path:  
\[\begin{split}\min_{x}&\sum_{(u,v,\theta)\in A^{\mathcal{ T}}}c_{uv}(\theta)\cdot x_{uv,\theta}\\ \text{s.t.}&\sum_{\theta\in\mathcal{T}(v)}x(\delta^ {+}(v_{\theta}))=1\qquad\forall\,v\in V\\ & x(\delta^{+}(v_{\theta}))-\delta^{-}(v_{\theta})=0\quad\forall \,v\
eq s,\theta\in\mathcal{T}(v)\\ & x_{a}\in\{0,1\}\qquad\qquad\qquad\qquad\qquad\forall\,a\in A^{ \mathcal{T}}.\end{split}\] (TDTSP-A)  
**Remark 2**.: _By virtue of the flow conservation constraints in (TDTSP-A), any solution of the program or its LP-relaxation can be decomposed into a set of paths leading from vertex \(s_{0}\) to vertices \(s_{\theta}\) for some values \(\theta\subseteq\mathcal{T}(s)\). As a result, there exist several equivalent linear objectives, for example the arrival time objective, given by_  
\[\sum_{\theta\in\mathcal{T}(s)}\sum_{(v,s,\theta^{\prime})\in\delta^{-}(s_{ \theta})}\theta\cdot x_{\text{\tiny{NS}},\theta}.\]  
Relation to the Static ATSP  
There is a strong relationship between the TDTSP and the ATSP. Let \(y:A\to\mathbb{R}_{\geq 0}\) be the compound flow traversing an arc \((u,v)\in A\) with respect to a feasible solution \((x_{a})_{a\in A^{\mathcal{T}}}\) of (TDTSP-A), given as  
\[y_{uv}\coloneqq\sum_{(u,v,\theta)\in A^{\mathcal{T}}}x_{uv,\theta}. \tag{3}\]  
The covering constraints and the flow conservation yield the well-known two matching equations,  
\[y(\delta^{+}(v))=y(\delta^{-}(v))=1\quad\forall\,v\in V.\]  
The covering constraints and the integrality of the variables \(x\) imply that the values \(y\) are binary for any feasible solution \(x\). However, a correct static ATSP formulation still requires subtour elimination constraints (SECs) of the form  
\[y(\delta^{+}(S))\geq 1\quad\forall\,S\subset V,\;S\
eq\emptyset,V.\]  
Since \(D^{\mathcal{T}}\) is acyclic, any solution of (TDTSP-A) is guaranteed to satisfy the additional SECs. Equivalently, flow augmentation techniques [32] for strengthening ATSP formulations are redundant for (TDTSP-A). Conversely, SECs are not necessarily satisfied by fractional solutions. Thus, (TDTSP-A) can be strengthened by separating SECs with respect to the underlying static ATSP (see Section 3.4).  
Valid inequalities for the ATSP can be included in the TDTSP by first computing the compound flow \(y^{*}\) of a solution \(x^{*}\) of the LP-relaxation of (TDTSP-A), executing some separation algorithm yielding a valid inequality in the compound variables \(y\), and finally expressing this inequality in terms of the original problem variables \(x\).  
Any feasible TDTSP solution is feasible for the underlying ATSP, and generic ATSP solutions do not necessarily produce feasible solutions of the TDTSP. Specifically, no tour \(T=(a_{1},\ldots,a_{n})\) with \(\theta^{\text{arr}}(T)>\theta^{\text{max}}\) can be embedded into \(D^{\mathcal{T}}\). The complete description of the TDTSP in terms of compound variables \(y\) can be obtained by adding forbidden path constraints of the form  
\[\sum_{a\in P}y_{a}\leq k-1\quad\forall\,P=(a_{1},\ldots,a_{k}):\theta^{\text{arr }}(P)>\theta^{\text{max}}.\]As a result, facet-defining ATSP inequalities, while valid, are not necessarily facet-defining for the TDTSP.