Weight-Constrained Route Planning Over Time-Dependent Graphs
Weight-Constrained Route Planning Over Time-Dependent Graphs
复制标题
DOI：
10.1109/icde.2019.00086
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Ye Yuan;Xiang Lian;Guoren Wang;Lei Chen;Yuliang Ma;Yishu Wang
中科院分区：
文献类型：
--
作者：
Ye Yuan;Xiang Lian;Guoren Wang;Lei Chen;Yuliang Ma;Yishu Wang
静态图上的权值约束路径规划（WRP）因其在交通网络中的广泛应用而得到了广泛的研究。然而，真实的交通网络往往随着时间的推移而发展，因此被建模为时间相关图。在本文中，我们研究了大的时间依赖图上的WRP问题，通过将连续的时间和权重函数，大多数现有的工作，时间依赖图上的路径规划是基于先进先出（FIFO）的性质。不幸的是，FIFO属性不适用于我们的问题。为了解决这个问题，我们提出了两个新的路径规划算法，即基线算法和先进的算法。具体而言，高级算法甚至比基线算法更有效，因为高级算法结合了快速遍历方案和时间函数的严格边界以尽可能早地终止遍历。我们通过在真实的数据集上的大量实验证实了我们算法的有效性和效率。
Weight-constrained route planning (WRP) over static graphs has been extensively studied due to its wide application to transportation networks. However, real transportation networks often evolve over time and are thus modeled as time-dependent graphs. In this paper, we study the WRP problem over a large time-dependent graph by incorporating continuous time and weight functions into it. Most existing works regarding route planning over time-dependent graphs are based on the first-in-first-out (FIFO) property. Unfortunately, the FIFO property does not hold for our problem. To solve the problem, we propose two novel route planning algorithms, namely, a baseline algorithm and an advanced algorithm. Specifically, the advanced algorithm is even more efficient than the baseline algorithm, as the advanced algorithm incorporates a fast traversal scheme and tight bounds of time functions to terminate the traversal as early as possible. We confirm the effectiveness and efficiency of our algorithms by extensive experiments on real datasets.