Most Diverse Near-Shortest Paths

Abstract

Computing the shortest path in a road network is a fundamental problem that has attracted lots of attention. However, in many real-world scenarios, determining solely the shortest path is not enough as users want to have additional, alternative ways of reaching their destination. In this paper, we investigate a novel variant of alternative routing, termed the k-Most Diverse Near-Shortest Paths (kMDNSP). In contrast to previous work, kMDNSP aims at maximizing the diversity of the recommended paths, while bounding their length based on a user-defined constraint. Our theoretical analysis proves the NP-hardness of the problem at hand. To compute an exact solution to kMDNSP, we present an algorithm which iterates over all paths that abide by the length constraint and generates k-subsets of them as candidate results. Furthermore, in order to achieve scalability, we also design three heuristic algorithms that trade the diversity of the result for performance. Our experimental analysis compares all proposed algorithms in terms of their runtime and the quality of the recommended paths.