# Dynamic Shortest Paths Methods for the Time-Dependent TSP
## 4 Computational Experiments
### Computational Results
#### 4.2.2 Performance of Different Pricers  
We proceed to evaluate the pricing methods introduced in Section 3.3. As a first step, we study the difference between pricing individual arcs and entire paths with respect to the arc-based formulation (TDTSP-A). While both approaches yield the same gaps at the root node, path-based pricing is substantially faster than pricing arcs, while yielding relaxations with substantially fewer variables.  
We then examine the effect of pricing \(k\)-cycle-free paths, based on the algorithms introduced in [17], the experimental results being depicted in Table 2. Clearly, increasing the value of \(k\) increases the computational effort. On the other hand, larger values of \(k\) yield tighter relaxations. To obtain a realistic picture of the running times, we solved the LP-relaxation of (TDTSP-A) and measured the required running time, thereby accounting for deviations in the size of the programs arising from the use of different pricing techniques. After solving the relaxations, we compute the relative gaps between the different dual bounds and the primal bound obtained from the original path-based pricing method, thereby ignoring any distortions due to improved primal bounds.  
We find that, independently of the formulation, pricing two-cycle-free paths incurs a negligible computational overhead of less than a minute, while closing almost 30% of the relative gap. Increasing \(k\) beyond two immediately results in a significant increase to the computational effort, requiring almost 40 min for large instances for the arc-based formulation. What is more, the effect of pricing \(k\)-cycle-free paths on the relative gap becomes less pronounced for larger values of \(k\).  
Regarding the formulations, the pricing procedure becomes significantly more difficult for the path-based formulation (TDTSP-P). While the effect is mitigated when we add dual stabilization, the difference remains significant. A likely explanation is that, when solving the arc-based formulation, the LP solver can compose the arcs of previously added paths in order to obtain new paths, which may not have been explicitly added before. As a result, the solver is quickly able to compute near-optimal dual values, thereby guiding the column generation. What is more, the difference between the formulations with respect to the relative gaps is very slight and does not merit the computational effort required.  
Based on these observations we proposed to use the arc-based formulation while pricing two-cycle-free paths in order to achieve a reasonable trade-off between computational overhead and decrease in relative gap.  
\begin{table}
\begin{tabular}{r r r r r r r r r r r r r r r} \hline \hline \multirow{2}{*}{**Instance**} & \multicolumn{4}{c}{(TDTSP-A)} & \multicolumn{4}{c}{(TDTSP-A) with Pricing} & \multicolumn{4}{c}{(TDTSP-P) with Pricing} \\ \cline{2-13}  & **p** & **d** & **g** & **n** & **\(\mathbf{f_{nord}}\)** & **p** & **d** & **g** & **n** & \(\mathbf{f_{nord}}\)** & **p** & **d** & **g** & **n** & \(\mathbf{f_{nord}}\) \\ \hline  
\hline \hline \end{tabular}
\end{table}
Table 1: Statistics with respect to the large instances for miscellaneous formulations, consisting of primal, dual values, remaining gap, the number of examined nodes, and the time required to solve the root node.