کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
478446 1446086 2012 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A comparison of heuristic best-first algorithms for bicriterion shortest path problems
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
A comparison of heuristic best-first algorithms for bicriterion shortest path problems
چکیده انگلیسی

A variety of algorithms have been proposed to solve the bicriterion shortest path problem. This article analyzes and compares the performance of three best-first (label-setting) algorithms that accept heuristic information to improve efficiency. These are NAMOA∗, MOA∗, and Tung & Chew’s algorithm (TC). A set of experiments explores the impact of heuristic information in search efficiency, and the relative performance of the algorithms. The analysis reveals that NAMOA∗ is the best option for difficult problems. Its time performance can benefit considerably from heuristic information, though not in all cases. The performance of TC is similar but somewhat worse. However, the time performance of MOA∗ is found to degrade considerably with the use of heuristic information in most cases. Explanations are provided for these phenomena.


► Three heuristic multiobjective best-first (label setting) algorithms are compared.
► The influence of solution depth and correlation between objectives is considered.
► Heuristic algorithm NAMOA∗ is generally the best alternative.
► A class of problems is analysed where heuristics do not improve time performance.
► A very bad time performance of heuristic algorithm MOA∗ is observed and analysed.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 217, Issue 1, 16 February 2012, Pages 44–53
نویسندگان
, , , ,