کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
478078 1446009 2015 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An exact method for the biobjective shortest path problem for large-scale road networks
ترجمه فارسی عنوان
یک روش دقیق برای کوچکترین مشکل مسیر زیستی برای شبکه های بزرگ جاده ای
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی


• Recursive exact algorithm that implicitly enumerates all solutions.
• Fast method that works well on graphs of up to 1.2 million nodes and 2.8 million arcs.
• Consistently outperformed a top-performer benchmark algorithm for real road networks.
• Easily extensible to the multiobjective shortest path problem with three or more objectives.

The Biobjective Shortest Path Problem (BSP) is the problem of finding (one-to-one) paths from a start node to an end node, while simultaneously minimizing two (conflicting) objective functions. We present an exact recursive method based on implicit enumeration that aggressively prunes dominated solutions. Our approach compares favorably against a top-performer algorithm on two large testbeds from the literature and efficiently solves the BSP on large-scale networks with up to 1.2 million nodes and 2.8 million arcs. Additionally, we describe how the algorithm can be extended to handle more than two objectives and prove the concept on networks with up to 10 objectives.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 242, Issue 3, 1 May 2015, Pages 788–797
نویسندگان
, , ,