留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

时间依赖图下的最小费用路径搜索

马慧 汤庸 傅瑜 易锋

马慧, 汤庸, 傅瑜, 易锋. 时间依赖图下的最小费用路径搜索[J]. 电子科技大学学报, 2020, 49(3): 458-466. doi: 10.12178/1001-0548.2019002
引用本文: 马慧, 汤庸, 傅瑜, 易锋. 时间依赖图下的最小费用路径搜索[J]. 电子科技大学学报, 2020, 49(3): 458-466. doi: 10.12178/1001-0548.2019002
MA Hui, TANG Yong, FU Yu, YI Feng. Finding the Minimal Cost Path in Time-Dependent Graphs[J]. Journal of University of Electronic Science and Technology of China, 2020, 49(3): 458-466. doi: 10.12178/1001-0548.2019002
Citation: MA Hui, TANG Yong, FU Yu, YI Feng. Finding the Minimal Cost Path in Time-Dependent Graphs[J]. Journal of University of Electronic Science and Technology of China, 2020, 49(3): 458-466. doi: 10.12178/1001-0548.2019002

时间依赖图下的最小费用路径搜索

doi: 10.12178/1001-0548.2019002
基金项目: 国家自然科学基金(U181120009, 61772211);广东省优秀青年教师基金(YQ2015241)
详细信息
    作者简介:

    马慧(1981-),女,博士,副教授,主要从事数据库理论、大规模图查询方面的研究

    通讯作者: 汤庸,E-mail:ytang@m.scnu.edu.cn
  • 中图分类号: TP311

Finding the Minimal Cost Path in Time-Dependent Graphs

  • 摘要: 该文提出了一种时间依赖图下最小费用路径的高效搜索算法。已有的算法从起点开始向四周扩展以发现到达终点的路径,搜索空间较大,查询耗时。本文从以下两方面减少搜索空间:首先缩小顶点的有效时间区间避免无用的计算,并且在顶点的相应的时间区间的最小费用正确计算出来之后,再计算扩展路径的费用;然后提出一种双向搜索方法,从起点和终点同时出发向四周扩展路径直到两个搜索相遇,从而控制搜索空间在以起点、终点为圆心的两个小圆内。针对路径的时变依赖性设计了双向搜索的停止条件和路径生成方法,理论上证明了方法的正确性。最后,在大规模数据集上测试验证了方法的有效性。
  • 图  1  一个时间依赖图及各条边的费用函数

    图  2  g1→3(t)的过程

    图  3  v0v3的最小费用路径的计算过程

    图  4  k=10下的平均查询时间

    图  5  OL和CA的k=10下的平均查询时间

    图  6  k=10, 20下两种搜索的平均查询时间

    图  7  平均查询时间对比

    表  1  文中常用符号的含义

    符号含义
    Ni+, Ni-分别表示顶点vi的出边邻居和入边邻居的集合
    vs,vd,td,ta查询的起点、终点、最早出发时刻、最晚到达时刻
    wij 通过边〈vi,vj〉的时间
    fij(t)t时刻从vi出发,通过边〈vi,vj〉的费用
    gi(t)t时刻位于vi,到达vd的最小费用
    edti在td时刻从vs出发,从vi出发的最早时刻
    ldti在ta时刻到达vd,从vi出发的最晚时刻
    gij(t)t时刻位于vi,途经〈vi,vj〉到达vd的最小费用
    gi(t)vs出发,在t时刻位于vi的最小费用
    gi(t)t时刻位于vi,到达vd的最小费用
    下载: 导出CSV
  • [1] DIJKSTRA E W. A note on two problems in connection with graphs[J]. Numerische Mathematics, 1959, 1(1): 269-271. doi:  10.1007/BF01386390
    [2] WU L, XIAO X, DENG D, et al. Shortest path and distance queries on road networks: An experimental evaluation[J]. Proceedings of the VLDB Endowment, 2012, 5(5): 406-417. doi:  10.14778/2140436.2140438
    [3] 刘贵松, 解修蕊, 黄海波, 等. 基于最短路径信任关系的推荐项目计算方法[J]. 电子科技大学学报, 2014, 43(2): 162-166. doi:  10.3969/j.issn.1001-0548.2014.02.001

    LIU Gui-song, XIE Xiu-rui, HUANG Hai-bo, et al. Fast computing method for items recommendation based on shortest-path trust relationship[J]. Journal of University of Electronic Science and Technology of China, 2014, 43(2): 162-166. doi:  10.3969/j.issn.1001-0548.2014.02.001
    [4] WU H, CHENG J, HUANG S, et al. Path problems in temporal graphs[J]. Proceedings of the VLDB Endowment, 2014, 7(9): 721-732. doi:  10.14778/2732939.2732945
    [5] WANG S, LIN W, YANG Y, et al. Efficient route planning on public transportation networks: A labelling approach[C]//International Conference on Management of Data. Melbourne, Australia: [s. n.], 2015: 967-982.
    [6] STRASSER B, WAGNER D. Connection scan accelerated[C]//Proceedings of the meeting on Algorithm Engineering and Experimentation. [S. l.]: [ACM], 2014: 125-137.
    [7] IDRI A, OUKARFI M, BOULMAKOUL A, et al. A new time-dependent shortest path algorithm for multimodal transportation network[J]. Procedia Computer Science, 2017, 109: 692-697. doi:  10.1016/j.procs.2017.05.379
    [8] BATZ G V, GEISBERGER R, NEUBAUER S, et al. Time-dependent contraction hierarchies and approximation[C]//Symposium on Experimental and Efficient Algorithms. Heidelberg, Berlin: Springer, 2010: 166-177.
    [9] BAST H, DELLING D, GOLDBERG A V, et al. Route planning in transportation networks[J]. Data Structures and Algorithms, 2016, 9220: 19-80.
    [10] LIU G, QIU Z, QU H, et al. Computing k shortest paths using modified pulse-coupled neural network[J]. Neurocomputing, 2015, 149: 1162-1176.
    [11] LIU G, QIU Z, QU H, et al. Computing k shortest paths from a source node to each other node[J]. Soft Computing, 2015, 19(8): 2391-2402. doi:  10.1007/s00500-014-1434-2
    [12] HU X B, CHIU Y C. A constrained time-dependent k shortest paths algorithm addressing overlap and travel time deviation[J]. International Journal of Transportation Science and Technology, 2015, 4(4): 371-394. doi:  10.1016/S2046-0430(16)30169-1
    [13] 杨雅君, 高宏, 李建中. 时间依赖代价函数下的最优路查询问题研究[J]. 计算机学报, 2012, 35(11): 2247-2264. doi:  10.3724/SP.J.1016.2012.02247

    YANG Ya-jun, GAO Hong, LI Jian-zhong. Finding the optimal path under time-dependent cost function on graphs[J]. Chinese Journal of Computers, 2012, 35(11): 2247-2264. doi:  10.3724/SP.J.1016.2012.02247
    [14] YANG Y, GAO H, YU J X, et al. Finding the cost-optimal path with time constraint over time-dependent graphs[J]. Proceedings of the VLDB Endowment, 2014, 7(9): 673-684. doi:  10.14778/2732939.2732941
    [15] LI L, WEN H, DU X, et al. Minimal on-road time route scheduling on time-dependent graphs[J]. Proceedings of the VLDB Endowment, 2017, 10(11): 1274-1285. doi:  10.14778/3137628.3137638
    [16] LI L, ZHENG K, WANG S, et al. Go slow to go fast: Minimal on-road time route scheduling with parking facilities using historical trajectory[J]. Very Large Data Bases, 2018, 27(3): 321-345. doi:  10.1007/s00778-018-0499-4
    [17] KOMAI Y, NGUYEN D H, HARA T, et al. kNN Search utilizing index of the minimum road travel time in time-dependent road networks[C]//Symposium on Reliable Distributed Systems. [S. l.]: IEEE, 2014: 131-137.
    [18] BISWAS S, GANGULY A, SHAH R, et al. Restricted shortest path in temporal graphs[C]//Database and Expert Systems Applications. Hanoi, Vietnam: [s. n.], 2015: 13-27.
    [19] DEAN B C. Algorithms for minimum-cost paths in time-dependent networks with waiting policies[J]. Networks, 2004, 44(1): 41-46. doi:  10.1002/net.20013
    [20] CAI L Y, SHA D. Shortest paths subject to time-varying stochastic transit times[C]//International Conference on Service Systems and Service Management. [S. l.]: IEEE, 2011: 1-2.
  • [1] 马闯, 杨晓龙, 张海峰, 李春春.  基于最少边的最短路径扰动 . 电子科技大学学报, 2023, 52(2): 271-279. doi: 10.12178/1001-0548.2022177
    [2] 李林, 范明钰, 郝江涛.  基于对抗攻击的图像隐写策略搜索 . 电子科技大学学报, 2022, 51(2): 259-263. doi: 10.12178/1001-0548.2021335
    [3] 张俐.  基因数据的交互依赖特征选择算法 . 电子科技大学学报, 2022, 51(5): 754-759. doi: 10.12178/1001-0548.2021136
    [4] 李冠中, 李绿周.  精确Grover量子搜索算法概述 . 电子科技大学学报, 2022, 51(3): 342-346. doi: 10.12178/1001-0548.2022100
    [5] 有超群, 李乐民.  SFC限制下的隐私保护型多域最短路问题 . 电子科技大学学报, 2020, 49(4): 537-541. doi: 10.12178/1001-0548.2019190
    [6] 王璞, 熊雨沙, 王骋程, 郑治豪, 鲁恒宇.  基于路径旅行时间分析的交通异常检测方法 . 电子科技大学学报, 2018, 47(6): 869-875. doi: 10.3969/j.issn.1001-0548.2018.06.011
    [7] 刘强, 陈西宏, 薛伦生, 范玉平, 张群.  基于映射函数的对流层双向时间比对斜延迟分析 . 电子科技大学学报, 2015, 44(5): 689-694. doi: 10.3969/j.issn.1001-0548.2015.05.009
    [8] 刘贵松, 解修蕊, 黄海波, 屈鸿.  基于最短路径信任关系的推荐项目计算方法 . 电子科技大学学报, 2014, 43(2): 162-166. doi: 10.3969/j.issn.1001-0548.2014.02.001
    [9] 张兵, 马新新, 志光.  轻量级RFID双向认证协议设计与分析 . 电子科技大学学报, 2013, 42(3): 425-430. doi: 10.3969/j.issn.1001-0548.2013.03.021
    [10] 薛金蓉, 张洪斌.  等价类中弱函数依赖的粗糙集度量 . 电子科技大学学报, 2013, 42(6): 935-938. doi: 10.3969/j.issn.1001-0548.2013.06.024
    [11] 宋青, 汪小帆.  最短路径算法加速技术研究综述 . 电子科技大学学报, 2012, 41(2): 176-184. doi: 10.3969/j.issn.1001-0548.2012.02.002
    [12] 陈科, 朱清新, 杨曦.  最优搜索机制下寻找最优插入-删除种子 . 电子科技大学学报, 2011, 40(2): 292-295. doi: 10.3969/j.issn.1001-0548.2011.02.027
    [13] 杨力, 马建峰.  可信的智能卡口令双向认证方案 . 电子科技大学学报, 2011, 40(1): 128-133. doi: 10.3969/j.issn.1001-0548.2011.01.024
    [14] 张磊, 陈俊亮, 孟祥武, 沈筱彦, 郭杰.  基于用户偏好的垂直搜索算法 . 电子科技大学学报, 2010, 39(1): 91-96. doi: 10.3969/j.issn.1001-0548.2010.01.021
    [15] 罗航, 黄建国, 龙兵, 王厚军.  用PSO方法搜索基于MLE的ARMA模型参数 . 电子科技大学学报, 2010, 39(1): 65-68. doi: 10.3969/j.issn.1001-0548.2010.01.016
    [16] 王向展, 宁宁, 于奇.  新型分段多分搜索算法高速A/D转换方案 . 电子科技大学学报, 2008, 37(1): 61-64.
    [17] 万仁福, 李方伟, 朱江.  匿名双向认证与密钥协商新协议 . 电子科技大学学报, 2005, 34(1): 61-64.
    [18] 赵建宏, 杨建宇, 雷维礼.  一种新的最短路径算法 . 电子科技大学学报, 2005, 34(6): 778-781.
    [19] 王宏, 王晟, 李乐民.  解决有复杂约束的最短路由问题的算法 . 电子科技大学学报, 2003, 32(3): 267-271.
    [20] 李中桂, 邱昆, 张宏斌, 薛飞.  WDM双纤双向自愈环网的研究 . 电子科技大学学报, 2001, 30(6): 559-562.
  • 加载中
图(7) / 表(1)
计量
  • 文章访问数:  5007
  • HTML全文浏览量:  1704
  • PDF下载量:  46
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-01-21
  • 修回日期:  2020-01-09
  • 网络出版日期:  2020-05-28
  • 刊出日期:  2020-05-01

时间依赖图下的最小费用路径搜索

doi: 10.12178/1001-0548.2019002
    基金项目:  国家自然科学基金(U181120009, 61772211);广东省优秀青年教师基金(YQ2015241)
    作者简介:

    马慧(1981-),女,博士,副教授,主要从事数据库理论、大规模图查询方面的研究

    通讯作者: 汤庸,E-mail:ytang@m.scnu.edu.cn
  • 中图分类号: TP311

摘要: 该文提出了一种时间依赖图下最小费用路径的高效搜索算法。已有的算法从起点开始向四周扩展以发现到达终点的路径,搜索空间较大,查询耗时。本文从以下两方面减少搜索空间:首先缩小顶点的有效时间区间避免无用的计算,并且在顶点的相应的时间区间的最小费用正确计算出来之后,再计算扩展路径的费用;然后提出一种双向搜索方法,从起点和终点同时出发向四周扩展路径直到两个搜索相遇,从而控制搜索空间在以起点、终点为圆心的两个小圆内。针对路径的时变依赖性设计了双向搜索的停止条件和路径生成方法,理论上证明了方法的正确性。最后,在大规模数据集上测试验证了方法的有效性。

English Abstract

马慧, 汤庸, 傅瑜, 易锋. 时间依赖图下的最小费用路径搜索[J]. 电子科技大学学报, 2020, 49(3): 458-466. doi: 10.12178/1001-0548.2019002
引用本文: 马慧, 汤庸, 傅瑜, 易锋. 时间依赖图下的最小费用路径搜索[J]. 电子科技大学学报, 2020, 49(3): 458-466. doi: 10.12178/1001-0548.2019002
MA Hui, TANG Yong, FU Yu, YI Feng. Finding the Minimal Cost Path in Time-Dependent Graphs[J]. Journal of University of Electronic Science and Technology of China, 2020, 49(3): 458-466. doi: 10.12178/1001-0548.2019002
Citation: MA Hui, TANG Yong, FU Yu, YI Feng. Finding the Minimal Cost Path in Time-Dependent Graphs[J]. Journal of University of Electronic Science and Technology of China, 2020, 49(3): 458-466. doi: 10.12178/1001-0548.2019002
  • 最优路径查询有着广泛的应用。近年来,学者们提出了多种最优路径查询算法。针对不同的应用场景,“最优路径”的查询目标也不一样。例如用户希望找到“距离最短”[1-3]、“最快到达”[4-9]或最优k条路径[10-12]等。在一些应用中,用户希望在道路上所花的费用越少越好。例如物流公司的货车在道路上行驶时间越长,耗油量就越大,需要找到一条耗油量最少的路径[13-14]

    上述应用可以用一个时间依赖图来刻画路网,图模型上的每条边附带一个函数fij(t),表示通过边〈vi,vj〉的费用随出发时刻t而变化。给定起点vs和终点vd,查询返回路径P,使得P的费用最小。允许在路径的顶点上停留,以待在合适的时间继续前行[13-20]。本问题的难点在于所研究的路径的费用具有时间依赖性。即从起点vs到顶点vi的最小费用不是一个常数,而是一个以时间为自变量的函数,表示最小费用依赖于时间变化。

    在路网中,每一个顶点都只能通过它的入边邻居到达。若能计算出到达vj的所有入边邻居vi的最小费用,便可计算出到达vj的最小费用。这个求值过程与最短路径的经典算法Dijkstra算法[1]类似。基于此,文献[13-14]采用了类Dijkstra算法求解:从起点开始向四周扩散,按路径费用升序扩展新路径。该方法与Dijkstra算法的区别在于:在传统的静态图下,每个顶点vi在Dijkstra搜索中仅被扩展一次,因为起点vsvi的最短路距离只有一个值,本问题中每个顶点vi会多次被拿出来扩展,因为对于同一顶点的到达时间不同,费用也不同。设c表示满足查询条件的最小费用,所有满足条件gi(t)<c的路径都会被用来扩展新路径,其中gi(t)表示从起点vs出发,在t时刻位于顶点vi的最小费用。

    如果把搜索过程中访问过的顶点在表示路网的图上作标记的话,搜索空间大致分布在以vs为圆心、c为半径的圆内。假设平均每个顶点被扩展k次,搜索量大致用k倍的以c为半径的圆的面积来衡量。为了减少搜索量,可分别从vs和终点vd出发启动正向搜索和逆向搜索,两个搜索交替进行,直到“相遇”为止。“相遇”指找到一个中间点vi,使得正向搜索已求出从vs到达vi的最小费用路径,逆向搜索也求出从vivd的最小费用路径,便可以从已搜索的路径中生成从vsvd的最小费用路径。需说明的是,最小费用路径不一定路过vi,细节将在第4节中讨论。直观上,双向搜索的搜索空间大致位于分别以vsvd为圆心,半径为c/2的两个圆上。假设平均每个顶点被扩展了k次,搜索空间大致等于两个半径为c/2的圆的面积之和的k倍,较单向搜索的搜索量大大减少。

    本文优化了文献[13-14]的算法,并在其基础上提出了双向搜索算法。虽然双向搜索是一种常见的优化算法,但路径费用与时间相关,双向搜索算法的难点在于:路径的费用的时变依赖性给双向搜索的处理细节和终止条件增加了复杂性。

    • 最优路径查询的一个经典问题是静态图上的最短路径查询。现有的方法在大规模路网下,一个查询平均只需数毫秒的时间便可完成[2]。但实际应用中路网具有动态性,边的权值依赖于时间变化。一类时间依赖图基于离散模型,即每一条边的权值依赖于某些离散的出发时间点[4-6]。另一类时间依赖图基于连续模型,即每一条边的权值是一个随时间变化的连续函数[7-8]。由于公共交通网络与路网有着天然的相似性,也有很多工作研究公共交通网络下的最优路径规划问题[9]。上述时间依赖图下的最优路径查询研究的共同点是计算“总耗时最少的路径”,即用到达时刻减去出发时刻衡量路径的耗时。总耗时最少的路径不一定是路径上途经边的费用之和最小的, 因此这些方法不能解决本文研究的问题。

      本文的研究基于文献[13]提出的模型:图中每条边〈vi,vj〉附有一个值wij,表示通过〈vi,vj〉的耗时;另有一个费用函数fij(t),表示通过〈vi,vj〉的费用依赖于顶点vi的出发时刻t,路径允许在顶点上等待,以实现费用最小。在此模型的基础上,文献[14]提出了一种两阶段搜索方法Two-Step,将文献[13]中的每条边的wij扩展成时间依赖函数,并对文献[13]的方法做了改进,包括wi→j是时间依赖函数的场景。文献[15]提出的问题模型与文献[13-14]相似,每条边〈vi,vj〉只有一个函数fij(t),fij(t)表示在t时刻通过〈vi,vj〉的耗时,目标求解路上耗时(on-road travel time)最小的路径,允许路径在顶点上等待。文献[16]在文献[15]的基础上采用车辆的历史轨迹数据来构造时间依赖图,并提出了一种求近似解的算法,加快了查询速度。另有工作研究基于离散时间模型的允许在顶点上等待的最小费用路径查询[18, 20]

    • 本文沿用文献[13]的时间依赖图模型和最小费用路径查询问题的定义。

      定义 1 时间依赖图。时间依赖图是一个有向图,记作GT=(V, E, W, F)。V={vi}是顶点的集合,EV×V是边的集合。〈vi,vj〉∈E表示一条从顶点vi到顶点vj的有向边。每条边〈vi,vj〉附有一个权值wijW,表示通过〈vi,vj〉的耗时;另有函数fij(t)∈F表示在t时刻通过〈vi,vj〉的费用。fij(t)用分段常量函数表示:

      $$f_{i \to j}(t) = \left\{ {\begin{aligned} & {{c_1}}\quad{{t_0} \leqslant t < {t_1}} \\ & {{c_2}}\quad{{t_1} \leqslant t < {t_2}} \\ & \qquad\quad \cdots \\ & {{c_k}}\quad{{t_{k - 1}} \leqslant t < {t_k}} \end{aligned}} \right.$$

      为了表述清晰,假设通过〈vi,vj〉的时间wij是一个非负常数。需说明的是,本文的算法也适用于当wij是一个关于t的函数的情形,只要wij(t)满足FIFO性质:t1<t2t1+wij(t1)<t2+wij(t2),具体改动方法参见文献[14]。

      同文献[13-14]一样,本文假设∀fF的所有分段区间均为左闭右开区间。当任意一端改成开区间或闭区间时,本文讨论的算法依然有效。

      定义 2 路径 P=v1@t1v2@t2→…→vk@tkvk+1是图GT的一条路径,其中〈vi,vi+1〉∈E(1≤ik)。P表示在t1时刻从顶点v1出发,在t1+w1→2时刻到达v2,然后在t2时刻从v2出发,···,到达vk后在tk时刻出发,最后到达vk+1。路径上允许到达顶点vi后,等待一段时间再出发,以期待P的费用更小。P上的时间约束满足ti+wii+1ti+1P的费用记为:

      $$\begin{aligned} {{\rm{cost}}(P)}=& { {f_{1 \to 2}}({t_1}) + {f_{2 \to 3}}({t_2}) + \cdots + {f_{k \to k + 1}}({t_k})} =\\ &\qquad\qquad { \sum\limits_{i = 1}^k {{f_{i \to i + 1}}({t_i})} } \end{aligned}$$

      定义 3 时间依赖图上的具有时间限制的最小费用路径查询。给定一个时间依赖图GT,起点vs,终点vd,时间td、ta,GT上的具有时间限制的费用最小路径查询返回路径P,使得:1)P在td或之后从vs出发,在ta或之前到达vd;2)所有满足条件1)的路径中,P的费用最小。

      图1a显示了一个时间依赖图,边上的数字表示wij图1b图1f为各条边的费用函数。若查询从v0v3的最小费用路径,td=0,ta=10,则P=v0@2→v2@5→v3是其中一个解,cost(P)=5。

      图  1  一个时间依赖图及各条边的费用函数

    • 表 1  文中常用符号的含义

      符号含义
      Ni+, Ni-分别表示顶点vi的出边邻居和入边邻居的集合
      vs,vd,td,ta查询的起点、终点、最早出发时刻、最晚到达时刻
      wij 通过边〈vi,vj〉的时间
      fij(t)t时刻从vi出发,通过边〈vi,vj〉的费用
      gi(t)t时刻位于vi,到达vd的最小费用
      edti在td时刻从vs出发,从vi出发的最早时刻
      ldti在ta时刻到达vd,从vi出发的最晚时刻
      gij(t)t时刻位于vi,途经〈vi,vj〉到达vd的最小费用
      gi(t)vs出发,在t时刻位于vi的最小费用
      gi(t)t时刻位于vi,到达vd的最小费用

      文中变量在表1中给出具体定义。

    • 因为路径的费用与时间相关,所以定义顶点vi的出发时间−最小代价函数为gi(t),表示若在t时刻位于vi,则在ta时刻或之前到达vd的最小费用。在t时刻位于vi,指在t时刻出发,或者在vi上等待至t时刻后的某个时刻出发。

      查询的起始顶点是vs,故搜索的目标是计算gs(t)的最小值。

    • 本节讨论在已知顶点vi的出边邻居的出发时间−最小费用函数的情况下,如何更新gi(t)。用Ni+表示vi的出边邻居的集合。设vjNi+gij(t)表示在t时刻位于vi,途经〈vi,vj〉再从vj到达vd的最小费用。由于从vi出发的路径只能通过Ni+中的顶点到达vd,所以gi(t)的值取决于gij(t) (vjNi+):

      $${g_i}(t) = \min\{ {g_{i \to j}}(t)|{v_j} \in N_i^ + \} $$ (1)

      gi(t)的求解过程可以分成两步:1) 求gij(t);2) 按式(1)更新gi(t)。第1)步的计算如下。

      gi(t)的定义域为[edti,ldti]。各顶点的edti值可以在以wij为边〈vi,vj〉的权值图上,从vs出发调用一次Dijkstra搜索求得;同理,各顶点的ldti值也可以从vd出发调用一次逆向Dijkstra搜索求得。

      若不考虑在vi上等待,有:

      $${g_{i \to j}}(t) = {f_{i \to j}}(t) + {g_j}(t{\rm{ + }}{w_{i \to j}})$$ (2)

      若考虑上在vi上等待,则gij(t)是一个单调递增函数:若t1<t2,则gij(t1)≤gij(t2)。这是因为:若在t2时出发的费用小,则在t1时可以选择等待至t2时才出发。结合式(1)可得,gi(t)也是一个单调递增函数。

      可见gij(t)的计算分成两步:首先通过式(2)计算gij(t),然后将gij(t)变成单调函数。图2为求g1→3(t)的计算过程,已知g3(t)=0。

      图  2  求g1→3(t)的过程

      引理 1 若已知gj(t),上述方法计算的gij(t)是在t时刻位于vi,途经边〈vi,vj〉到达vd的最小费用函数。

    • 回顾查询的目标是求gs(t)的最小值,并非gs(t)在整个定义域上的值。已知gj(t)求gij(t),对gj(t)的定义域按gj(t)的取值分成若干段,按定义域上的取值从小到大的顺序求gij(t)在各分段的值。所以在搜索过程中,也可以先后用gj(t)的某个分段的值计算gij(t),不需要在完整计算出gj(t)后才计算gij(t)。增量式计算的思想是:为了减少计算量,当gj(t)的某个分段的值已被正确计算出来后,才用来计算gij(t)。计算过程如算法1所示。

      算法1 Reverse Search

      输入:GT,起点vs、终点vd、最早出发时刻td、最晚到达时刻ta。

      输出:最小费用。

      1) 分别从vsvd调用Dijkstra搜索,用td、ta求各顶点vi的edti和ldti值。

      2) ∀viV−{vd}, gi(t)=+∞; gd(t)=0; Ti=edti;

      3) 将元组(0, vd, edtd, ldtd)加进H

      4) while (!H.empty()) do

      5) 从H弹出元组(cj, vj, tdj, taj)

      6) if (vj==vs) then return cj

      7) for each viNj do

      8) gij(twij) = fij (twij) + cj, tdjt < taj

      9) 将gij(t)变成单调递增函数,更新gi;

      10) ci = min{gi(t) | Tit}

      11) 设gi(t)取值ci的区间右端点是tai;

      12) 将元组(ci, vi, Ti, tai)加进H

      13) Tj = taj;

      14) cj = min{gj(t) | t≥taj}

      15) 设gj (t)取值cj的区间的右端点是taj;

      16) 将元组(cj, vj, Tj, taj)加进H

      17) return +∞;

      vd以外,各顶点vigi(t)=+∞,表示gi(t)在定义域[edti, ldti]上的取值未确定,Ti的取值将在下文中解释。算法迭代地选取某个顶点vj和相应的时间区间扩展,更新vj的入边邻居的费用,直到找到从vs出发的最小费用路径为止。

      算法维护一个最小堆HH中的每个元素是一个四元组(cj, vj, tdj, taj),表示顶点vj的函数gj(t)在区间[tdj,taj)的取值为cjH中的元组以cj为关键字排序。初始时H仅包含一个元组(0, vd, edtd, ldtd) (第3行)。当(cj, vj, tdj, taj)弹出时,gj(t)在[tdj, taj)区间上的取值已被正确计算出来,为cj,这一点将在定理1中证明。当vs首次弹出时,最小费用路径已找到(第6行)。

      vj不是vs,用vj在[tdj, taj)区间上的取值cj计算gij(t)(第7~12行,详细的计算过程将在下一段讨论)。每个顶点vj附带一个值Tj,表示gj(t)的已确定值的时间区间的右端点。初始时,Tj=edtj。当vj首次从H弹出时,由定理1可知,cjgj(t)的最小值,tajgj(t)=cj的时间区间的右端点,接下来用gj(t)在[edtj, taj)这一段的值计算gij(t)。由于gj(t)是单调递增函数,所以gj(t)的下一个最小值的区间的左端点是taj,于是在第13行令Tj= taj,表示下一步将用gj(t)在[Tj, ·)上的最小值更新gij(t)。因此,(cj, vj, tdj, taj)扩展完毕后,继续找出gj(t)在区间在[Tj, ·)上的最小值cj,将vjcjcj取值对应的时间区间加进H

      扩展vj的详细过程如下。第8)行计算得到的gij(t)并非单调函数,需要把gij(t)变成单调递增函数。按式(1)更新gi(t),之后需要重新找出gi(t)在未确定取值的时间区间上的最小值ci(第10)行)。第12)行中,若H中没有包含顶点是vi的四元组,则将(ci, vi, Ti, tai)加进H;若H中包含顶点是vi的四元组(ci', vi', tdi', tai'),而且费用大于ci,则用(ci, vi, Ti, tai)代替(ci', vi', tdi', tai')。

      计算过程如图3所示。求v0v3的最小费用路径,td=0, ta=10。计算各顶点的最早出发时刻和最晚出发时刻,得到顶点vigi(t)函数的定义域分别是:v0[0,5], v1[3,8], v2[3,8], v3[5,10]。初始时,T0=0, T1=3, T2=3, T3=5。首先,g3(t)=0,H包含四元组(0,v3,5,10)。

      第一次迭代,(0,v3,5,10)从H中弹出。扩展〈v1,v3〉,得到的g1(t)如图3a所示,细实线表示将g1(t)变成单调递增函数,下同。此时g1(t)的最小值是5,所以将元组(5,v1,3,8)加进H。同理,扩展〈v2,v3〉,得到g2(t)如图3b所示,将(3,v2,3,7)加进H

      图  3  v0v3的最小费用路径的计算过程

      第二次迭代,(3,v2,3,7)从H中弹出。扩展〈v0,v2〉,得到g0(t)如图3c所示,将元组(5, v0, 0, 4)加进H。扩展〈v1,v2〉得到的g1(t)无更新。至此,(3,v2,3,7)扩展完毕,将T2改成7。g2(t)在t≥7上的最小值是5,所以将(5,v2,7,8)加进H

      第三次迭代,(5,v0,6,8)从H中弹出,至此已找到v0v3的最小费用5。

    • 算法Reverse Search与Two-Step算法相比,在两方面缩小了搜索空间:1) Reverse Search将gi(t)的定义域缩小至[edti,ldti],而Two-Step把正向搜索的定义域仅限定在[edti,ta]。实际上[ldti, ta]区间上的计算是无意义的。尤其对于路径上靠近起点的顶点vi,其ldti的值可能比ta小很多,且在[ldti, ta]区间上的费用也比小(由于vi靠近起点),这意味着搜索初期用了[ldti, ta]中的一些子区间扩展路径,而这部分扩展是不可能生成在ta前到达终点的路径的;2) 在第8)行,Reverse Search仅用[Tj, taj) 区间计算gij(t),剩余区间[taj, ·)不用。这是因为此时gj(t)在[taj, ·)上的取值尚未确定,仍可能被vj的出边邻居更新,用未确定的值来计算gij(t)也是无意义的。

      证明方法如下。

      定理 1 在Reverse Search中,当(cj, vj, tdj, taj)弹出时,gj(t)函数在[tdj, taj)上的取值已确定,即为cj

      证明:以示区分,用gj(t)表示正确的出发时间−最小费用函数;用gj*(t)表示元组(cj, vj, tdj, taj)弹出时,当前计算出的值。证明gj*(t)=gj(t), tdjt<taj

      采用数学归纳法。首次迭代(0, vd, edti, ldtd)弹出时, gd*(t)=gd(t)=0。假设在前k次迭代中命题成立,现证明第k+1次迭代时命题仍然成立。不妨设存在tj∈[tdj, taj),使得gj*(tj)≠gj(tj)。由于gj(tj)表示正确的最小费用,所以有gj*(tj) >gj(tj)。

      设在tj时刻从vj出发的最小费用路径Pj=vj@tj→···vu@tuvw@tw→···→vd。由于:gj*(t)≠gj(tj)且gd*(t)=gd(t)=0,所以在Pj上,存在两个相邻的顶点vuvwvu在时刻tu出发,vw在时刻tw出发,使得在前k次迭代中,vw的包含tw的时间区间的元组曾经从H中弹出,vu的包含tu的时间区间的元组尚未从H中弹出。分别记Pu(Pw)为Pj上在tu时刻vu出发(在tw时刻vw出发)的子路径。

      每条边上的费用都是非负数,所以cost(Pu)≤cost (Pj)。又因为:cost (Pu)=fuw(tu)+cost (Pw)且Pj是最小费用路径,即cost(Pj)=gj(tj),所以:

      $${f_{u \to w}}({t_u}) + {\rm{cost}}({P_w}) \leqslant {g_j}({t_j})$$ (3)

      gw(tw)是在时刻tw位于vw、到达vd的最小费用,所以gw(tw)≤cost(Pw)。结合式(3),有:

      $${f_{u \to w}}({t_u}) + {g_w}({t_w}) \leqslant {g_j}({t_j})$$ (4)

      vw的包含tw的时间区间的元组从H弹出时,曾用fuw(t)计算guw(t),接着用guw(t)更新gu*(t),因此gu*(tu)≤fuw(tu)+gw*(tw)。按归纳,vw的包含tw的时间区间的元组从H弹出时,gw*(tw)=gw(tw)。因此:

      $$g_u^*({t_u}) \leqslant {f_{u \to w}}({t_u}) + {g_w}({t_w})$$ (5)

      结合式(4)和式(5),可得gu*(tu)≤gj(tj)<gj*(tj)。由于vu的包含tu的时间区间的四元组也未从H弹出,这与“第k+1次迭代时选取vj的包含tj的四元组”矛盾。证毕。

    • 正向搜索计算顶点vi的到达时间−费用函数:gi(t)表示在td时刻或之后从vs出发,若在t时刻位于vi时的最小费用。搜索过程参考第3节的讨论。

      双向搜索的思路是:分别从vsvd启动正向搜索和逆向搜索,两个搜索交替进行,直到两个搜索相遇为止。具体地,用c表示当前找到的路径的最小费用,初始时,c=+∞。用gi(t)表示顶点vi的到达时间−最小费用函数,gi(t)表示vi的出发时间−最小费用函数。分别用HH表示正向搜索和逆向搜索的最小堆。假设当前四元组(cj, vj, tdj, taj)从H弹出,vivj的一个入边邻居。利用算法1更新gi(t)后,利用gi(t)更新c:

      $${c_ \bot } = \min \{ {c_ \bot },g_i^ \to (t_f) + g_i^ \leftarrow (t_b)|t_f \leqslant t_b\} $$ (6)

      双向搜索的终止条件与重构最小费用路径:在搜索过程中,c的值不断地更新。当正向(或逆向)搜索弹出顶点vmid,使得vmid的正向搜索的已确定值的时间区间中存在时间点tf,且vmid的逆向搜索的已确定值的时间区间中存在时间点tb,满足tftb,搜索终止,c即为所求的最小费用。最小费用路径并不一定途经vmid,而是途经令c取得最小值的顶点vi

      设当前从最小堆中弹出顶点v,如何判断v存在时间点tftb$t_f \leqslant t_b $,且$g_i^ \to (t_f) $$ g_i^ \leftarrow (t_b) $的值均已确定回顾在逆向搜索中,每个顶点vi附带一个值Ti(在双向搜索中,记为Ti),表示已确定值的时间区间的右端点;对称地,在正向搜索中,每个顶点vi附带一个值Ti,表示已确定值的时间区间的左端点。在搜索过程中,Ti从初值edti开始递增;Ti从ldti开始递减。当TiTi时,表明存在tftb如上述描述。

      定理 2 当双向搜索算法终止时,所得的c即为最小费用。

      证明:首先,当四元组(cj, vj, tdj, taj)从正向搜索的最小堆H弹出时,gj(t)在[tdj, taj)区间上的取值已确定,即为cj。此证明过程与定理1同理。

      设正向(或逆向)搜索从最小堆中弹出顶点vmid,使得vmid在正向和逆向搜索的已确定值的时间区间存在时间点tftb,满足tftb,搜索终止。假设正确的最小费用是c,分两种情况:1) c=gmid(tf)+gmid(tb);2) c<gmid(tf)+gmid(tb)。

      1) 若c=gmid(tf)+gmid(tb),说明vmid在一条最小费用路径P上,在tf时刻到达vmid,在tb时刻离开vmid。设Pvmid的前驱顶点是vxvmid的后继顶点是vy。若vx在正向搜索中先出堆,vy在逆向搜索中后出堆,则在vx出堆时,由引理1可知,能通过扩展边〈vx, vmid〉正确计算出gmid(tf)的值;之后在vy出堆时,能通过扩展边〈vmidvy〉正确计算出gmid(tb)。再通过式(6)计算出c=gmid(tf)+gmid(tb)。对称地,若vy在逆向搜索中先出堆,vx在正向搜索中后出堆,也能正确计算出c

      2) c<gmid(tf)+gmid(tb)。设P是最小费用路径,即cost(P)=cvkP上的一个顶点,用Pk表示P上从vsvk的那一截前缀路径,Pk表示P上从vkvd的那一截后缀路径。必定存在两个相邻的顶点vxvy,即P=vs@ts→···→vx@txvy@ty→···→vd,使得:

      $${\rm{cost}}(P_x^ \to ) < g_{{\rm{mid}}}^ \to ({t_f})\qquad{\rm{cost}}(P_y^ \to ) \geqslant g_{{\rm{mid}}}^ \to ({t_f})$$ (7)

      Px在时刻tax到达vx,由gx(t)的定义得:

      $$g_x^ \to ({{\rm {ta}}_x}) \leqslant {\rm{cost}}(P_x^ \to ) < g_{{\rm{mid}}}^ \to ({t_f})$$ (8)

      由于cost(P)=cost(Py)+cost(Py),结合本节的假设cost(P)<gmid(tf)+gmid(tb),得:

      $${\rm{cost}}(P_y^ \to ) - g_{{\rm{mid}}}^ \to ({t_f}) < g_{{\rm{mid}}}^ \leftarrow ({t_b}) - {\rm{cost}}(P_y^ \leftarrow )$$ (9)

      结合式(7)和式(9),cost(Py)<gmid(tb)。按gy(ty)的定义,gy(ty)≤cost(Py)。于是,gy(ty)<gmid(tb)。说明在逆向搜索中,vy的包含ty的时间区间的元组比vmid的包含tb的时间区间的元组先出堆。结合定理1和式(8),说明在搜索终止之前:1) vy的包含ty的时间的元组区间曾从H中弹出;2) vx的包含tax的时间区间的元组曾从中H中弹出。不妨设2)先发生,1)后发生。则在1)发生时,gx(tax)已正确计算出来,且在逆向搜索扩展〈vx,vy〉时,也正确计算出gx(tx),此时利用式(6)可算出正确的最小费用c。当1)先发生,2)后发生,也能得出相同的结论。证毕。

    • 实验采用Visual Studio 2017Community C++编写,Windows 10平台运行,机器配置Intel(R) Core(TM) i78700K CPU和64 GB内存。

    • 本文采用两组路网数据集测试(http://www.cs.utah.edu/~lifeifei/SpatialDataset.htm)。OL描述了奥尔登堡的路网,包括6 105个顶点和7 035条边;CA描述了加利福尼亚州的路网,包括20 147个顶点和21 692条边。同文献[13-14]的测试方法,本文在路网的基础上生成时间依赖图。图中每条边〈vi,vj〉的时间代价wij取路网的边的权值。费用函数fij(t)的定义域设为[0, 20 000]。将fij(t)的定义域随机分成k段,每一段上随机生成一个[20, 100]范围内的整数。k分别取10和20。

      分别在OL和CA上随机生成查询集。查询集共包含10 000个查询,随机生成每个查询的起点和终点。首先计算出每个查询的从起点到终点的最快到达时间,近似地用来衡量起点到终点的远近。将这10 000个查询按最快到达时间升序排序,每1 000个查询分成一组,分别将这10组查询记为Q1,Q2, ···, Q10。于是,Q1组内的查询的起点和终点相距较近,Q10组内的相距较远。为了保证大部分查询有解,每个查询的td限定在[0, 10 000]范围,ta在[10 000, 20 000]范围内随机生成。

      实验分别在以下4方面测试算法:1) Reverse Search算法与文献[13-14]的Two-Step算法的效率对比;2)~4)从起点和终点之间的远近、图的规模和费用函数上分段数量k这3方面对比单向(正向)搜索和双向搜索的性能。以示公平,单、双向搜索均使用了第3节提出的增量式搜索方法。算法考察的性能指标为平均每个查询的耗时,以ms为单位。

    • 1) Reverse Search与Two-Step算法效率对比。图4显示了OL数据集k=10的时间依赖图下,Reverse Search和Two-Step对10组查询集的平均耗时。起止点相距越远的查询效率差别越大。这是因为Reverse Search与Two-Step相比,缩小了每个顶点的有效时间区间,而且等某个顶点在某时间段出发的最小费用正确计算出来以后,才用来计算扩展路径的费用。这两个优化能减少部分无用的计算。

      图  4  k=10下的平均查询时间

      2) 起点和终点之间的远近对单向搜索和双向搜索的效率影响。图5显示了OL和CA在k=10的时间依赖图下,查询集Q1,Q2,···,Q10每个查询的平均花费时间,y轴用对数的比例显示。图例标记的前两个字母表示路网名称,S表示单向搜索,B表示双向搜索。随着起点与终点的距离增加,两者的效率差尤为明显。例如在OL数据集下的R1查询集中,单向、双向搜索平均每个查询花费1.25 ms和0.98 ms;在R10查询集中,单向、双向搜索平均每个查询花费15.87 ms和4.18 ms,双向搜索耗时仅是单向搜索的26.3%。造成较大的效率差是因为双向搜索能减少搜索过程中访问的顶点数,而由于搜索过程中一个顶点可能多次被多次访问,每次访问对应不同的时间区间。因此,双向搜索通过减少访问的顶点数提高了查询效率。留意到实验中的单向搜索已经使用了第3节提出的增量式搜索优化。与Two-Step相比,对于查询相距较远的顶点,双向搜索的平均每个查询耗时约是Two-Step的10%。

      图  5  OL和CA的k=10下的平均查询时间

      3) 图的规模对算法效率的影响。从图5显示的数据看出,CA的顶点数和边数约是OL的4倍,但平均查询时间CA约是OL的10倍。而且随着查询起止点的距离增大,两个图上的查询的效率差尤为明显。这是因为图规模变大后,两点之间的可选的路径数暴涨,所以查询也更耗时。

      4) 函数上的分段数量k的影响。图6以CA为例显示了k=10和k=20时的平均查询时间。总体来说,不管用单向搜索还是双向搜索,k越大,平均每个查询时间越长。这是因为在搜索过程中每个顶点会反复从最小堆中弹出,每次弹出的顶点附带不同的时间区间,分段越多顶点上的时间区间也越多,因此顶点反复弹出次数越多。图7从另一个角度展示了当路网与查询集固定的情况下,k=10和k=20下的两种搜索的查询时间对比。有趣的是,不管使用哪种搜索,k变大时引起的平均查询时间增加的比率相对稳定。

      图  6  k=10, 20下两种搜索的平均查询时间

      图  7  平均查询时间对比

    • 本文提出了一种时间依赖图下的最小费用路径查询的高效算法。首先通过缩小顶点的有效时间区间与延迟计算路径费用的方法减少部分无意义的计算;然后提出双向搜索的方法削减了搜索空间,提高了算法的效率。理论上证明了方法的正确性,实践上用真实路网验证了方法的有效性。下一步工作拟进一步将大规模图查询的索引方法引入本问题中,研究在时间依赖图下的最小费用路径索引算法。

参考文献 (20)

目录

    /

    返回文章
    返回