Dijkstra算法是1959年由荷兰计算机科学家Dijkstra提出的图论中求最短路径的常用算法^[12], 该算法可求得图中一点到其他任一顶点的最短路径^[13].Dijkstra算法将网络节点分成3部分:未标记节点、临时标记节点和永久标记节点.在网络图中, 将所有节点初始化为未标记节点, 在搜索过程中游历节点和任一路径中相连通的节点为临时标记节点, 每次循环都是把从临时标记节点中搜索距起源点路径长度最短的节点作为永久标记节点, 直至找到目标节点或者所有的节点都成为永久标记节点后才算法结束.如图1所示, 假设节点网络的起源点为节点0, 目标点为节点4, 求节点0到节点4最短路径的距离(各节点间的长度是假设的).

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 路径的节点网络Fig.1 The meshed network of the route

假设每个节点都有一对标号(w_i, p_j), w_i是起源点到目标点的最短路径的长度, w_j是从起源点s到任意节点j的最短路径长度(从顶点到其本身的最短路径是零路(没有弧的路), 其长度等于零), p_j为从起源点s到节点j的最短路径中j点的前一节点.求解从起源点i到目标节点j的最短路径, 基本过程如下:

1)初始化.起源点设置为

①若起源点s最短路径长度w_s=0, p_s为空;

②所有其他节点的路径长度w_i=¥ , p_i=s;

③标记起源点s.记所有已标记的节点k=s, 其他节点设为未标记的.

2)检验从所有已标记的节点k到其直接连接的未标记节点j的距离, 并设置

wj=minwj, wk+dkj(1)

式中:w_j是未标记节点j的最短路径长度; w_k是已标记节点k的最短路径长度; d_kj是从节点k到节点j的直接连接距离.

3)选取下一个点.从所有未标记的节点w_j中, 选取最小的一个标记节点i, 即w_i=minw_j(所有未标记的节点j), 节点i就被选为最短路径中的一点, 并设为已标记的点.

4)找到节点i的前一点.从已标记的节点中找到直接连接到节点i的点j^', 作为前一点, 设置i=j'.

5)标记点i.如果所有节点已标记, 则算法求出最短路径(见表1); 否则, 记k=i, 转到步骤2)再继续.

表1

Tab.1

表1(Tab.1)

表1 0节点到4节点的最短路径 Tab.1 List of the shortest path of node 0 to node 4 循环 节点集s 标记节点数K 节点0到1的 距离D{0} 节点0到1的 距离D{1} 节点0到2的 距离D{2} 节点0到3的 距离D{3} 节点0到4的 距离D{4} 初始化 {0} - 0 10 ∞ 30 100 1 {0, 1} 1 0 10 60 30 100 2 {0, 1, 3} 3 0 10 50 30 90 3 {0, 1, 3, 2} 2 0 10 50 30 60 4 {0, 1, 3, 2, 4} 4 0 10 50 30 60

表1 0节点到4节点的最短路径 Tab.1 List of the shortest path of node 0 to node 4

Dijkstra算法优化思路如下:首先, 从起源点s的临时集合NB_s(与起源点s直接相连的节点集合)中选择距离最小的邻居节点k作为转接点, 同时划归到标识集合S(初始时, 为S{s}); 然后, 对k临时集合与标识集合的差集中节点的值进行更新, 从标识集合S中所有节点的临时集合的并集与标识集合的差集(∪ NB_sS, i∈ S)中选择一个路径距离值最小的节点W_k作为下一个转接点, 并划归到标识集合S中.重复上述过程, 直到所有的节点都被标识过, 即 s=n, 算法结束.

设NB_i为节点i的临时集合, S为标识集合, w_i是从源点s到节点j的最短路径长度, P_i是从s到j的最短路径中j点的前一节点, d_ij是节点i到节点j的距离.算法过程^[14]如下:

1)初始化标识集合S= s, w_i=d_si i∈NBs, 否则w_i=¥ i∉NBs; P_i=s.

2)若k临时集合节点到起源点距离最小d_sk=mind_si, 则S=S∪ k, j∈ NB_s.

3)修改k临时集合节点NB_k=S中的w_i值, w_i=min wi, wk+dki; 若w_i值改变, 则P_j=k, j∈ NB_s-S.

4)选定已标记的临时节点集合NB_i-S i∈S中的w_i最小值, 并将其划归到s中, w_k=minw_i, S=S∪ k; 若 s=n, 节点已标识, 则算法终止, 否则转到步骤3).

对于节点总数为n的网络图, Dijkstra算法求解最短路径总共需要迭代n-1次, 每次迭代都新加一个节点到临时节点集合中, 由于第i次迭代时不在临时节点集合中的节点数为n-i.那么, 第i次迭代需对n-i个节点进行处理的次数为

∑i=1n-1n-i=nn-12(2)

当式(2)中的网络节点数量为n时, 路径求解的时间复杂度为O n2, 即为网络图上从起源点到其余各节点的最短路径求解的时间复杂度.随着节点总数n的增大, 其计算效率和存储效率降低.

时间复杂度O n2取决于转接点k的临时集合NB_s的元素数量, 那么优化算法空间复杂度为O(n× p), 其中p为邻接矩阵存储结构N× N下节点对象所占用的空间, 是常量.另外, 根据网络节点和路段的个数, 可以求出节点的平均出度e, 即

e=mn(3)

式中:m为路段数.

一般在GIS网络关系图中, e∈ [1, 4], 由于步骤3)、步骤4)都是搜索与V_i(i=l, 2, 3, …, n)相邻的节点操作, 时间复杂度均为O(n× e); 步骤4)的时间复杂度为O(m), 即O(n× e).

选取汉中市主城区道路网络作为研究数据, 将高速公路、国道、省道、县道、铁路、主干道、次干道、乡镇道路等矢量要素导入到本地地理数据库.首先, 指定参与道路网络矢量要素的拓扑等级, 设置容限值(限速、限行)和转弯模型, 建立道路弧线段-节点拓扑网络模型; 其次, 根据道路网络节点-弧线段连通规则, 设定费用变量和约束变量, 费用变量为路径成本费用^[15], 约束变量属性字段为布尔值, 即为单行和双行线; 最后, 设定道路网络中路段的行驶方向和节点延迟.通过网络拓扑规则和关系, 建立节点和路段连接的有向网络图, 其模型为

Rw=N, R, LR R=< x, y> |x, y∈N, 且Lx, y LR=lxy|< x, y> ∈R(4)

式中:R_w代表道路网络; N代表节点集; R代表路段集合, 其元素为有序对< x, y> , 且表示由节点x到节点y存在一条有向通路; L_R代表路段的加权长度, 其元素L x, y表示有向路段< x, y> 的加权长度; l_xy为节点x到节点y的任一路段长度.

路段的加权长度L_R是指根据多目标函数和规划要求, 综合各种动态和静态属性约束条件后求解的最优路径^[16], 而并非路径的实际距离或者长度.因此, 最优路径不仅指一般地理空间意义上的距离最短^[17], 还可以引申到时间、费用、线路容量等^[18].

道路网络既有起点、终点、停靠点、路径、路障等, 又有费用成本、等级、限制和描述符^[19].其中, 阻强是网络中的节点或路段因某些突发事件(如交通事故)而不可运行时, 原来获得的最优路径需要进行修正, 具体步骤如下:

1)修路时, 即某个路段不可运行, 属于永久性的.当道路在维修时, 最优路径的距离也随着维修状态而发生改变.

2)交叉路口出现车祸等情况时, 暂时不可通行, 即网络中的节点不可运行, 延长了车辆行驶时间.

任一路径的综合路阻C采用加权求和法计算^[20], 有

C=∑i=1nCi=∑i=1nDi1a1+Di2a2+…+Dijaj(5)

式中:C_i为第i路段的综合路阻; D_ij为第i路段中的路阻因素分值; a_j为第j路阻因素权重.

任一路段路阻因素分值D_ij的计算采用上限测度, 计算公式为

Dij=dij/dj, max(6)

式中:D_ij为第i路段j路阻因素分值; d_ij为路阻因素的实际值; d_{j, max}为第j路阻因素的最大实际值.

假设汉中站为初始源点, 陕西理工大学南校区南门为目标节点, 在任意路口可以调头, 计算汉中站— 陕西理工大学南校区南门的距离和时间最优路径.如图2(a)所示, 在车辆行驶速度理想的状态下, 从汉中站到陕西理工大学南校区南门的距离最短路线长为4 377.8 m, 所用时间成本为10.7 min, 而在时间约束模式下的路线距离为4 384.9 m, 行驶时长最小为9.7 min, 如图2(b)所示.在实际行驶中, 路线选择受驾驶员对时间最短和距离最短的偏好影响.

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 路径选择Fig.2 Route choice

假设在繁杂路口、事故现场、医院等位置节点车流量大, 设置临时障碍点, 短时间内车辆禁止通过, 计算距离最短和时间最短路径.如图3所示, 在障碍路况下, 车辆行驶的最短距离为4 610.3 m, 时间成本为10.7 min; 最短行驶时间为10.2 min, 行驶距离为4 630.6 m, 二者在时间和距离成本上相差不大.这表明, 从汉中站到陕西理工大学南校区南门时, 最优路径的选择受行驶距离或行驶时间成本的影响甚微, 不起决定性作用, 可在时间成本和距离成本模式下自主选择.

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 障碍路况下路径选择Fig.3 Route choice under the barrier

基于道路网络等级、路段限速模式下, 驾驶员在主观意愿上会优先选择省道、国道、城市主干道, 其次选择城市次干道、乡镇道路.假设主干道限速30 km/h、次干道限速25 km/h、省道限速35 km/h, 计算出在限速模式下的最优路径.在限速模式下, 距离最短路径需要行驶4 455.3 m, 行驶时间成本为13.2 min(见图4(a)), 比无约束模式下的时间最短路径多行驶2.3 min.限速模式下的最短时间为10.5 min, 行驶距离为4 739.4 m(见图4(b)), 与最短距离路径模式相比, 时间成本降低了, 距离成本增加了361.5 m.在道路通行能力有限情况下, 尤其在上下班高峰期, 实际的行驶时间与最优路径的行驶时间存在较大差异.而交通路况在非高峰时段, 最优路径与实际行驶时间和距离成本较为接近.

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 限速模式下路径选择Fig.4 Route choice under the speed binit mode

优化后的Dijkstra算法和传统Dijkstra算法, 在计算路径的运行时间和距离最短时, 主要取决于行驶路线的节点数量.时间最短和距离最短路径的求解有不同之处, 主要表现在有向图中每条路段上障碍点、行驶方向、限速的设置.假设每个限速路段节点的延时时间为30 s, 非限速路段的节点处延时25 s, 行驶过程中通过的红绿灯最少, 计算出时间最短路径为18.4 min, 比限速模式下时间最短路径的时间成本多5.2 min, 如图5所示.

图5

Fig.5

	Figure Option ViewDownloadNew Window
	图5 节点延时条件下的距离最短路径Fig.5 The shortest route of distance under the node delay conditions

为检验优化路线的行驶理论时长和实际行驶时长(见表2), 与优化路线的行驶时长相比, 实际行驶时间用时较长, 最小时长差值为1.2 min, 最大时长差值2.9 min.在城市道路网络不限速、不限等级的情况下, 时间最短路径的行驶距离(线2)比距离最短路径的行驶距离(线1)多行驶了7.4 m, 以行驶距离增加和道路等级降低来换取行驶时长最小化.在障碍路况模式下, 线4时间行驶时长比线3的实际行驶时长多了1.0 min, 行驶中的驾驶员对障碍点和路况不熟悉, 实际行驶时长比模型输出的理论行驶时长多用了2.9 min.在限速模式下, 线5中城市车辆的行驶时长实际值受限于道路拥堵、通行能力、路况信息等条件, 比线6实际行驶时长多了1.2 min, 与行驶理论时长多了2.3 min.而在路口节点处延时30 s的情况下, 实际行驶距离较为合理, 实际行驶时长较大.因此, 节点延时、障碍路况、限速限行是影响城市车辆选线的主要因素, 最优路径中节点数量对行驶时长和行驶距离起到主导作用.

表2

Tab.2

表2(Tab.2)

表2 基于Dijkstra算法优化的车辆选线与实际行驶时间对比 Tab.2 Comparison of actual driving time and vehicle routing results after the optimization of Dijkstra algorithm 序号 选线条件 距离/m 行驶理 论时长/ min 实际行 驶时长/ min 行驶时 长差 值/min 节点数 线1 不限道路等级和 行驶速度模式 下的距离最短 4 377.8 10.7 11.9 1.2 19 线2 不限道路等级和 行驶速度模式 下时间最短 4 385.2 9.7 11.5 1.8 17 线3 障碍路况模式 下距离最短 4 610.3 10.7 12.1 1.4 20 线4 障碍路况模式 下时间最短 4 630.6 10.2 13.1 2.9 18 线5 限速限行模式 下距离最短 4 455.2 10.9 13.2 2.3 17 线6 限速限行模式 下时间最短 4 739.3 10.5 12.0 1.5 21 线7 节点处延时30 s 的时间最短 4 463.3 15.9 18.4 2.5 17

表2 基于Dijkstra算法优化的车辆选线与实际行驶时间对比 Tab.2 Comparison of actual driving time and vehicle routing results after the optimization of Dijkstra algorithm