{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T18:54:43Z","timestamp":1773168883148,"version":"3.50.1"},"reference-count":27,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2021,1,29]],"date-time":"2021-01-29T00:00:00Z","timestamp":1611878400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Research Campus MODAL","award":["05M20ZBM"],"award-info":[{"award-number":["05M20ZBM"]}]},{"DOI":"10.13039\/501100003329","name":"Ministerio de Econom\u00eda y Competitividad","doi-asserted-by":"publisher","award":["MTM2016-74877-P"],"award-info":[{"award-number":["MTM2016-74877-P"]}],"id":[{"id":"10.13039\/501100003329","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The Dynamic Multiobjective Shortest Path problem features multidimensional costs that can depend on several variables and not only on time; this setting is motivated by flight planning applications and the routing of electric vehicles. We give an exact algorithm for the FIFO case and derive from it an FPTAS for both, the static Multiobjective Shortest Path (MOSP) problems and, under mild assumptions, for the dynamic problem variant. The resulting FPTAS is computationally efficient and beats the known complexity bounds of other FPTAS for MOSP problems.<\/jats:p>","DOI":"10.3390\/a14020043","type":"journal-article","created":{"date-parts":[[2021,1,29]],"date-time":"2021-01-29T09:25:22Z","timestamp":1611912322000},"page":"43","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["An FPTAS for Dynamic Multiobjective Shortest Path Problems"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4197-0893","authenticated-orcid":false,"given":"Pedro","family":"Maristany de las Casas","sequence":"first","affiliation":[{"name":"Network Optimization Department, Zuse Institute Berlin, Takustra\u00dfe 7, 14195 Berlin, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7223-9174","authenticated-orcid":false,"given":"Ralf","family":"Bornd\u00f6rfer","sequence":"additional","affiliation":[{"name":"Network Optimization Department, Zuse Institute Berlin, Takustra\u00dfe 7, 14195 Berlin, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5735-9415","authenticated-orcid":false,"given":"Luitgard","family":"Kraus","sequence":"additional","affiliation":[{"name":"Network Optimization Department, Zuse Institute Berlin, Takustra\u00dfe 7, 14195 Berlin, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0681-4585","authenticated-orcid":false,"given":"Antonio","family":"Sede\u00f1o-Noda","sequence":"additional","affiliation":[{"name":"Departamento de Matem\u00e1ticas, Estad\u00edstica e Investigaci\u00f3n Operativa, Universidad de La Laguna, 38271 San Crist\u00f3bal de La Laguna, Santa Cruz de Tenerife, Spain"}]}],"member":"1968","published-online":{"date-parts":[[2021,1,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Fandel, G., and Gal, T. (1980). Bicriterion Path Problems. Multiple Criteria Decision Making Theory and Application, Springer.","DOI":"10.1007\/978-3-642-48782-8"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Asano, T. (2006). Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-linear Objectives with Applications. Algorithms and Computation, Springer.","DOI":"10.1007\/11940128"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/j.cor.2016.06.022","article-title":"Analysis of FPTASes for the multi-objective shortest path problem","volume":"78","author":"Breugem","year":"2017","journal-title":"Comput. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"B\u00f6kler, F., and Chimani, M. (2020). Approximating Multiobjective Shortest Path in Practice. 2020 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9781611976007.10"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1007\/s11047-018-9685-y","article-title":"A tutorial on multiobjective optimization: Fundamentals and evolutionary methods","volume":"17","author":"Emmerich","year":"2018","journal-title":"Nat. Comput."},{"key":"ref_6","unstructured":"Ehrgott, M., and Gandibleux, X. (2006). Multiple Criteria Optimization: State of the Art Annotated Bibliographic Surveys, Springer."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1007\/s002910000046","article-title":"A survey and annotated bibliography of multiobjective combinatorial optimization","volume":"22","author":"Ehrgott","year":"2000","journal-title":"OR Spektrum"},{"key":"ref_8","unstructured":"Gl\u00fcckaufova, D., Loula, D., and Cerny, M. Multi-objective shortest path problem: A survey. Proceedings of the International Workshop on Multicriteria Decision Making: Methods-Algorithms-Applications at Liblice, Czechoslovakia."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1016\/0377-2217(93)90140-I","article-title":"Multiobjective transportation network design and routing problems: Taxonomy and annotation","volume":"65","author":"Current","year":"1993","journal-title":"Eur. J. Oper. Res."},{"key":"ref_10","first-page":"199","article-title":"A classification of Bicriterion Shortest Path (BSP) algorithms","volume":"17","author":"Skriver","year":"2000","journal-title":"Asia Pac. J. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"269","DOI":"10.2478\/v10006-007-0023-2","article-title":"Selected multicriteria shortest path problems: An analysis of complexity, models and adaptation of standard algorithms","volume":"17","author":"Tarapata","year":"2007","journal-title":"Int. J. Appl. Math. Comput. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1111\/j.1475-3995.2011.00815.x","article-title":"Multicriteria path and tree problems: Discussion on exact algorithms and applications","volume":"19","author":"Pascoal","year":"2012","journal-title":"Int. Trans. Oper. Res."},{"key":"ref_13","first-page":"425","article-title":"Problemes multicriteres","volume":"16","author":"Vincke","year":"1974","journal-title":"Cah. Centre d\u2019 Etudes de Rech. Oper."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1007\/978-3-642-46618-2_15","article-title":"Some considerations about computational complexity for multiobjective combinatorial problems","volume":"294","author":"Serafini","year":"1986","journal-title":"Recent Adv. Hist. Dev. Vector Optim."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/0377-2217(84)90077-8","article-title":"On a multicriteria shortest path problem","volume":"16","author":"Martins","year":"1984","journal-title":"Eur. J. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/j.ejor.2019.01.007","article-title":"A biobjective Dijkstra algorithm","volume":"276","author":"Colebrook","year":"2019","journal-title":"Eur. J. Oper. Res."},{"key":"ref_17","unstructured":"de las Casas, P.M., Sedeno-Noda, A., and Bornd\u00f6rfer, R. (2020). An Asymptotically and Computationally Improved Multiobjective Shortest Path Algorithm, Takustr. Technical Report 20\u201326. ZIB."},{"key":"ref_18","unstructured":"Papadimitriou, C., and Yannakakis, M. (2000, January 12\u201314). On the approximability of trade-offs and optimal access of Web sources. Proceedings of the 41st Annual Symposium on Foundations of Computer Science, Washington, DC, USA."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Trzaskalik, T., and Michnik, J. (2002). Multiple Objective Path Optimization for Time Dependent Objective Functions. Multiple Objective and Goal Programming, Physica-Verlag HD.","DOI":"10.1007\/978-3-7908-1812-3"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/978-3-540-68552-4_26","article-title":"Multi-criteria Shortest Paths in Time-Dependent Train Networks","volume":"5038","author":"Disser","year":"2008","journal-title":"Exp. Algorithms Lect. Notes Comput. Sci."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Foschini, L., Hershberger, J., and Suri, S. (2011). On the Complexity of Time-Dependent Shortest Paths. Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics. SODA\u2018 11.","DOI":"10.1137\/1.9781611973082.27"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1090\/S0002-9904-1954-09848-8","article-title":"The theory of dynamic programming","volume":"60","author":"Bellman","year":"1954","journal-title":"Bull. Am. Math. Soc."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1865","DOI":"10.1016\/S0305-0548(02)00112-0","article-title":"Solving bicriteria 0-1 knapsack problems using a labeling algorithm","volume":"30","author":"Captivo","year":"2003","journal-title":"Comput. Oper. Res."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","article-title":"Fibonacci heaps and their uses in improved network optimization algorithms","volume":"34","author":"Fredman","year":"1987","journal-title":"J. ACM"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1299","DOI":"10.1016\/j.cor.2008.02.002","article-title":"A comparison of solution strategies for biobjective shortest path problems","volume":"36","author":"Raith","year":"2009","journal-title":"Comput. Oper. Res."},{"key":"ref_26","first-page":"12:1","article-title":"Solving Time Dependent Shortest Path Problems on Airway Networks Using Super-Optimal Wind","volume":"Volume 54","author":"Goerigk","year":"2016","journal-title":"16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)"},{"key":"ref_27","first-page":"15:1","article-title":"Cost Projection Methods for the Shortest Path Problem with Crossing Costs","volume":"Volume 59","author":"Dollevoet","year":"2017","journal-title":"17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/2\/43\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:17:09Z","timestamp":1760159829000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/2\/43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,29]]},"references-count":27,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,2]]}},"alternative-id":["a14020043"],"URL":"https:\/\/doi.org\/10.3390\/a14020043","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,29]]}}}