城市动态时间较短路径诱导系统实现研究

刘张雷，史忠科
西北工业大学自动化学院，陕西西安

摘　　　要：就城市路网动态时间较短路径诱导系统的实现展开研究。针对邻接表和邻接矩阵在保存完整的路网信息时出现高冗余并导致算法计算时间成倍增加的现象，以改进的前向关联边结构作为路网的存储结构，并依此对Ｄｉｊｋｓｔｒａ算法进行改进，用于路网节点之间动态时间较短路径的求取。在此基础上，基于市区实时交通流数据和相位配时信息，结合高精度交通电子地图，开发了东莞市动态路径诱导系统进行实验仿真。该系统针对改进后的算法与原算法的差异，设置了静态和动态两种较短路径计算模式，对两种模式的计算时间和计算结果进行了对比。结果表明改进算法能够在不增加时间复杂度的前提下，充分考虑动态交通流状况、交叉口限向和转向延误，有效解决城市路网动态时间较短路径问题。

关　键　词：动态时间较短路径；前向关联边；Ｄｉｊｋｓｔｒ

１　引　言
城市路网动态时间较短路径的计算，不仅要考虑交叉口之间路段上的行程时间，还需要考虑交叉口各转向的信号相位延误和转向限制。因此，路网的存储结构不仅要能够存储路段权重，还要体现交叉口节点自身的权重。解决这个问题的一般思路是通过城市路网转换模型，把节点权重转换为边的权重，从而实现城市路网图向普通赋权有向图的转换，再利用邻接矩阵或邻接表存储转换后的有向图。本文首先就邻接矩阵或邻接表存储转换路网信息这一方法展开分析，指出了它容易造成存储空间高冗余并导致算法计算时间成倍增加的弊端。由此，本文采用一种改进的前向关联边结构作为存储结构，同时依照此结构对Ｄｉｊｋｓｔｒａ算法进行了改进，并开发了东莞市动态路径诱导系统进行动态时间较短路径求取的实验，实验结果表明改进算法能够在不增加时间复杂度的前提下，充分考虑交叉口限向和转向延误，有效解决城市路网动态时间较短路径问题。

登录网站后可下载文件

相关阅读:

没有相关新闻...