# An FPTAS for Dynamic Multiobjective Shortest Path Problems
## 3 The Multiobjective Dijkstra Algorithm for Dynamic MOSP Problems
### Description of the Algorithm
Figure 6: BD-FPTAS (yellow) and Martins-FPTAS (blue) on grid instances (**left**) and netmaker instances (**right**). #### 5.2.3 Our Implementation of [PERSON]'s Algorithm

Note that our implementation of [PERSON]'s (exact) Algorithm and of the Martins-FPTAS is competitive compared to other relevant publications. For example, our biobjective implementation is up to \(\times 10^{5}\) faster than the one used in [3] when solving EXP instances. We believe that the reason is that-as already mentioned-we are using a constant time dominance check in the biobjective case. However, an in depth comparison of the performance of both implementations is not possible: we restricted ourselves to instances that use an approximation factor \(\varepsilon\leq 1\). This matches the assumption that we made in Section 4 to ensure that \((1+\varepsilon)=\Theta(\varepsilon)\). The direct comparison of our implementation of [PERSON]'s algorithm with the one used in [4] is even harder because the used instances do not coincide. However, the authors try to use \(\mathcal{C}++\) vectors whenever possible and use a lexicographically sorted binary heap to store the tentative labels. These choices are similar to ours (we use \(C\) arrays) and the reported running times on instances with three cost components are comparable to ours. #### 5.2.4 Results on Dyn-MOSP Instances

Figure 8 contains histograms showing how the labels (left) and running time (right) savings of the MD-FPTAS are distributed among the 380 considered Dyn-MOSP instances. On average, 21% of the time and 35% of the exact labels can be saved already for \(\varepsilon=0.5\). \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline  & & \multicolumn{6}{c}{**Martins**} & \multicolumn{2}{c}{**MDA**} \\ \hline  & \multicolumn{2}{c}{\(\mathcal{N}_{\mathbf{t}}\)**(02o)/**} & \multicolumn{2}{c}{**Exact \(\mathbf{t}[s]\)**} & \multicolumn{2}{c}{**FPTAS \(\mathbf{t}[s]\)**} & \multicolumn{2}{c}{**Exact \(\mathbf{t}[s]\)**} & \multicolumn{2}{c}{**FPTAS \(\mathbf{t}[s]\)**} \\ \hline  & \(\varepsilon=\) & & & 0.05 & 1 & & 0.05 & 1 \\ \cline{2-9} GRID 3D & avg & 8307 & 647.5844 & 772.9468 & 757.3884 & 439.4622 & 452.7110 & 452.4130 \\ One-to-One & min & 4 & 0.0255 & 0.0200 & 0.0255 & 0.0251 & 0.0232 & 0.0261 \\  & max & 30,041 & 4258.0670 & 5027.8374 & 5015.9595 & 3338.0901 & 3375.1526 & 3408.5612 \\ \hline NET 3D & avg & 13,308,684 & 1136.8950 & 1271.7758 & 1227.7586 & 823.6826 & 872.3511 & 844.0173 \\ One-to-All & min & 1,170,703 & 8.8158 & 43.9947 & 10.3916 & 4.0682 & 18.8914 & 5.5458 \\  & max & 38,647,047 & 4288.9419 & 4626.8179 & 4636.0591 & 4394.0124 & 4486.7231 & 4468.3011 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Results obtained by 3-dimensional Martins-FPTAS and MD-FPTAS. Figure 7: MD-FPTAS (yellow) and Martins-FPTAS (blue) on grid instances (**left**) and netmaker instances (**right**). In Table 5, we depicted some geographically distant departure airports and show the impact of the FPTAS when computing routes to all reachable nodes. We finish our computational experiments showing the least consumption and fastest routes from Berlin to Yekaterinburg in Figure 9. Even though consumption and time are correlated objectives, this example shows that both have to be considered since the routes vary considerably. ## 6 Conclusions

We have proven that Dynamic Multiobjective Shortest Path (Dyn-MOSP) problems can be solved by a generalization of the static Multiobjective Dijkstra Algorithm (MD-A) if the arc cost functions are FIFO and have independent dynamics (e.g., weight and time; time and state of charge). Our main contribution was to adapt the techniques used in the seminal work by [PERSON] and [PERSON] [2] to derive a new FPTAS for MOSP problems that is based on the label setting MD-A. The running time of the resulting MD-FPTAS is the number of computed paths multiplied by the running time of the classical Dijkstra algorithm and is thus--to the best of our knowledge--the most efficient FPTAS for MOSP problems in the literature.