6533b852fe1ef96bd12ab76f
RESEARCH PRODUCT
Most Diverse Near-Shortest Paths
Ernst AlthausTheodoros ChondrogiannisPanagiotis BourosChristian Häckersubject
Mathematical optimizationHeuristic (computer science)Computer sciencemedia_common.quotation_subjectAlternative routing Route planning Path similarity Near-shortest paths Path diversificationConstraint (information theory)Iterated functionBounding overwatchShortest path problemScalabilityQuality (business)ddc:004Routing (electronic design automation)media_commondescription
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. published
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2021-11-02 | Proceedings of the 29th International Conference on Advances in Geographic Information Systems |