An FPTAS for Dynamic Multiobjective Shortest Path Problems
Pedro Maristany de las Casas, Ralf Borndörfer, Luitgard Kraus, Antonio Sedeño‐Noda
Abstract
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.
Topics & Concepts
Shortest path problemMathematical optimizationK shortest path routingFIFO (computing and electronics)Path (computing)Computer scienceConstrained Shortest Path FirstMulti-objective optimizationRouting (electronic design automation)MathematicsTheoretical computer scienceGraphComputer hardwareProgramming languageComputer networkOptimization and Search ProblemsVehicle Routing Optimization MethodsComplexity and Algorithms in Graphs