期刊
OPERATIONS RESEARCH
卷 70, 期 1, 页码 160-178出版社
INFORMS
DOI: 10.1287/opre.2021.2166
关键词
constrained shortest path; distance oracles; highway dimension
资金
- U.S. Army Research Laboratory [W911NF-17-1-0094]
- National Science Foundation Directorate for Mathematical and Physical Sciences [DMS-1839346, ECCS-1847393, CNS-1955997]
Motivated by the needs of modern transportation service platforms, this study addresses the problem of computing constrained shortest paths at scale using preprocessing techniques. It proposes a scalable algorithm for CSP queries and establishes the relationship between constrained highway dimension and performance. Practical algorithms are developed with additional network clustering heuristics, achieving significant speed improvements compared to existing approaches.
Motivated by the needs of modern transportation service platforms, we study the problem of computing constrained shortest paths (CSP) at scale via preprocessing techniques. Our work makes two contributions in this regard: 1) We propose a scalable algorithm for CSP queries and show how its performance can be parametrized in terms of a new network primitive, the constrained highway dimension. This development extends recent work that established the highway dimension as the appropriate primitive for characterizing the performance of unconstrained shortest-path (SP) algorithms. Our main theoretical contribution is deriving conditions relating the two notions, thereby providing a characterization of networks where CSP and SP queries are of comparable hardness. 2) We develop practical algorithms for scalable CSP computation, augmenting our theory with additional network clustering heuristics. We evaluate these algorithms on real-world data sets to validate our theoretical findings. Our techniques are orders of magnitude faster than existing approaches while requiring only limited additional storage and preprocessing.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据