کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4959107 | 1445470 | 2017 | 27 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Analysis of FPTASes for the multi-objective shortest path problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Analysis of FPTASes for the multi-objective shortest path problem Analysis of FPTASes for the multi-objective shortest path problem](/preview/png/4959107.png)
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 78, February 2017, Pages 44-58
Journal: Computers & Operations Research - Volume 78, February 2017, Pages 44-58
نویسندگان
Thomas Breugem, Twan Dollevoet, Wilco van den Heuvel,