کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
478121 | 1446022 | 2014 | 11 صفحه PDF | دانلود رایگان |
• A novel quickest path algorithm is proposed.
• The algorithm runs in O(r(m+nlogn))O(r(m+nlogn)) time and uses O(m+n)O(m+n) space.
• It is a ratio-labeling algorithm working as a Dijkstra-like method.
• The method enumerates only supported efficient paths.
• Computational tests show that the algorithm performs very well.
We address the quickest path problem proposing a new algorithm based on the fact that its optimal solution corresponds to a supported non-dominated point in the objective space of the minsum–maxmin bicriteria path problem. This result allows us to design a label setting algorithm which improves all existing algorithms in the state-of-the-art, as it is shown in the extensive experiments carried out considering synthetic and real networks.
Journal: European Journal of Operational Research - Volume 238, Issue 2, 16 October 2014, Pages 596–606