A Multi-Threading Algorithm for Constrained Path Optimization Problem on Road Networks

Dutta, Kousik Kumar; Dewan, Ankita; Gunturi, Venkata M.V.

Abstract

The constrained path optimization (CPO) problem takes the following input: (a) a road network represented as a directed graph, where each edge is associated with a “cost” and a “score” value; (b) a source-destination pair and; (c) a budget value, which denotes the maximum permissible cost of the solution. Given the input, the goal is to determine a path from source to destination, which maximizes the “score” while constraining the total “cost” of the path to be within the given budget value. CPO problem has applications in urban navigation. However, the CPO problem is computationally challenging as it can be reduced to an instance of the arc orienteering problem, which is known to be NP-hard. Given its heavy computational nature, the current state-of-the-art algorithms for this problem explore only a limited amount of search space to come up with a solution within a reasonable amount of execution time (around a few seconds). As a result, these algorithms often miss out on promising candidates and thus, result in low solution quality. In contrast, this paper proposes a novel algorithm called Parallel-Spatial-RG, which explores a much larger search space and obtains a significantly better solution quality. By using multiple threads, Parallel-Spatial-RG keeps the execution time within feasible limits by smartly distributing the total workload evenly among all the available threads. Moreover, Parallel-Spatial-RG is also able to demonstrate an almost linear speed-up with an increase in the number of cores.

Citation

Dutta, K. K., Dewan, A., & Gunturi, V. M. (2022, November). A Multi-Threading Algorithm for Constrained Path Optimization Problem on Road Networks. Presented at Web Information Systems Engineering – WISE 2022, Biarritz, France

• Presentation Conference Type: Conference Paper (published)
• Conference Name: Web Information Systems Engineering – WISE 2022
• Start Date: Nov 1, 2022
• End Date: Nov 3, 2022
• Acceptance Date: Jul 22, 2022
• Online Publication Date: Nov 7, 2022
• Publication Date: Nov 6, 2022
• Deposit Date: Sep 27, 2023
• Publisher: Springer Verlag
• Peer Reviewed: Peer Reviewed
• Volume: 13724 LNCS
• Pages: 110-118
• Series Title: Lecture Notes in Computer Science
• Series Number: 13724
• Series ISSN: 0302-9743 ; 1611-3349
• ISBN: 9783031208904
• DOI: https://doi.org/10.1007/978-3-031-20891-1_9
• Public URL: https://hull-repository.worktribe.com/output/4387408