An FPTAS for Dynamic Multiobjective Shortest Path Problems

Please always quote using this URN: urn:nbn:de:0297-zib-80954
  • 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.

Download full text files

Export metadata

Metadaten
Author:Pedro Maristany de las CasasORCiD, Ralf BorndörferORCiD, Luitgard KrausORCiD, Antonio Sedeño-NodaORCiD
Document Type:ZIB-Report
Tag:Flight Planning Problem; Multiobjective Approximation Algorithms; Multiobjective Shortest Paths; Time Dependent Shortest Paths
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B99 None of the above, but in this section
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C29 Multi-objective and goal programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C35 Programming involving graphs or networks [See also 90C27]
Date of first Publication:2020/12/01
Series (Serial Number):ZIB-Report (20-31)
ISSN:1438-0064