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. The current state-of-the-art algorithms for this problem are essentially serial in nature and cannot take full advantage (i.e., achieve good load balance) of the increasingly available multi-core systems to solve a CPO query. Our proposed parallel algorithm (with its intelligent task-assignment scheme) achieves both superior solution quality and very low execution times (via good load balancing). Moreover, our approach is also able to demonstrate an almost linear speed-up with an increase in the number of cores.
翻译:限制的路径优化(CPO)问题需要以下投入:(a) 道路网络,以方向图为代表,每个边缘都与“成本”和“核心”价值相关;(b) 源目的地配对,以及(c) 预算价值,这意味着解决方案的最大允许成本。鉴于这一投入,目标是确定一条从源到目的地的路径,最大限度地增加“核心”,同时限制路径在特定预算价值范围内的总“成本”。CPO问题在城市导航中的应用。然而,CPO问题在计算上具有挑战性,因为它可以降低到一个弧方向问题的例子,而这个问题已知是PP-硬的。目前对这一问题的最新算法基本上是序列性的,不能充分利用(即实现良好的负载平衡)日益可利用的多核心系统解决CPO问题。此外,我们提议的平行算法(及其智能任务分配法)既能达到高的解决方案质量,又能达到非常低的执行速度(通过良好的负载平衡,几乎可以显示线性速度增长)。