TY - JOUR A1 - Maristany de las Casas, Pedro A1 - Borndörfer, Ralf A1 - Kraus, Luitgard A1 - Sedeño-Noda, Antonio T1 - An FPTAS for Dynamic Multiobjective Shortest Path Problems JF - Algorithms N2 - 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. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.3390/a14020043 VL - 14 IS - 2 SP - 1 EP - 22 ER - TY - JOUR A1 - Maristany de las Casas, Pedro A1 - Kraus, Luitgard A1 - Sedeno-Noda, Antonio A1 - Borndörfer, Ralf T1 - Targeted multiobjective Dijkstra Algorithm JF - Networks N2 - We introduce the Targeted Multiobjective Dijkstra Algorithm (T-MDA), a label setting algorithm for the One-to-One Multiobjective Shortest Path (MOSP) Problem. It is based on the recently published Multiobjective Dijkstra Algorithm (MDA) and equips it with A*-like techniques. For any explored subpath, a label setting MOSP algorithm decides whether the subpath can be discarded or must be stored as part of the output. A major design choice is how to store subpaths from the moment they are first explored until the mentioned final decision can be made. The T-MDA combines the polynomially bounded size of the priority queue used in the MDA and alazy management of paths that are not in the queue. The running time bounds from the MDA remain valid. In practice, the T-MDA outperforms known algorithms from the literature and the increased memory consumption is negligible. In this paper, we benchmark the T-MDA against an improved version of the state of the art NAMOA∗drOne-to-One MOSP algorithm from the literature on a standard testbed. Y1 - 2023 U6 - https://doi.org/10.1002/net.22174 VL - 82 IS - 3 SP - 277 EP - 298 ER - TY - CHAP A1 - Blanco, Marco A1 - Borndörfer, Ralf A1 - Maristany de las Casas, Pedro T1 - An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles T2 - 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022) N2 - The Flight Planning Problem is to find a minimum fuel trajectory between two airports in a 3D airway network under consideration of the wind. We show that this problem is NP-hard, even in its most basic version. We then present a novel A∗ heuristic, whose potential function is derived from an idealized vertical profile over the remaining flight distance. This potential is, under rather general assumptions, both admissible and consistent and it can be computed efficiently. The method outperforms the state-of-the-art heuristic on real-life instances. Y1 - 2022 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2022.1 VL - 106 SP - 1:1 EP - 1:15 ER - TY - GEN A1 - Maristany de las Casas, Pedro A1 - Borndörfer, Ralf A1 - Kraus, Luitgard A1 - Sedeño-Noda, Antonio T1 - An FPTAS for Dynamic Multiobjective Shortest Path Problems N2 - We propose in this paper the Dynamic Multiobjective Shortest Problem. It features multidimensional states that can depend on several variables and not only on time; this setting is motivated by flight planning and electric vehicle routing applications. We give an exact algorithm for the FIFO case and derive from it an FPTAS, which is computationally efficient. It also features the best known complexity in the static case. T3 - ZIB-Report - 20-31 KW - Multiobjective Shortest Paths KW - Time Dependent Shortest Paths KW - Multiobjective Approximation Algorithms KW - Flight Planning Problem Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-80954 ER - TY - JOUR A1 - Schienle, Adam A1 - Maristany de las Casas, Pedro A1 - Blanco, Marco T1 - A Priori Search Space Pruning in the Flight Planning Problem N2 - We study the Flight Planning Problem for a single aircraft, where we look for a minimum cost path in the airway network, a directed graph. Arc evaluation, such as weather computation, is computationally expensive due to non-linear functions, but required for exactness. We propose several pruning methods to thin out the search space for Dijkstra's algorithm before the query commences. We do so by using innate problem characteristics such as an aircraft's tank capacity, lower and upper bounds on the total costs, and in particular, we present a method to reduce the search space even in the presence of regional crossing costs. We test all pruning methods on real-world instances, and show that incorporating crossing costs into the pruning process can reduce the number of nodes by 90\% in our setting. T3 - ZIB-Report - 20-32 Y1 - 2019 U6 - https://doi.org/https://doi.org/10.4230/OASIcs.ATMOS.2019.8 SN - 1438-0064 ER -