时间依赖代价函数下的最优路径查询问题研究

Finding the Optimal Path under Time-Dependent Cost Function on Graphs

作者研究了时间依赖图下,具有时间限制的费用代价最优路径的查询问题.目前有关时间依赖图上的最短路径查询的研究工作解决的是最短旅行时间问题(TDSP),这些工作都利用了以下性质:到达某个顶点的最早时刻可以通过到达其邻居的最早时刻计算得出.然而,在计算具有时间限制的费用代价最优路径时,该性质并不成立.因此,目前解决TDSP问题的方法均不能解决文中面对的问题.对此作者提出一个新的算法用于计算时间依赖图模型上的满足时间限制的费用代价最优路径.该算法适用于有向图和无向图.作者证明了算法的时间复杂度和空间复杂度分别为O(knlogn+mk2logk)和O((n+m)k).最后,作者通过真实数据集上的实验,验证了该算法的有效性.

Shortest path query is an important problem in graphs and has been well-studied on static graphs. However, in real applications, the costs of edges in graphs always change over time. We call such graphs as time-dependent graphs. In this paper, we study how to find the optimal path with the minimum cost under time constraint on large time-dependent graphs. Most existing works about time-dependent shortest path problem （TDSP） focus on finding the shortest path with the minimum travel time. All these works utilize the following property., the earliest arriving time of vertex v can be computed by the earliest arriving time of v＇s neighbors. Unfortunately, this property does not hold in our problem. In this paper, we propose a novel algorithm to compute the optimal path with the minimum cost under time constraint. We show the time and space complexity are O（kn logn＋mk21ogk） and O（（n＋m）k） respectively. We confirm the effectiveness and efficiency of our algorithms using real-life datasets in experiments.