Book
Exact and Approximate Algorithms for Finding k-Shortest Paths with Limited Overlap
| العنوان: | Exact and Approximate Algorithms for Finding k-Shortest Paths with Limited Overlap |
|---|---|
| المؤلفون: | Chondrogiannis T, Bouros P, Gamper J, Leser U |
| المساهمون: | Mitschang B, Markl V, Bress S, Andritsos P, Sattler KU, Orlando S |
| بيانات النشر: | OpenProceedings.org |
| سنة النشر: | 2017 |
| المجموعة: | Free University of Bozen-Bolzano (UNIBZ): BIA (Bozen-Bolzano Institutional Archive) |
| الوصف: | Shortest path computation is a fundamental problem in road net- works with various applications in research and industry. However, returning only the shortest path is often not satisfying. Users might also be interested in alternative paths that are slightly longer but have other desired properties, e.g., less frequent traffic congestion. In this paper, we study alternative routing and, in particular, the k-Shortest Paths with Limited Overlap (k-SPwLO) query, which aims at computing paths that are (a) sufficiently dissimilar to each other, and (b) as short as possible. First, we propose MultiPass, an exact algorithm which traverses the network k−1 times and em- ploys two pruning criteria to reduce the number of paths that have to be examined. To achieve better performance and scalability, we also propose two approximate algorithms that trade accuracy for efficiency. OnePass+ employs the same pruning criteria as Multi- Pass, but traverses the network only once. Therefore, some paths might be lost that otherwise would be part of the solution. ESX computes alternative paths by incrementally removing edges from the road network and running shortest path queries on the updated network. An extensive experimental analysis on real road networks shows that: (a) MultiPass outperforms state-of-the-art exact algo- rithms for computing k-SPwLO queries, (b) OnePass+ runs sig- nificantly faster than MultiPass and its result is close to the exact solution, and (c) ESX is faster than OnePass+ (though slightly less accurate) and scales for large road networks and large values of k. ; open |
| نوع الوثيقة: | book part |
| وصف الملف: | application/pdf |
| اللغة: | English |
| ردمك: | 978-3-89318-073-8 3-89318-073-7 |
| Relation: | 20th International Conference on Extending Database Technology (EDBT 2017); Venice : 21.3.2017 - 24.3.2017; http://dx.doi.org/10.5441/002/edbt.2017.37; http://openproceedings.org/html/pages/2017_edbt.html; https://bia.unibz.it/handle/10863/10794 |
| DOI: | 10.5441/002/edbt.2017.37 |
| الاتاحة: | https://doi.org/10.5441/002/edbt.2017.37 http://openproceedings.org/html/pages/2017_edbt.html https://bia.unibz.it/handle/10863/10794 |
| رقم الانضمام: | edsbas.27BEC40C |
| قاعدة البيانات: | BASE |
| ردمك: | 9783893180738 3893180737 |
|---|---|
| DOI: | 10.5441/002/edbt.2017.37 |