# An FPTAS for Dynamic Multiobjective Shortest Path Problems
## 3 The Multiobjective Dijkstra Algorithm for Dynamic MOSP Problems
### Description of the Algorithm
Even better, it also works for Dyn-MOSP instances if the arc

Figure 8: Distribution of percentage of labels saved by the MD-FPTAS in comparison to the exact MD-A on FPP instances. \begin{table}
\begin{tabular}{c r r r r r r} \hline \hline
**Out-Airport** & \multicolumn{2}{c}{**Exact**} & \multicolumn{2}{c}{\(\varepsilon=0.5\)} & \multicolumn{2}{c}{\(\varepsilon=1\)} \\ \hline  & \(t[s]\) & \(\mathcal{N}\) & \(t[s]\) & \(\mathcal{N}\) & \(t[s]\) & \(\mathcal{N}\) \\ \hline Cape Town & 1.3288 & 1,537,645 & 1.0757 & 917,327 & 1.0246 & 817,945 \\ Los Angeles & 11.1541 & 12,854,272 & 8.5292 & 8,260,426 & 8.4359 & 7,961,418 \\ Moscow & 15.8314 & 19,385,407 & 11.4957 & 11,458,971 & 11.2693 & 10,819,170 \\ Berlin-Tegel & 14.6621 & 16,815,977 & 12.8159 & 12,724,498 & 12.6338 & 12,126,247 \\ Tenerife & 6.4615 & 9,182,417 & 5.4099 & 6,247,958 & 5.2085 & 5,739,303 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Running times and computed permanent labels on FPP instances. Figure 9: Least consumption (left) and fastest (right) routes from Berlin to Yekaterinburg. Source: www.skyvector.com. cost functions are FIFO, continuous, and piecewise linear, having only positive intercepts. These requirements are not very restrictive in practice. We corroborated the theoretical efficiency of our algorithms computationally. On a test set of standard bidimensional and 3-dimensional instances, our MD-FPTAS was faster than the Martins-FPTAS introduced by [PERSON] et al. [3]. In the static case, we faced the same problem as the authors in [2; 3]: the FPTAS does not avoid the computation of paths unless \(\varepsilon\) is chosen very large. The reason is that, so far, most instances used in the literature to test MOSP algorithms have integer costs, causing efficient cost vectors to lie at least one cost unit apart from each other. In Dyn-MOSP instances the evaluation of continuous, piecewise linear functions is likely to generate labels with rational cost. This is the case in the Flight Planning instances that we considered. Furthermore, indeed, using realistic values for \(\varepsilon\), we computed \((1+\varepsilon)\)-covers for these instances and saved 21% in terms of running time and 35% in terms of labels. Conceptualization: P.M.d.l.C., R.B., and A.S.-N.; methodology, P.M.d.l.C., R.B., and A.S.-N.; software, P.M.d.l.C. and L.K. ; validation, P.M.d.l.C. and L.K. ; formal analysis, P.M.d.l.C., R.B., L.K., and A.S.-N.; investigation, P.M.d.l.C. and L.K. ; resources, P.M.d.l.C., R.B., L.K., and A.S.-N.; data curation, P.M.d.l.C. and L.K. ; writing-original draft preparation, P.M.d.l.C. ; writing-review and editing, P.M.d.l.C., R.B., L.K., and A.S.-N.; visualization, L.K. ; supervision, P.M.d.l.C., R.B., and A.S.-N.; project administration, P.M.d.l.C., R.B., and A.S.-N.; funding acquisition, R.B. and A.S.-N. All authors have read and agreed to the published version of the manuscript. The researches affiliated to the Zuse Institute Berlin conducted this work within the Research Campus MODAL-Mathematical Optimization and Data Analysis Laboratories-, funded by the German Federal Ministry of Education and Research (BMBF) (fund number 05M20 ZBM). [PERSON] was partially supported by the grant MTM2016-74877-P from the Ministerio de Economia y Competitividad. Data Availability Statement: Data sharing not applicable. We thank Lufthansa Systems GmbH & Co. KG for providing us with the data used to build our Dyn-MOSP test instances. We also thank [PERSON] for the helpful and fruitful discussions related proofs and the implementations concerning Dyn-MOSP problems. The authors from [3] provided us with the biobjective Grid and Netmaker instances used in their paper, so we could compare our results with existing data. They got their instances from [PERSON], who we also want to thank for providing us with the 3-dimensional instances we used for our computations. The authors declare no conflict of interest. ## References

* [PERSON] (1980) [PERSON] Bicriterion Path Problems.