A parallelizable algorithm for constrained maximization of preferences in large time-dependent graphs
摘要
The growing availability of large-scale transportation data has transformed urban mobility by enabling a wide range of preferences in route choices. One such problem is the maximization of a preference metric (e.g., safety, ease of navigation, or scenic appeal) while adhering to certain upper bound on travel-time. Such route planning problems have diverse use-cases in urban navigation. However, determining routes which maximize a preference metric, while adhering to an upper bound on travel-time, is computationally hard. This problem can be reduced to an instance of the Arc Orienteering Problem (AOP) which is known to be an NP-Hard problem. Although there have been works which attempted to develop heuristics for this problem, they are limited in their solution quality due their myopic search strategy. Moreover, their inherent serial nature limits their ability to harness the benefits of increasingly available parallel processing offered by modern multi-core processors. This shortcoming of the current state of the art severely limits their use in large-scale deployments. To address these limitations, this paper proposes a novel recursive algorithm that explores the solution space more comprehensively while intelligently reusing the intermediate results (across recursive calls) to improve performance. Furthermore, the algorithm’s computational structure is inherently parallelizable, enabling it to fully exploit modern multi-core architectures through existing scheduling frameworks. Extensive experiments on large, real-world road networks demonstrate that this approach yields, on average, a