-
最优路径查询有着广泛的应用。近年来,学者们提出了多种最优路径查询算法。针对不同的应用场景,“最优路径”的查询目标也不一样。例如用户希望找到“距离最短”[1-3]、“最快到达”[4-9]或最优k条路径[10-12]等。在一些应用中,用户希望在道路上所花的费用越少越好。例如物流公司的货车在道路上行驶时间越长,耗油量就越大,需要找到一条耗油量最少的路径[13-14]。
上述应用可以用一个时间依赖图来刻画路网,图模型上的每条边附带一个函数fi→j(t),表示通过边〈vi,vj〉的费用随出发时刻t而变化。给定起点vs和终点vd,查询返回路径P,使得P的费用最小。允许在路径的顶点上停留,以待在合适的时间继续前行[13-20]。本问题的难点在于所研究的路径的费用具有时间依赖性。即从起点vs到顶点vi的最小费用不是一个常数,而是一个以时间为自变量的函数,表示最小费用依赖于时间变化。
在路网中,每一个顶点都只能通过它的入边邻居到达。若能计算出到达vj的所有入边邻居vi的最小费用,便可计算出到达vj的最小费用。这个求值过程与最短路径的经典算法Dijkstra算法[1]类似。基于此,文献[13-14]采用了类Dijkstra算法求解:从起点开始向四周扩散,按路径费用升序扩展新路径。该方法与Dijkstra算法的区别在于:在传统的静态图下,每个顶点vi在Dijkstra搜索中仅被扩展一次,因为起点vs到vi的最短路距离只有一个值,本问题中每个顶点vi会多次被拿出来扩展,因为对于同一顶点的到达时间不同,费用也不同。设c⊥表示满足查询条件的最小费用,所有满足条件gi(t)<c⊥的路径都会被用来扩展新路径,其中gi(t)表示从起点vs出发,在t时刻位于顶点vi的最小费用。
如果把搜索过程中访问过的顶点在表示路网的图上作标记的话,搜索空间大致分布在以vs为圆心、c⊥为半径的圆内。假设平均每个顶点被扩展k次,搜索量大致用k倍的以c⊥为半径的圆的面积来衡量。为了减少搜索量,可分别从vs和终点vd出发启动正向搜索和逆向搜索,两个搜索交替进行,直到“相遇”为止。“相遇”指找到一个中间点vi,使得正向搜索已求出从vs到达vi的最小费用路径,逆向搜索也求出从vi到vd的最小费用路径,便可以从已搜索的路径中生成从vs到vd的最小费用路径。需说明的是,最小费用路径不一定路过vi,细节将在第4节中讨论。直观上,双向搜索的搜索空间大致位于分别以vs、vd为圆心,半径为c⊥/2的两个圆上。假设平均每个顶点被扩展了k次,搜索空间大致等于两个半径为c⊥/2的圆的面积之和的k倍,较单向搜索的搜索量大大减少。
本文优化了文献[13-14]的算法,并在其基础上提出了双向搜索算法。虽然双向搜索是一种常见的优化算法,但路径费用与时间相关,双向搜索算法的难点在于:路径的费用的时变依赖性给双向搜索的处理细节和终止条件增加了复杂性。
-
本文沿用文献[13]的时间依赖图模型和最小费用路径查询问题的定义。
定义 1 时间依赖图。时间依赖图是一个有向图,记作GT=(V, E, W, F)。V={vi}是顶点的集合,E⊆V×V是边的集合。〈vi,vj〉∈E表示一条从顶点vi到顶点vj的有向边。每条边〈vi,vj〉附有一个权值wi→j∈W,表示通过〈vi,vj〉的耗时;另有函数fi→j(t)∈F表示在t时刻通过〈vi,vj〉的费用。fi→j(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〉的时间wi→j是一个非负常数。需说明的是,本文的算法也适用于当wi→j是一个关于t的函数的情形,只要wi→j(t)满足FIFO性质:t1<t2↔t1+wi→j(t1)<t2+wi→j(t2),具体改动方法参见文献[14]。
同文献[13-14]一样,本文假设∀f∈F的所有分段区间均为左闭右开区间。当任意一端改成开区间或闭区间时,本文讨论的算法依然有效。
定义 2 路径 P=v1@t1→v2@t2→…→vk@tk→vk+1是图GT的一条路径,其中〈vi,vi+1〉∈E(1≤i≤k)。P表示在t1时刻从顶点v1出发,在t1+w1→2时刻到达v2,然后在t2时刻从v2出发,···,到达vk后在tk时刻出发,最后到达vk+1。路径上允许到达顶点vi后,等待一段时间再出发,以期待P的费用更小。P上的时间约束满足ti+wi→i+1≤ti+1。P的费用记为:
$$\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显示了一个时间依赖图,边上的数字表示wi→j。图1b~图1f为各条边的费用函数。若查询从v0到v3的最小费用路径,td=0,ta=10,则P=v0@2→v2@5→v3是其中一个解,cost(P)=5。
-
表 1 文中常用符号的含义
符号 含义 Ni+, Ni- 分别表示顶点vi的出边邻居和入边邻居的集合 vs,vd,td,ta 查询的起点、终点、最早出发时刻、最晚到达时刻 wi→j 通过边〈vi,vj〉的时间 fi→j(t) 在t时刻从vi出发,通过边〈vi,vj〉的费用 gi(t) t时刻位于vi,到达vd的最小费用 edti 在td时刻从vs出发,从vi出发的最早时刻 ldti 在ta时刻到达vd,从vi出发的最晚时刻 gi→j(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的出边邻居的集合。设vj∈Ni+,gi→j(t)表示在t时刻位于vi,途经〈vi,vj〉再从vj到达vd的最小费用。由于从vi出发的路径只能通过Ni+中的顶点到达vd,所以gi(t)的值取决于gi→j(t) (vj∈Ni+):
$${g_i}(t) = \min\{ {g_{i \to j}}(t)|{v_j} \in N_i^ + \} $$ (1) gi(t)的求解过程可以分成两步:1) 求gi→j(t);2) 按式(1)更新gi(t)。第1)步的计算如下。
gi(t)的定义域为[edti,ldti]。各顶点的edti值可以在以wi→j为边〈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上等待,则gi→j(t)是一个单调递增函数:若t1<t2,则gi→j(t1)≤gi→j(t2)。这是因为:若在t2时出发的费用小,则在t1时可以选择等待至t2时才出发。结合式(1)可得,gi(t)也是一个单调递增函数。
可见gi→j(t)的计算分成两步:首先通过式(2)计算gi→j(t),然后将gi→j(t)变成单调函数。图2为求g1→3(t)的计算过程,已知g3(t)=0。
引理 1 若已知gj(t),上述方法计算的gi→j(t)是在t时刻位于vi,途经边〈vi,vj〉到达vd的最小费用函数。
-
回顾查询的目标是求gs(t)的最小值,并非gs(t)在整个定义域上的值。已知gj(t)求gi→j(t),对gj(t)的定义域按gj(t)的取值分成若干段,按定义域上的取值从小到大的顺序求gi→j(t)在各分段的值。所以在搜索过程中,也可以先后用gj(t)的某个分段的值计算gi→j(t),不需要在完整计算出gj(t)后才计算gi→j(t)。增量式计算的思想是:为了减少计算量,当gj(t)的某个分段的值已被正确计算出来后,才用来计算gi→j(t)。计算过程如算法1所示。
算法1 Reverse Search
输入:GT,起点vs、终点vd、最早出发时刻td、最晚到达时刻ta。
输出:最小费用。
1) 分别从vs和vd调用Dijkstra搜索,用td、ta求各顶点vi的edti和ldti值。
2) ∀vi∈V−{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 vi∈Nj− do
8) gi→j(t−wi→j) = fi→j (t−wi→j) + cj, tdj≤ t < taj
9) 将gi→j(t)变成单调递增函数,更新gi;
10) ci = min{gi(t) | Ti ≤t}
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以外,各顶点vi的gi(t)=+∞,表示gi(t)在定义域[edti, ldti]上的取值未确定,Ti的取值将在下文中解释。算法迭代地选取某个顶点vj和相应的时间区间扩展,更新vj的入边邻居的费用,直到找到从vs出发的最小费用路径为止。
算法维护一个最小堆H,H中的每个元素是一个四元组(cj, vj, tdj, taj),表示顶点vj的函数gj(t)在区间[tdj,taj)的取值为cj。H中的元组以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计算gi→j(t)(第7~12行,详细的计算过程将在下一段讨论)。每个顶点vj附带一个值Tj,表示gj(t)的已确定值的时间区间的右端点。初始时,Tj=edtj。当vj首次从H弹出时,由定理1可知,cj是gj(t)的最小值,taj是gj(t)=cj的时间区间的右端点,接下来用gj(t)在[edtj, taj)这一段的值计算gi→j(t)。由于gj(t)是单调递增函数,所以gj(t)的下一个最小值的区间的左端点是taj,于是在第13行令Tj= taj,表示下一步将用gj(t)在[Tj, ·)上的最小值更新gi→j(t)。因此,(cj, vj, tdj, taj)扩展完毕后,继续找出gj(t)在区间在[Tj, ·)上的最小值cj,将vj、cj和cj取值对应的时间区间加进H。
扩展vj的详细过程如下。第8)行计算得到的gi→j(t)并非单调函数,需要把gi→j(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所示。求v0到v3的最小费用路径,td=0, ta=10。计算各顶点的最早出发时刻和最晚出发时刻,得到顶点vi的gi(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,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中弹出,至此已找到v0到v3的最小费用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) 区间计算gi→j(t),剩余区间[taj, ·)不用。这是因为此时gj(t)在[taj, ·)上的取值尚未确定,仍可能被vj的出边邻居更新,用未确定的值来计算gi→j(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), tdj≤t<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@tu→vw@tw→···→vd。由于:gj*(t)≠gj(tj)且gd*(t)=gd(t)=0,所以在Pj上,存在两个相邻的顶点vu和vw,vu在时刻tu出发,vw在时刻tw出发,使得在前k次迭代中,vw的包含tw的时间区间的元组曾经从H中弹出,vu的包含tu的时间区间的元组尚未从H中弹出。分别记Pu(Pw)为Pj上在tu时刻
从vu出发(在tw时刻 从vw出发)的子路径。 每条边上的费用都是非负数,所以cost(Pu)≤cost (Pj)。又因为:cost (Pu)=fu→w(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弹出时,曾用fu→w(t)计算gu→w(t),接着用gu→w(t)更新gu*(t),因此gu*(tu)≤fu→w(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节的讨论。
双向搜索的思路是:分别从vs和vd启动正向搜索和逆向搜索,两个搜索交替进行,直到两个搜索相遇为止。具体地,用c⊥表示当前找到的路径的最小费用,初始时,c⊥=+∞。用gi→(t)表示顶点vi的到达时间−最小费用函数,gi←(t)表示vi的出发时间−最小费用函数。分别用H→和H←表示正向搜索和逆向搜索的最小堆。假设当前四元组(cj, vj, tdj, taj)从H←弹出,vi是vj的一个入边邻居。利用算法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,满足tf≤tb,搜索终止,c⊥即为所求的最小费用。最小费用路径并不一定途经vmid,而是途经令c⊥取得最小值的顶点vi。
设当前从最小堆中弹出顶点v,如何判断v存在时间点tf与tb,
$t_f \leqslant t_b $ ,且$g_i^ \to (t_f) $ 和$ g_i^ \leftarrow (t_b) $ 的值均已确定回顾在逆向搜索中,每个顶点vi附带一个值Ti(在双向搜索中,记为Ti←),表示已确定值的时间区间的右端点;对称地,在正向搜索中,每个顶点vi附带一个值Ti→,表示已确定值的时间区间的左端点。在搜索过程中,Ti←从初值edti开始递增;Ti→从ldti开始递减。当Ti→≤Ti←时,表明存在tf和tb如上述描述。定理 2 当双向搜索算法终止时,所得的c⊥即为最小费用。
证明:首先,当四元组(cj, vj, tdj, taj)从正向搜索的最小堆H→弹出时,gj→(t)在[tdj, taj)区间上的取值已确定,即为cj。此证明过程与定理1同理。
设正向(或逆向)搜索从最小堆中弹出顶点vmid,使得vmid在正向和逆向搜索的已确定值的时间区间存在时间点tf和tb,满足tf≤tb,搜索终止。假设正确的最小费用是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。设P上vmid的前驱顶点是vx,vmid的后继顶点是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)=c。vk是P上的一个顶点,用Pk→表示P上从vs到vk的那一截前缀路径,Pk←表示P上从vk到vd的那一截后缀路径。必定存在两个相邻的顶点vx、vy,即P=vs@ts→···→vx@tx→vy@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)后发生,也能得出相同的结论。证毕。
Finding the Minimal Cost Path in Time-Dependent Graphs
-
摘要: 该文提出了一种时间依赖图下最小费用路径的高效搜索算法。已有的算法从起点开始向四周扩展以发现到达终点的路径,搜索空间较大,查询耗时。本文从以下两方面减少搜索空间:首先缩小顶点的有效时间区间避免无用的计算,并且在顶点的相应的时间区间的最小费用正确计算出来之后,再计算扩展路径的费用;然后提出一种双向搜索方法,从起点和终点同时出发向四周扩展路径直到两个搜索相遇,从而控制搜索空间在以起点、终点为圆心的两个小圆内。针对路径的时变依赖性设计了双向搜索的停止条件和路径生成方法,理论上证明了方法的正确性。最后,在大规模数据集上测试验证了方法的有效性。Abstract: This paper proposes an efficient search to find a minimal cost path in a time-dependent graph. Current method discovers paths to the destination by expanding discovered paths originated from the source vertex. However, this blind search incurs large searching space, which lowers the query efficiency. The searching space is reduced in the following two ways. Firstly, during the search, the computation is confined within the valid time interval of each vertex to avoid useless computations. Besides, the costs of new expanded paths is computed not until the minimal cost of a path within a time interval of a vertex is correctly computed. Secondly, two searches are respectively invoked from the source vertex and the destination vertex, by which the searching space is roughly located in two small circles centered at the source and the destination. The bi-directional search stopping criteria as well as the way to regenerate the minimal cost path are discussed. The correctness of the proposed method is also theoretically proved. Finally, extensive experiments on large scale datasets confirm the efficiency of the proposed method.
-
Key words:
- bidirectional search /
- piecewise constant function /
- shortest path /
- time-dependent cost
-
表 1 文中常用符号的含义
符号 含义 Ni+, Ni- 分别表示顶点vi的出边邻居和入边邻居的集合 vs,vd,td,ta 查询的起点、终点、最早出发时刻、最晚到达时刻 wi→j 通过边〈vi,vj〉的时间 fi→j(t) 在t时刻从vi出发,通过边〈vi,vj〉的费用 gi(t) t时刻位于vi,到达vd的最小费用 edti 在td时刻从vs出发,从vi出发的最早时刻 ldti 在ta时刻到达vd,从vi出发的最晚时刻 gi→j(t) 在t时刻位于vi,途经〈vi,vj〉到达vd的最小费用 gi→(t) 从vs出发,在t时刻位于vi的最小费用 gi←(t) 在t时刻位于vi,到达vd的最小费用 -
[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.