Optimal path algorithm of road network with traffic restriction
-
摘要: 为了解决车辆诱导系统中复杂道路结构表达及因为城市道路交通信号管理而产生的最优路径选择求解的复杂性, 依据图论中最短路径算法的基本原理, 提出了含有禁行路线路网的最优路径求解算法。以行程时间最少为目标, 按照网络转化法把含有禁行路线的路网转化为不含有禁行路线的路网, 采用邻接节点矩阵和邻接节点权矩阵实现了道路节点关系的表达, 改善了传统的Dijkstra算法, 将全局节点路径的求解转化为与求解节点紧密联系的局部区域求解, 将所研究的网络转化方法和改进的路径寻优算法应用于车辆诱导系统。结果表明应用该算法能够在含有禁行路线的路网中求解最优路径, 减少了问题求解的路网节点数, 提高了计算效率。Abstract: Based on the principle of the shortest path algorithm in graphic theory, this paper described the optimal path solution in practical urban road network, which includes traffic control signal. The characteristics of road network with restricted routes were analyzed, the corresponding mathematic model was constructed to convert it into another road network with free routes. The relationship of road network joints was expressed, the traditional Dijkstra algorithm was optimized by dynamic adjacent node relation matrix and adjacent node weight matrix, the corresponding algorithm was constructed. A vehicle guidance system was developed with the optimized Dijkstra algorithm to find the optimal routes in the network. The results indicate that the system can reduce the computation nodes of road networks.
-
Key words:
- traffic planning /
- road network /
- vehicle guidance system /
- optimal path algorithm /
- traffic restriction
-
0. 引言
最优路径的求解是车辆诱导系统的基础技术, 其选择成为出行者关心的一个重要问题[1-3]。在车辆诱导系统中除考虑出发地与目的地之间的路径最短外, 还要考虑行程时间最少、费用最少以及综合费用最少等, 这些不同意义下的最短路径统称为最优路径。在图论中对最短路径问题的求解已经有较为成熟的算法, 但是对于车辆诱导系统而言, 最优路径的求解并不能直接利用图论中最短路径算法, 因为在实际道路条件下, 为了使交通畅通, 交通管理部门制定了许多规则, 其中包括路段单行、路口禁止左转、禁止直行等, 这样就使得表面上连通的道路网络实际上并不连通。因此需要将这种含有交通限制(以下通称为禁行)的道路网络转化为不含禁行路线的道路网络, 然后再用图论中的有关算法进行求解。
1. 不含禁行路线的最优路径求解
本文以行程时间最少来阐述最优路径的求解算法, 其他意义下的最优路径算法与此类似。
不含禁行路线的道路网络是一个三元组G(V, A, M), 其中V是节点集, V={V1, V2, …, Vn}, Vi是节点, n是节点总数目; A是弧集, A={a1, a2, …, am}, ak=〈Vi, Vj〉, m是弧的数目, 即元素ak是以Vi为弧尾以Vj为弧头的有向弧; M是带权邻接矩阵, 其元素Mij≥0, wij为弧〈Vi, Vj〉上的权值
Μij={wij(〈Vi,Vj〉∈A)∞(〈Vi,Vj〉∉A)
不含禁行路线的道路网络最优路径求解, 可以直接利用图论中最短路径算法, 其中比较成熟和效率较高的算法是按路径长度递增的顺序产生最短路径的Dijkstra算法[4-6]。图 1为含有禁行路线的道路网络, 如果不考虑禁行路线, 则节点V1到节点V5的最优路径, 可以直接用Dijkstra算法计算。
2. 含有禁行路线的最优路径算法
实际道路网络中禁行路线主要有2种情况: 第1种情况是某一路段禁止通行, 在图 1中, 如果 < V1, V6 > 弧是一条禁行路线, 只要在道路网络中的邻接矩阵中, 将有向弧 < V1, V6 > 的权值设为无穷大∞, 直接利用Dijkstra算法求解2节点之间的最优路径即可; 第2种情况是某一路口禁止左转, 或禁止右转, 或禁止直行, 在图 1中, 从V1来的车辆在V6处禁行左转, 即 < V1, V6, V5 > 是一条禁行路线。这时就不能简单地在道路网络中将弧 < V1, V6 > 和弧 < V6, V5 > 的权值设为∞, 因为这样设置将会使路线 < V1, V6, V4 > 、 < V2, V6, V5 > 和 < V3, V6, V5 > 也变成禁行路线, 这显然不对。另外, 实际道路网络中在相邻的2个或2个以上路口连续设置禁止左转, 或禁止右转以及禁止直行的情况很少, 即在道路网络中禁行路线包含3条或3条以上弧的情况很少出现, 本文只讨论常见的第2种情况。
2.1 含有禁行路线道路网络的数学描述
与不含禁行路线的道路网络相比, 含有禁行路线的道路网络是一个四元组G(V, A, F, M), 其中V、A、M和不含禁行路线的道路网络中的含义相同; F是禁行路线集, F={f1, f2, …, fl}, F中每一个元素fl是V中某3个元素Vi、Vj、Vk的有序对, 记为fl=〈Vi, Vj, Vk〉, 其中〈Vi, Vj〉∈A, 〈Vj, Vk〉∈A, 若fl=〈Vi, Vk, Vk〉是一条禁行路线, 即表示从节点Vi经有向弧〈Vi, Vj〉到达节点Vj, 再经有向弧〈Vj, Vk〉到达节点Vk的路线是禁行的。
对于含有禁行路线的道路网络, 定义从节点Vs出发, Vt为终点的不含禁行路线的有向路线称为合法的Vs→Vt有向路径, 在所有合法的Vs→Vt有向路径中其所经过的所有有向弧的权重之和最小的路径称为Vs→Vt的最优路径。
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′: 对于节点ak=〈Vi, Vj〉∈V′, al=〈Vp, Vq〉∈V′, 如果al是ak的直接后继, 即Vj=Vp, 且〈Vi, Vj, Vq〉∉F, 则〈ak, al〉∈A′, 即〈ak, al〉是A′中的一条有向弧, 且Mkl′=Mij, 否则〈ak, al〉∉A′, Mkl′=∞。称转化后不含禁行路线的道路网络G′为含禁行路线的道路网络G的转化网络Ⅰ。
定义道路网络中只有出度而没有入度的节点为网络的起点s, 只有入度而没有出度的节点为网络的终点t。
由于原来含有禁行路线的道路网络G的弧集A转化为G′中节点集V′, 使得网络G的起点s和终点t在转化网络Ⅰ中得不到很好体现, 即以起点s为弧尾的弧在转化网络Ⅰ中对应的节点没有直接前驱, 以终点t为弧头的弧在转化网络Ⅰ中对应的节点没有直接后继, 这样使得转化网络Ⅰ成为不连通。以图 1含有禁行路线的道路网络为例, 以原来路网的弧作为转化后网络中的节点, 然后按照上述规则给转化网络的边赋以权值, 便得到图 2的转化网络Ⅰ, 其中节点a1、a5、a6没有直接前驱, a1、a4、a10没有直接后继。这时如果恰好计算这2个节点间的最优路径, 就无法求解。如果要计算这2个节点之间的最优路径, 就需要在转化网络Ⅰ的G′中添加2个虚拟节点a0、am+1, 使a0成为原网络G中以起点为弧尾的弧在转化网络Ⅰ中对应节点的直接前驱, 使am+1成为原网络G中以终点为弧头的弧在转化网络Ⅰ中对应节点的直接后继, 且
Μ´0s={0(a0是as的直接前驱)∞(其他)Μ´t(m+1)={Μit(Vi是Vt的直接前驱)∞(其他)
称添加虚拟节点后的转化网络Ⅰ的G′为原来含有禁行路线道路网络G的转化网络Ⅱ的G″。按照上述添加虚拟节点的方法, 在图 2的转化网络Ⅰ中, a1、a5、a6加上虚拟节点a0, 给a1、a4、a10加上虚拟节点a11, 并且赋以相应的权值, 得到图 3的转化网络Ⅱ。但是在实际应用中所计算的最优路径的2个节点都在所选取的节点范围之内, 即不会恰好是原来道路网络的起点和终点, 故一般不用添加虚拟节点, 进行网络转换。
2.3 用优化的Dijkstra算法求解最优路径
道路网络是一个稀疏网络, 邻接矩阵中很多元素是∞, 占用很多资源, 而实际上, 相互连通的节点间的权值才是有意义的, 因此改变邻接矩阵的存储方式, 可以大大节省存储空间。在实际的道路网络中1个节点最多有5个邻接节点, 因此取5作为邻接矩阵的列数, 道路网络的节点总数作为矩阵的行数, 构造表达节点之间邻接关系的矩阵, 并称之为邻接节点关系矩阵。按照邻接节点关系矩阵中各元素的邻接关系对应弧的权值(以0填充的权值对应∞)构造新的带权邻接矩阵, 并称之为邻接节点权矩阵。用邻接节点关系矩阵和邻接节点权矩阵来表达道路网络, 不但容易描述道路网络节点间的关系, 而且可以节省存储空间, 提高运算速度。
为了提高运行速度, 减少计算时间和所占计算机内存, 可以不事先初始化邻接节点关系矩阵和邻接节点权矩阵。并且对于车辆导航中的最优路径而言, 仅需要从起点至终点的一条最优路径, 没有必要计算从起点至其他各节点的多条最优路径。将Dijkstra算法进行优化, 基本算法如下。
(1) 根据起点Vs和终点Vt所在的地理位置, 求出Vs和Vt之间的直线距离L, 并从2个端点分别延长0.1L, 形成L′, 然后以L′为弦, 以1.5L′为弧长画弧, 以2条弧之间的范围选取包含Vs及Vt的多个节点[7-8], 并赋给一个一维数组Vvertex。
(2) 由数组Vvertex中的节点以及节点之间的权值初始化动态邻接节点关系矩阵M′和邻接节点权矩阵M(i为节点在数组Vvertex中的位置, 且1≤i≤m, 1≤j≤m, m为数组Vvertex中节点的个数)。令V′为数组Vvertex中所有节点的集合, S为已找到从起点Vs出发的最优路径的节点的集合, 其初始化为起点Vs。令一维数组P记录节点的前驱, 并初始化为Pi=-1。
(3) 判断起点Vs的位置, 令Ps=0, 用Di表示起点Vs出发到节点Vi的最短行程时间。
(4) 判断终点Vt的位置, 如果Pt=-1, 则继续, 如果Pt≠-1, 则转到(9)。
(5) 求从起点Vs出发到节点Vi的最短行程时间, 令
Di=min{Msj′Ps≠-1,
1≤j≤5} (Vi∈V′)
(6) 令k=Msj, 如果Pk=-1, 则Pk=i。
(7) 选择j, 使得Mkj=i, 1≤j≤5;并令Mkj′=Mst′=∞。
(8) 修改从Vs出发到集合V′-S上任一节点Vk(k≠i, 且1≤k≤m)可达的最优路径长度。令Mkl′=Mkl′+Di(1≤l≤m), 转到(4)。
(9) 重复(4)~(8)至多m-1次求得从起点Vs至终点Vt的最短行程时间为Dt, 如果没有找到最短路径, 则转到步骤(1)扩大节点范围, 再进行运算。
3. 实例分析
运用Visual B.Net可视化编程及Access数据库技术, 开发了车辆导航系统。在该系统中, 对所在城市含有禁行路线的道路网络进行了转化, 使之成为不含禁行路线的路网, 并按照优化的Dijkstra算法计算最优路径。利用该诱导系统计算出的最优路径见图 4。图 4中出发地(起点)在图的左上角, 目的地(终点)在图的右下角, 图中粗实线为通过优化算法运算得到的从起点到终点的最优路径, 并且以对话框形式给出了导航信息描述。
从图 4中可以看出从起点到终点的最优路径并没有走A→B→E, 虽然这条路径行程时间更少, 而是走A→B→C→D→E。这是因为A→B→E是一条禁行路线, 即来自A→B方向的车辆在路口B禁止右转。另外, 在计算从起点到终点的最优路径时, 程序根据上述设计的算法自动选择了包括起点和终点的部分节点, 而没有按照传统的计算方法, 选择整个路网的节点。图 4所示的测试中, 程序只选择了165个节点, 即由这165个节点形成的邻接权矩阵进行最优路径的计算。而采用经典的Dijkstra算法需要从整个道路网络的3215个节点生成的静态邻接矩阵来计算最优路径。因为该算法的时间复杂度是T(n)=O(n2)(n为节点的个数), 即采用该算法的执行时间与n2成正比, 显然改进的Dijkstra算法运算效率高。
4. 结语
从含有禁行路线的道路网络的转化以及对Dijkstra算法的优化实现了在含有禁行道路网络中车辆诱导系统的最优路径的快速求解和最优路径的指示诱导功能。如果针对城市的交通状况对交通道路网络的弧赋予不同的权值, 就可实现不同意义下的最优路径求解。如果动态地修改交通道路网络弧的权值, 就可实现动态的最优路径求解。
-
[1] 刘灿齐. 车流在交叉口分流向延误的最短路径及算法[J]. 同济大学学报, 2002, 30(1): 52-53. https://www.cnki.com.cn/Article/CJFDTOTAL-TJDZ200201010.htmLIU Can-qi. Shortest path including deday of each flow at intersection and its algorithm[J]. Journal of Tongji University, 2002, 30(1): 52-53. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-TJDZ200201010.htm [2] 郑祖武. 现代城市交通[M]. 北京: 人民交通出版社, 1998. [3] 张长健. 新型交通监控指挥自动化系统设计[J]. 计算机工程与设计, 2001, 22(3): 44-46. https://www.cnki.com.cn/Article/CJFDTOTAL-SJSJ200103011.htmZHANG Chang-jian. A novel traffic monitoring and command automation system design[J]. Computer Engineering and Design, 2001, 22(3): 44-46. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-SJSJ200103011.htm [4] Dial R B. A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees[J]. Network, 1979, 25(3): 215-248. [5] Benjamin Zhan F. Three fastest shortest path algorithms on real road networks[J]. Journal of Geographic Information and Decision Analysis, 1995, 1(1): 69-82. [6] 严尉敏, 吴伟民. 数据结构[M]. 北京: 清华大学出版社, 1997. [7] 张飞舟. 智能交通系统中的公交车辆调度方法研究[J]. 中国公路学报, 2003, 16(2): 82-85. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL200302020.htmZHANG Fei-zhou. Research on dispatching methods of public traffic vehicles in intelligent transport system[J]. China Journal of Highway and Transport, 2003, 16(2): 82-85. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL200302020.htm [8] 李军. 车辆优化调度可视化系统[J]. 交通运输工程学报, 2004, 4(1): 80-83. cle/id/200401020LI Jun. Vehicle visual scheduling system[J]. Journal of Traffic and Transportation Engineering, 2004, 4(1): 80-83. (in Chinese) cle/id/200401020 -