0.   引言

最优路径的求解是车辆诱导系统的基础技术, 其选择成为出行者关心的一个重要问题^[1-3]。在车辆诱导系统中除考虑出发地与目的地之间的路径最短外, 还要考虑行程时间最少、费用最少以及综合费用最少等, 这些不同意义下的最短路径统称为最优路径。在图论中对最短路径问题的求解已经有较为成熟的算法, 但是对于车辆诱导系统而言, 最优路径的求解并不能直接利用图论中最短路径算法, 因为在实际道路条件下, 为了使交通畅通, 交通管理部门制定了许多规则, 其中包括路段单行、路口禁止左转、禁止直行等, 这样就使得表面上连通的道路网络实际上并不连通。因此需要将这种含有交通限制(以下通称为禁行)的道路网络转化为不含禁行路线的道路网络, 然后再用图论中的有关算法进行求解。

1.   不含禁行路线的最优路径求解

本文以行程时间最少来阐述最优路径的求解算法, 其他意义下的最优路径算法与此类似。

不含禁行路线的道路网络是一个三元组G(V, A, M), 其中V是节点集, V={V₁, V₂, …, V_n}, V_i是节点, n是节点总数目; A是弧集, A={a₁, a₂, …, a_m}, a_k=〈V_i, V_j〉, m是弧的数目, 即元素a_k是以V_i为弧尾以V_j为弧头的有向弧; M是带权邻接矩阵, 其元素M_ij≥0, w_ij为弧〈V_i, V_j〉上的权值

${\rm M}{}_{ij}=\{\begin{array}{cc}w{}_{ij}& (\langle V{}_i,V{}_j\rangle \in A)\\ \infty & (\langle V{}_i,V{}_j\rangle \notin A)\end{array}$

图  1  含有禁行路线的道路网络

Figure  1.  Road network with restricted routes

下载: 全尺寸图片 幻灯片

不含禁行路线的道路网络最优路径求解, 可以直接利用图论中最短路径算法, 其中比较成熟和效率较高的算法是按路径长度递增的顺序产生最短路径的Dijkstra算法^[4-6]。图 1为含有禁行路线的道路网络, 如果不考虑禁行路线, 则节点V₁到节点V₅的最优路径, 可以直接用Dijkstra算法计算。

2.   含有禁行路线的最优路径算法

实际道路网络中禁行路线主要有2种情况: 第1种情况是某一路段禁止通行, 在图 1中, 如果 < V₁, V₆ > 弧是一条禁行路线, 只要在道路网络中的邻接矩阵中, 将有向弧 < V₁, V₆ > 的权值设为无穷大∞, 直接利用Dijkstra算法求解2节点之间的最优路径即可; 第2种情况是某一路口禁止左转, 或禁止右转, 或禁止直行, 在图 1中, 从V₁来的车辆在V₆处禁行左转, 即 < V₁, V₆, V₅ > 是一条禁行路线。这时就不能简单地在道路网络中将弧 < V₁, V₆ > 和弧 < V₆, V₅ > 的权值设为∞, 因为这样设置将会使路线 < V₁, V₆, V₄ > 、 < V₂, V₆, V₅ > 和 < V₃, V₆, V₅ > 也变成禁行路线, 这显然不对。另外, 实际道路网络中在相邻的2个或2个以上路口连续设置禁止左转, 或禁止右转以及禁止直行的情况很少, 即在道路网络中禁行路线包含3条或3条以上弧的情况很少出现, 本文只讨论常见的第2种情况。

2.1   含有禁行路线道路网络的数学描述

与不含禁行路线的道路网络相比, 含有禁行路线的道路网络是一个四元组G(V, A, F, M), 其中V、A、M和不含禁行路线的道路网络中的含义相同; F是禁行路线集, F={f₁, f₂, …, f_l}, F中每一个元素f_l是V中某3个元素V_i、V_j、V_k的有序对, 记为f_l=〈V_i, V_j, V_k〉, 其中〈V_i, V_j〉∈A, 〈V_j, V_k〉∈A, 若f_l=〈V_i, V_k, V_k〉是一条禁行路线, 即表示从节点V_i经有向弧〈V_i, V_j〉到达节点V_j, 再经有向弧〈V_j, V_k〉到达节点V_k的路线是禁行的。

对于含有禁行路线的道路网络, 定义从节点V_s出发, V_t为终点的不含禁行路线的有向路线称为合法的V_s→V_t有向路径, 在所有合法的V_s→V_t有向路径中其所经过的所有有向弧的权重之和最小的路径称为V_s→V_t的最优路径。

2.2   道路网络转化

含有禁行路线的道路网络不能直接利用Dijkstra算法求解2个节点间的最优路径, 因此需要转化为不含禁行路线的道路网络。按下述方法将含有禁行路线的道路网络G(V, A, F, M)转化为不含禁行路线的道路网络G^′(V^′, A^′, M^′)。把G(V, A, F, M)的弧集A转化为G^′(V^′, A^′, M^′)中节点集, 即V^′=A, 按下述规则确定弧集A^′以及邻接矩阵M^′: 对于节点a_k=〈V_i, V_j〉∈V^′, a_l=〈V_p, V_q〉∈V^′, 如果a_l是a_k的直接后继, 即V_j=V_p, 且〈V_i, V_j, V_q〉∉F, 则〈a_k, a_l〉∈A^′, 即〈a_k, a_l〉是A^′中的一条有向弧, 且M_kl^′=M_ij, 否则〈a_k, a_l〉∉A^′, M_kl^′=∞。称转化后不含禁行路线的道路网络G^′为含禁行路线的道路网络G的转化网络Ⅰ。

定义道路网络中只有出度而没有入度的节点为网络的起点s, 只有入度而没有出度的节点为网络的终点t。

由于原来含有禁行路线的道路网络G的弧集A转化为G^′中节点集V^′, 使得网络G的起点s和终点t在转化网络Ⅰ中得不到很好体现, 即以起点s为弧尾的弧在转化网络Ⅰ中对应的节点没有直接前驱, 以终点t为弧头的弧在转化网络Ⅰ中对应的节点没有直接后继, 这样使得转化网络Ⅰ成为不连通。以图 1含有禁行路线的道路网络为例, 以原来路网的弧作为转化后网络中的节点, 然后按照上述规则给转化网络的边赋以权值, 便得到图 2的转化网络Ⅰ, 其中节点a₁、a₅、a₆没有直接前驱, a₁、a₄、a₁₀没有直接后继。这时如果恰好计算这2个节点间的最优路径, 就无法求解。如果要计算这2个节点之间的最优路径, 就需要在转化网络Ⅰ的G^′中添加2个虚拟节点a₀、a_m+1, 使a₀成为原网络G中以起点为弧尾的弧在转化网络Ⅰ中对应节点的直接前驱, 使a_m+1成为原网络G中以终点为弧头的弧在转化网络Ⅰ中对应节点的直接后继, 且

图  2  转化网络Ⅰ

Figure  2.  Converting network Ⅰ

下载: 全尺寸图片 幻灯片

$\begin{array}{l}{\rm M}{}_{0s}^{´}=\{\begin{array}{cc}0\hfill & (a{}_0\text{是}a{}_s\text{的}\text{直}\text{接}\text{前}\text{驱})\hfill \\ \infty \hfill & (\text{其}\text{他})\hfill \end{array}\\ {\rm M}{}_{t(m+1)}^{´}=\{\begin{array}{cc}{\rm M}{}_{it}\hfill & (V{}_i\text{是}V{}_t\text{的}\text{直}\text{接}\text{前}\text{驱})\hfill \\ \infty \hfill & (\text{其}\text{他})\hfill \end{array}\end{array}$

称添加虚拟节点后的转化网络Ⅰ的G^′为原来含有禁行路线道路网络G的转化网络Ⅱ的G^″。按照上述添加虚拟节点的方法, 在图 2的转化网络Ⅰ中, a₁、a₅、a₆加上虚拟节点a₀, 给a₁、a₄、a₁₀加上虚拟节点a₁₁, 并且赋以相应的权值, 得到图 3的转化网络Ⅱ。但是在实际应用中所计算的最优路径的2个节点都在所选取的节点范围之内, 即不会恰好是原来道路网络的起点和终点, 故一般不用添加虚拟节点, 进行网络转换。

图  3  转化网络Ⅱ

Figure  3.  Converting network Ⅱ

下载: 全尺寸图片 幻灯片

2.3   用优化的Dijkstra算法求解最优路径

道路网络是一个稀疏网络, 邻接矩阵中很多元素是∞, 占用很多资源, 而实际上, 相互连通的节点间的权值才是有意义的, 因此改变邻接矩阵的存储方式, 可以大大节省存储空间。在实际的道路网络中1个节点最多有5个邻接节点, 因此取5作为邻接矩阵的列数, 道路网络的节点总数作为矩阵的行数, 构造表达节点之间邻接关系的矩阵, 并称之为邻接节点关系矩阵。按照邻接节点关系矩阵中各元素的邻接关系对应弧的权值(以0填充的权值对应∞)构造新的带权邻接矩阵, 并称之为邻接节点权矩阵。用邻接节点关系矩阵和邻接节点权矩阵来表达道路网络, 不但容易描述道路网络节点间的关系, 而且可以节省存储空间, 提高运算速度。

为了提高运行速度, 减少计算时间和所占计算机内存, 可以不事先初始化邻接节点关系矩阵和邻接节点权矩阵。并且对于车辆导航中的最优路径而言, 仅需要从起点至终点的一条最优路径, 没有必要计算从起点至其他各节点的多条最优路径。将Dijkstra算法进行优化, 基本算法如下。

(1) 根据起点V_s和终点V_t所在的地理位置, 求出V_s和V_t之间的直线距离L, 并从2个端点分别延长0.1L, 形成L^′, 然后以L^′为弦, 以1.5L^′为弧长画弧, 以2条弧之间的范围选取包含V_s及V_t的多个节点^[7-8], 并赋给一个一维数组V_vertex。

(2) 由数组V_vertex中的节点以及节点之间的权值初始化动态邻接节点关系矩阵M^′和邻接节点权矩阵M(i为节点在数组V_vertex中的位置, 且1≤i≤m, 1≤j≤m, m为数组V_vertex中节点的个数)。令V^′为数组V_vertex中所有节点的集合, S为已找到从起点V_s出发的最优路径的节点的集合, 其初始化为起点V_s。令一维数组P记录节点的前驱, 并初始化为P_i=-1。

(3) 判断起点V_s的位置, 令P_s=0, 用D_i表示起点V_s出发到节点V_i的最短行程时间。

(4) 判断终点V_t的位置, 如果P_t=-1, 则继续, 如果P_t≠-1, 则转到(9)。

(5) 求从起点V_s出发到节点V_i的最短行程时间, 令

D_i=min{M_sj^′P_s≠-1,

1≤j≤5} (V_i∈V^′)

(6) 令k=M_sj, 如果P_k=-1, 则P_k=i。

(7) 选择j, 使得M_kj=i, 1≤j≤5;并令M_kj^′=M_st^′=∞。

(8) 修改从V_s出发到集合V^′-S上任一节点V_k(k≠i, 且1≤k≤m)可达的最优路径长度。令M_kl^′=M_kl^′+D_i(1≤l≤m), 转到(4)。

(9) 重复(4)~(8)至多m-1次求得从起点V_s至终点V_t的最短行程时间为D_t, 如果没有找到最短路径, 则转到步骤(1)扩大节点范围, 再进行运算。

3.   实例分析

运用Visual B.Net可视化编程及Access数据库技术, 开发了车辆导航系统。在该系统中, 对所在城市含有禁行路线的道路网络进行了转化, 使之成为不含禁行路线的路网, 并按照优化的Dijkstra算法计算最优路径。利用该诱导系统计算出的最优路径见图 4。图 4中出发地(起点)在图的左上角, 目的地(终点)在图的右下角, 图中粗实线为通过优化算法运算得到的从起点到终点的最优路径, 并且以对话框形式给出了导航信息描述。

图  4  最优路径搜寻

Figure  4.  Optimal route searching

下载: 全尺寸图片 幻灯片

从图 4中可以看出从起点到终点的最优路径并没有走A→B→E, 虽然这条路径行程时间更少, 而是走A→B→C→D→E。这是因为A→B→E是一条禁行路线, 即来自A→B方向的车辆在路口B禁止右转。另外, 在计算从起点到终点的最优路径时, 程序根据上述设计的算法自动选择了包括起点和终点的部分节点, 而没有按照传统的计算方法, 选择整个路网的节点。图 4所示的测试中, 程序只选择了165个节点, 即由这165个节点形成的邻接权矩阵进行最优路径的计算。而采用经典的Dijkstra算法需要从整个道路网络的3215个节点生成的静态邻接矩阵来计算最优路径。因为该算法的时间复杂度是T(n)=O(n²)(n为节点的个数), 即采用该算法的执行时间与n²成正比, 显然改进的Dijkstra算法运算效率高。

4.   结语

从含有禁行路线的道路网络的转化以及对Dijkstra算法的优化实现了在含有禁行道路网络中车辆诱导系统的最优路径的快速求解和最优路径的指示诱导功能。如果针对城市的交通状况对交通道路网络的弧赋予不同的权值, 就可实现不同意义下的最优路径求解。如果动态地修改交通道路网络弧的权值, 就可实现动态的最优路径求解。