论文标题
道路网络上约束路径优化问题的多线程算法
A Multi-Threading Algorithm for Constrained Path Optimization Problem on Road Networks
论文作者
论文摘要
约束路径优化（CPO）问题采用以下输入：（a）作为有向图的道路网络，每个边缘都与“成本”和“得分”值相关联； （b）源用途对和； （c）预算价值，表示解决方案的最大允许成本。鉴于输入，目标是确定从源到目的地的路径，该路径最大化“得分”，同时限制在给定预算值之内的路径的总“成本”。 CPO问题在城市导航中有应用。但是，CPO问题在计算上是具有挑战性的，因为它可以简化为ARC定向问题的实例，该问题已知是NP-HARD。此问题的当前最新算法本质上是串行的，并且无法完全优势（即实现良好的负载平衡）来解决CPO查询。我们提出的并行算法（具有智能任务分配方案）既达到了卓越的解决方案质量，又可以实现非常低的执行时间（通过良好的负载平衡）。此外，我们的方法还能够证明几乎线性的加速，并且核心数量增加。
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.
