کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
474604 699076 2015 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Dimensionality reduction in multiobjective shortest path search
ترجمه فارسی عنوان
کاهش ابعاد در جستجوی کوتاهترین چند هدفه
کلمات کلیدی
بهینه سازی ترکیبی، مشکل چندین هدف کوتاه ترین راه، الگوریتم های دقیق تنظیم برچسب، مرزهای پایین
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی


• A dimensionality reduction technique is applied to speed up dominance checks.
• The new technique is proved to be equivalent to the standard dominance checks.
• The technique applies to exact best-first multiobjective shortest path label-setting algorithms.
• The paper evaluates the application of the new technique to the NAMOA⁎ label-setting algorithm.
• Experiments on grids and road maps reveal dramatic performance improvements.

One-to-one multiobjective search in graphs deals with the problem of finding all Pareto-optimal solution paths between given start and goal nodes according to a number of distinct noncommensurate objectives. The problem is inherently more complex than single objective graph search. Time requirements are dominated by the facts that (a) many different non-dominated labels may need to be explored for each node; (b) each new label under consideration must be checked for dominance against various subsets of previously generated labels. This paper describes how a dimensionality reduction technique can be applied to exact label-setting algorithms, reducing the number of dominance checks and allowing for much faster multiobjective search. The technique is applied to NAMOA⁎NAMOA⁎, a state of the art exact label-setting multiobjective search algorithm, achieving reductions in time requirements of more than an order of magnitude over problems in random grids and realistic road maps. Tests include problems with three, four, and five objectives.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 64, December 2015, Pages 60–70
نویسندگان
, , ,