Analysis of FPTASes for the Multi-Objective Shortest Path Problem

Research output: Contribution to journalArticleAcademicpeer-review

17 Citations (Scopus)

Abstract

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 [25]. 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.
Original languageEnglish
Pages (from-to)44-58
Number of pages15
JournalComputers and Operations Research
Volume78
Early online date1 Jul 2016
DOIs
Publication statusPublished - 2017

Fingerprint

Dive into the research topics of 'Analysis of FPTASes for the Multi-Objective Shortest Path Problem'. Together they form a unique fingerprint.

Cite this