Analysis of FPTASes for the multi-objective shortest path problem
We propose a new FPTAS for the multi-objective shortest path problem with non-negative and integer arc costs. The algorithm uses elements from both an exact labeling algorithm and an FPTAS proposed by Tsaggouris and Zaroliagis . We analyze the running times of these three algorithms both from a theoretical and a computational point of view. Theoretically, we show that there are instances for which the new FPTAS runs arbitrarily faster than the other two algorithms. Furthermore, for the bi-objective case, the number of approximate solutions generated by the proposed FPTAS is at most the number of Pareto-optimal points multiplied by the number of nodes. By performing a set of computational tests, we show that the new FPTAS performs best in terms of running time in case there are many dominated paths and the number of Pareto-optimal points is not too small.
|Keywords||Complexity analysis, FPTAS, Multi-objective optimization, Shortest path problem|
|Persistent URL||dx.doi.org/10.1016/j.cor.2016.06.022, hdl.handle.net/1765/115623|
|Series||ERIM Top-Core Articles|
|Journal||Computers & Operations Research|
Breugem, T, Dollevoet, T.A.B, & van den Heuvel, W. (2017). Analysis of FPTASes for the multi-objective shortest path problem. Computers & Operations Research, 78, 44–58. doi:10.1016/j.cor.2016.06.022