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 -