城市动态时间最短路径诱导系统实现研究
刘张雷，史忠科
（西北工业大学白动化学院，陕西西安71 0129）
摘 要：就城市路同动态时间最短路径诱导系统的实现展开研究：针对邻接表和邻接矩阵在保存完整的路网信息时出现高冗余并导致算法计算时间成倍增加的现象，以改进的前向关联边结构作为路网的存储结构，并依此对dijkstra算法进行改进，用于路网节点之间动态时间最短路径的求取，在此基础上，基于市区实时交通流数据和相位配时信息，结合高精度交通电子地图，开发了东莞市动态路径诱导系统进行实验仿真。该系统针对改进后的算法与原算法的差异，设置了静态和动态两种最短路径计算模式，对两种模式的计算时间和计算结果进行了对比。结果表明改进算法能够在不增加时间复杂度的前提下，充分考虑动态交通流状况、交叉口限向和转向延误，有效解决城市路网动态时间最短路径问题。
关键词：动态时间最短路径；前向关联边；dijkstra
申图分类号：tp 27 文献标识码：a
1引言
城市路网动态时间最短路径的计算，不仅要考虑交叉口之间路段上的行程时间，还需要考虑交叉口各转向的信号相位延误和转向限制。因此，路网的存储结构不仅要能够存储路段权重，还要体现交叉日节点自身的权重。
解决这个问题的一般思路是通过城市路网转换模型，把节点权重转换为边的权重，从而实现城市路网图向普通赋权有向图的转换，再利用邻接矩阵或邻接表存储转换后的有向图。
本文首先就邻接矩阵或邻接表存储转换路网信息这一方法展开分析，指出了它容易造成存储空间高冗余并导致算法汁算时间成倍增加的弊端。由此，本文采用一种改进的前向关联边结构作为存储结构，同时依照此结构对dijkstra算法进行了改进，并开发了东莞市动态路径诱导系统进行动态时间最短路径求取的实验，实验结果表明改进算法能够在不增加时间复杂度的前提下，充分考虑交叉口限向和转向延误，有效解决城市路网动态时间最短路径问题。
2邻接矩阵或邻接表存储转换路网信息时的弊端
常用的路网模型转换方法有两种：增设虚拟边法和对偶图法。增设虚拟边法根据交叉口实际构造（丁字路口、十字字路口或其他），将此交叉口节点进行一对多的扩展。并将各个可行的转向以虚拟有向线段加以表示，该转向的延误对应于有向线段的权值。利用这种方法，可以从路网图中清晰地看出，交叉口哪些入口禁止左转，同时电能够看到各个直行、左转或右转路线在此交叉口的延误时间。但由于在交叉口进行节点扩展时，它将路网的节点数扩大了8倍。设城市路网包括n个交叉日，由上述分析中已知一个十字路口节点经增设虚拟边处理后变成了8个节点表示，如图l，图2所示．
假设以邻接表：3l存储有向图的方式存储转换后的路网信息，并采用算法复杂度的dijkstra算法进行时问最短路径的计算，所需运算时间相应要扩大64倍。对偶图法是一种新颖的路网结构表示形式，将路段以图中节点表示，交叉日各个路口转向以有向线段表示；路段的权重转化为节点的权熏，交叉口各转向延误转化为相应有向线段的权值。它同样使得路网的节点数成倍地扩张，如果也以邻接表作为存储结构，也会导致计算时间的成倍增长。
3 改进的前向关联边结构
前向关联边结构最早由dial等人在1979年提出。对于n个交叉口，m条路段的城市路网。这种结构利用一个一维数组pointednodes，按n个节点的编号顺序，依次保存从各个节点出发的有向线段的终止节点的编号，同时用另外一个一维数组traveltime来保存各条有向线段的相应权值（对于时问最短路径问题，权值取该路段的行程时间），pointednodes数组和traveltime数组都占用了m个存储单元。由每个节点出发的有向线段不止一条，即路网中各个节点的出度大于等于1，pointednodes数组中对应于每个节点的终止节点的个数也是大于等于1的。前向关联边结构用一维数组pointer，保存各个起始节点所指向的第一个终止节点在数组中的索引值，pointer数组占用的存储单元数与路网节点数是相同的。
|
