کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
473494 698793 2012 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Finding the K shortest paths in a schedule-based transit network
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Finding the K shortest paths in a schedule-based transit network
چکیده انگلیسی

Finding the shortest paths in a schedule-based public transit network is similar to finding the shortest paths in a network with multi-costs constrained and time-window constraints. We consider a schedule-based transit network, where each node in the network has a list of scheduled departure times for transit vehicles. The objective of this paper is to find out the first K   shortest paths in a schedule-based transit network. An algorithm with a time complexity of O(S¯2L¯3)+O(L¯4S¯Rlmax)+O(S¯L¯RlmaxK(L¯3log(L¯3)+L¯3)) is proposed to enumerate these paths. We compare the time complexity of our algorithm with that of two existing path finding algorithms. We show that our algorithm has a better performance in computational time complexity than the two existing path finding algorithms, though it is only applicable if the number of transfers does not exceed 2. Also, for large sized real transit network, our algorithm determines the K shortest paths in a much shorter time frame than the existing two algorithms.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 39, Issue 8, August 2012, Pages 1812–1826
نویسندگان
, , , ,