Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

11-2022

Abstract

In many route planning applications, finding constrained shortest paths (CSP) is an important and fundamental problem. CSP aims to find the shortest path between two nodes on a graph while satisfying a path constraint. Solving CSPs requires a large search space and is prohibitively slow on large graphs, even with the state-of-the-art parallel solution on GPUs. The reason lies in the lack of effective navigational information and pruning strategies in the search procedure. In this paper, we propose SPEC, a Shortest Path Enhanced approach for solving the exact CSP problem. Our design rationales of SPEC rely on the observation that the shortest path (SP) provides valuable information in the search procedure of CSP. Hence, we propose a label priority that distinguishes promising candidate paths based on SP. We further devise efficient pruning and teleporting strategies utilizing SP lengths and costs, which eliminates unfeasible paths at an early stage. Furthermore, we observe that the expansion number at each search iteration affects the overall performance significantly. Thus, we devise an adaptive controller based on reinforcement learning. We also show that SPEC works seamlessly with the parallel implementation. Extensive experimental results on 8 read-world graphs reveal that single thread SPEC achieves an order of magnitude speedup over the state-of-the-art GPU-based method. The parallel implementation boosts SPEC 3 to 5 times further.

Keywords

Constrained shortest path, shortest path

Discipline

Numerical Analysis and Scientific Computing | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Data Science and Engineering

Publication

2022 IEEE International Conference on Data Mining (ICDM): Orlando, November 22 - December 1: Proceedings

First Page

588

Last Page

597

ISBN

9781665450997

Identifier

10.1109/ICDM54844.2022.00069

Publisher

IEEE Computer Society

City or Country

Washington, DC

Additional URL

https://doi.org/10.1109/ICDM54844.2022.00069

Download

Share

COinS