کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6892958 699328 2014 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A lower bound for the quickest path problem
ترجمه فارسی عنوان
یک خط پایین برای سریعترین مشکل مسیر
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی
The point-to-point quickest path problem is a classical network optimization problem with numerous applications, including that of computing driving directions. In this paper, we define a lower bound on the time-to-target which is both accurate and fast to compute. We show the potential of this bound by embedding it into an A⁎ algorithm. Computational results on three large European metropolitan road networks, taken from the OpenStreetMap database, show that the new lower bound allows us to achieve an average reduction of 14.36%. This speed-up is valuable for a typical web application setting, where a server needs to answer a multitude of quickest path queries at the same time. Even greater computing time reductions (up to 28.06%) are obtained when computing paths in areas with moderate speeds, e.g. historical city centers.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 50, October 2014, Pages 154-160
نویسندگان
, ,