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.
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] | |
Publishing Institution: | Zuse Institute Berlin (ZIB) |
Date of first Publication: | 2020/12/01 |
Series (Serial Number): | ZIB-Report (20-31) |
Published in: | Appeared in Algorithms 2021, 14(2), 43 |
DOI: | https://doi.org/https://doi.org/10.3390/a14020043 |