2024/09/25 by Kousik Kumar Dutta, Dutta, Kousik Kumar, Venkata M. V. Gunturi +1
Computer Science · #Data Management and Algorithms #FOS: Computer and information sciences #Other Computer Science (cs.OH) #Semantic Web and Ontologies #Web Applications and Data Management
paper · pdf · doi:10.48550/arxiv.2409.17192
openalex publication_date 2024/09/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Time-Dependent Constrained Path Optimization (TD-CPO) takes the following input: (i) time-dependent (TD) road network, (ii) source (s), (iii) destination (d), (iv) departure time (t) and, (v) budget (B). In TD graph, each edge is characterized by a time-dependent arrival time and a score function. TD-CPO aims to determine a loopless path s--d departing from s at time t and arriving at d on or before t+B while maximizing the score. TD-CPO has applications in urban navigation. TD-CPO is a variant of the Arc Orienteering Problem (AOP) known to be NP-hard in nature. The key computational challenge of TD-CPO is that we need to find the "longest path" in terms of score within the given budget constraint in a TD graph. Current works prune down the search space very aggressively. Thus, despite having low execution time, these algorithms often produce low-quality solutions. In contrast, our proposed approach SCOPE efficiently solves TD-CPO by exploiting road networks' spatial and temporal properties. The inherent computational structure of SCOPE enables trivial parallelization for improved performance. Our experiments indicate that SCOPE produces superior quality solutions (nearly 2x) compared to the state-of-the-art algorithm while having comparable running times. Furthermore, SCOPE exhibits almost linear speedup as the number of CPUs (cores) increases (up to 24 CPUs).