Finding k -shortest paths with limited overlap
- PDF / 2,668,895 Bytes
- 25 Pages / 595.276 x 790.866 pts Page_size
- 1 Downloads / 244 Views
REGULAR PAPER
Finding k-shortest paths with limited overlap Theodoros Chondrogiannis1
· Panagiotis Bouros2
· Johann Gamper3
· Ulf Leser4
· David B. Blumenthal5
Received: 20 May 2019 / Accepted: 10 February 2020 © The Author(s) 2020
Abstract In this paper, we investigate the computation of alternative paths between two locations in a road network. More specifically, we study the k-shortest paths with limited overlap (kSPwLO) problem that aims at finding a set of k paths such that all paths are sufficiently dissimilar to each other and as short as possible. To compute kSPwLO queries, we propose two exact algorithms, termed OnePass and MultiPass, and we formally prove that MultiPass is optimal in terms of complexity. We also study two classes of heuristic algorithms: (a) performance-oriented heuristic algorithms that trade shortness for performance, i.e., they reduce query processing time, but do not guarantee that the length of each subsequent result is minimum; and (b) completeness-oriented heuristic algorithms that trade dissimilarity for completeness, i.e., they relax the similarity constraint to return a result that contains exactly k paths. An extensive experimental analysis on real road networks demonstrates the efficiency of our proposed solutions in terms of runtime and quality of the result. Keywords Alternative routing · Road networks · Query services
1 Introduction Computing the shortest path between two locations in a road network is a fundamental problem that has attracted lots of attention by both the research community and industry. However, in many real-world scenarios, determining solely the shortest path is not enough. For instance, users of navigation systems are interested in alternative paths that might be longer than the shortest path but have other desirable properties. Another scenario where alternative routes are useful is
B
Theodoros Chondrogiannis [email protected] Panagiotis Bouros [email protected] Johann Gamper [email protected] Ulf Leser [email protected] David B. Blumenthal [email protected]
1
University of Konstanz, Konstanz, Germany
2
Johannes Gutenberg University Mainz, Mainz, Germany
3
Free University of Bozen-Bolzano, Bolzano, Italy
4
Humboldt-Universität zu Berlin, Berlin, Germany
5
Technical University of Munich, Munich, Germany
transport of humanitarian aid goods through unsafe regions. The distribution of the load to a fleet of vehicles that follow non-overlapping routes increases the chances that at least some of the goods will be delivered. The need for alternative routes also arises in emergency situations, such as natural disasters and terrorist attacks. To avoid panic and potential catastrophic collisions while dealing with the aftermath of such events, evacuation plans should include alternative paths that overlap as little as possible. A first take on providing alternative routes is to solve the K -shortest paths problem [16,23,37]. In most cases though, the returned paths share large stretches, and t
Data Loading...
