Finding the most navigable path in road networks

Kaur, Ramneek; Goyal, Vikram; Gunturi, Venkata M.V.

Abstract

Input to the Most Navigable Path (MNP) problem consists of the following: (a) a road network represented as a directed graph, where each edge is associated with numeric attributes of cost and “navigability score” values; (b) a source and a destination and; (c) a budget value which denotes the maximum permissible cost of the solution. Given the input, MNP aims to determine a path between the source and the destination which maximizes the navigability score while constraining its cost to be within the given budget value. The problem can be modeled as the arc orienteering problem which is known to be NP-hard. The current state-of-the-art for this problem may generate paths having loops, and its adaptation for MNP that yields simple paths, was found to be inefficient. In this paper, we propose five novel algorithms for the MNP problem. Our algorithms first compute a seed path from the source to the destination, and then modify the seed path to improve its navigability. We explore two approaches to compute the seed path. For modification of the seed path, we explore different Dynamic Programming based approaches. We also propose an indexing structure for the MNP problem which helps in reducing the running time of some of our algorithms. Our experimental results indicate that the proposed solutions yield comparable or better solutions while being orders of magnitude faster than the current state-of-the-art for large real road networks.

Citation

Kaur, R., Goyal, V., & Gunturi, V. M. (2021). Finding the most navigable path in road networks. GeoInformatica, 25(1), 207-240. https://doi.org/10.1007/s10707-020-00428-5

• Journal Article Type: Article
• Acceptance Date: Nov 5, 2020
• Online Publication Date: Jan 3, 2021
• Publication Date: Jan 1, 2021
• Deposit Date: Sep 27, 2023
• Publicly Available Date: Oct 4, 2023
• Journal: GeoInformatica
• Print ISSN: 1384-6175
• Electronic ISSN: 1573-7624
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 25
• Issue: 1
• Pages: 207-240
• DOI: https://doi.org/10.1007/s10707-020-00428-5
• Keywords: Spatial networks; Road networks; Routing
• Public URL: https://hull-repository.worktribe.com/output/4388301