Analysis of FPTASes for the multi-objective shortest path problem

详细信息    查看全文

• 作者：Thomas Breugem ; ^{breugem@ese.eur.nl} ; Twan Dollevoet ^{dollevoet@ese.eur.nl} ; Wilco van den Heuvel ^{wvandenheuvel@ese.eur.nl}
• 关键词：Shortest path problem ; Multi-objective optimization ; FPTAS ; Complexity analysis
• 刊名：Computers & Operations Research
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：78
• 期：Complete
• 页码：44-58
• 全文大小：1242 K
• 卷排序：78

文摘

A new FPTAS for a multi-objective shortest path (MOSP) problem is developed. The running time of this FPTAS decreases with the size of the Pareto-optimal frontier. The FPTAS can be arbitrarily faster than one from literature and an exact algorithm. We provide an instance with maximum sized Pareto-optimal frontier w.r.t. the nodes. We extensively test FPTASes for the MOSP problem in a computational study.