第7卷第2期 智能系统学报 Vol.76.2 2012年4月 CAAI Transactions on Intelligent Systems Apr.2012 D0I:10.3969/i.issn.16734785.201111019 网络出版t地址：htp://www.cnki.net/kcma/detail/23.1538.TP.20120416.0910.004.html 城市交通最优路径算法 陈亮，何为，韩力群 (北京工商大学计算机与信息工程学院，北京100048) 摘要：城市智能交通系统中，最优路径算法及其优化是研究热点之一，是整个交通系统较为核心的部分.结合图论 中最短路径算法，研究了城市交通可达路径算法，并对其进行了有效优化.通过图论中的路径代价函数，提出了城市 最优路径算法，在此基础上，通过优化搜索区域、可达路径的搜索方向以及路网分层搜索等优化策略，达到了优化城 市最优路径算法的目的，提出的城市最优路径及其优化算法能够给出行者提供多条参考的时间最优路线，方便出行 者选择.通过算法的应用实例，验证了城市最优路径及其优化算法的有效性与实时性， 关键词：智能交通：图论：行车路线算法优化：RBF神经网络：最优路径 中图分类号：TP391.4文献标志码：A文章编号：16734785(2012)02016707 Study on an urban transportation optimal path algorithm CHEN Liang,HE Wei,HAN Liqun (College of Computer and Information Engineering,Beijing Commercial and Industrial University,Beijing 100048,China) Abstract:In urban intelligent transportation systems,the optimal path algorithm and its optimization are hot topic and the core of the whole transportation system.By introducing the shortest path algorithm in graph theory,this pa- per first researched the accessible paths for the urban transportation along with an optimization algorithm.Next,by using the path cost function,an optimal path algorithm for urban transportation was proposed.On this basis,by op- timizing the search area,the search direction for accessible paths,and the road network hierarchical search optimi- zation strategy,the goal of optimizing urban paths was attained.The proposed optimal urban path and its optimiza- tion algorithm were able to provide several time-optimal pedestrian paths for references.Through practical applica- tions,the validity and real-time characteristics of the proposed urban optimal path and its optimization algorithm were verified. Keywords:intelligent transportation;graph theory;routing algorithm optimization;optinal path 路径优化是路径规划的核心问题，目前应用最 代价函数值，并按照从小到大的顺序进行排序. 广泛的是1959年Dijkstra1提出并以其名字命名的 在将本文的算法应用至实际交通网络中时，为 Dijkstra算法，可以解决带有非负代价函数值的路网 了避免大规模稀疏网络造成计算时间延长，在应用 中的单源最短路径，但是Dijkstra算法的复杂度为 优化的可达路径算法时，将道路网络分成2个级别， 0(n)2,由于路径规划要求实时性，因此人们在 得到了较好的效果.利用V℃++6.0对算法进行仿 Dijkstra算法基础上进行各种改进，如进行启发式搜 真，将未经优化的算法与优化算法的结果进行比较， 索的A*算法[31、在记忆路径基础上的启发式搜索 并用实例验证，表明本文的算法能够很好地实现实 算法D*算法[4等，但是这些算法通常只给出一条 时性与最优有效性， 最优路径. 本文在路径规划的过程中，利用图的深度优先 1 可达路径优化算法 遍历5算法，寻找源点与终点的所有可达路径，并 1.1各种存储方式的比较 通过限制搜索的路网节点规模和限制搜索方向的规 路径优化问题首先要将实际道路的拓扑结构， 则，进行算法的优化，最后计算得到所有可达路径的 通过一定的计算机存储结构进行映射.主要的存储 收稿日期：2011-11-22.网络出版日期：201204-16 结构形式有邻接矩阵、邻接链表、十字链表、邻接多 通信作者：陈亮.E-mail:newboy_01@163.com 重链表[67」
·168 智能系统学报 第7卷 邻接矩阵的优势在于容易判断2点间的关系，但 选取图中的1、2、3、4、5点作说明，如图2所示 缺点是存储稀疏图所占用的空间过大，并且算法时间 例如：节点1指向节点2、3，那么节点1的指针指向 复杂度较高，为O(n2+m*n),这对于实际应用中具 节点序列中的2、3，依此类推，将转向条件计入在下 有成千上万个节点的交通路网图并不合适.十字链表 一个节点中，就是图2中代价函数值所代表的， 和邻接多重链表要求的存储空间都非常小，但是本身 节点指针节点序列 代价听数值 结构较为复杂，在实际中应用也比较有限. 0 2 空 12右12直 13左13直 邻接链表的实现方法是链表，缺点在于不易判 5 空 21石 空 断2点间的关系，但是对于关联点的查询较为有效， 4 空 24右24直24左 12 空 27石 空 优点是节省存储空间，算法时间复杂度为0(m+ 31右 空 空 粉 n).因此适用于实际交通网络这类大型稀疏图，本 4 34左 空 34右 34直 空 35左 空 空 文采用的存储方式就是邻接链表1」 42左 空 42右 436 1.2路径代价函数值的计算 空 43左 53直53石 空 源点和终点间的所有可达路径中，路径总代价 函数值最小者即为最优路径.可达路径的总代价函 图2前向关联边结构及其对应代价函数值 Fig.2 Associated side of the structure and its cost 数值是全部构成路段的代价函数值的总和，此外，由 function value 于交叉路口对转向的种种限制，延误时间可达到总 根据指针对应的节点序列找到二维数组的行，再 时间的17%~35%[91，因此在计算每条可达路径的 通过下一结点的偏移量找到对应的二维数组的列，即 代价函数值时，还必须考虑交叉口转向因素的影响， 在作者前期的工作中o,已利用RBF神经网 可求出每一段路径的代价函数值，最后将路径中每一 络方法建立了路段的代价函数模型，将5种道路属 路段的代价函数值加起来，就得到了整条路径的代价 性作为影响因素设为RBF网络的输人，网络输出为 函数值，然后根据代价函数值从小到大对可达路径进 路段代价函数值，这5种道路属性包括：道路交通实 行排序并显示出来，供使用者参考选择21」 时路况、车道数、自助红绿灯数、路段长度及车辆转 1.3城市交通可达路径算法的优化 向方向对行车代价函数值的影响，从而为计算整条 本文采用深度优先遍历算法求得交通图中任意 路径的总代价函数值打下了基础. 2点之间的所有可达路径，具体通过深度优先遍历 但是，计算整条路径代价函数值的难度在于每 算法中的迭代算法来实现.迭代算法利用一个堆栈 ·条路段的代价函数值是在已知转向的情况下得到 S来记录访问过程，当初始点（源点）压入栈后，并建 的结果.因此，本文通过建立前向关联边，并采用查 立一个ist[]数组来标记节点是否被访问过，然后 表的方法解决每一条路径总的代价函数值的计 进行迭代，步骤如下： 算们，即将3个点之间的关系两两合并，得出二维 1)检测堆栈是否为空，若堆栈为空，则迭代结 数组的行数和列数，然后将每一段加起来，即可得到 束；否则，进行下一步； 每一条路径的代价函数值.特别地，在终点和它上一 2)访问源点的邻接表中的点，找出isit[v]为0 个节点的代价函数值的计算中，设置了一个数组存 的点v,将其标记为源点的下一节点，并置isit[v] 放最后一段路段的代价，因为通常到达了终点不存 的值为1，判断是否为终点，如是，则弹出终点，并 在选择方向的问题，从而将这个数组中的值设置为 记录路径数组route[],否则进行下一步； 直行的代价函数值.以图1为例，进行简单说明. 3)求v的邻接点表，将v未被访问过的邻接顶 点压入栈，同样进行判断是否为终点，如是终点则 弹出，记录路径，否则进行下一步； 重复进行1)~3)： 设计程序流程如图3所示.在此过程中，每一个 节点都已经记录了上一个节点，即route[v],算法结 束后，逆序打印每一条路径，即可得到图中任意2点 间的所有可达路径 上述算法并不复杂，对于有向图中寻找任意2 图1有向图 Fig.1 Directed graph 点间所有可达路径十分有效.但是该算法存在2个 问题：1)搜索很多冗余可达路径，不符合常理的“绕
第2期 陈亮，等：城市交通最优路径算法 ·169 路”路径；2)算法的效率有待提高.针对这2个问 1.3.2城市可达路径算法优化 题，本小节将研究优化算法的有效规则 在深度优先遍历搜索可达路径算法的基础上， 开始 结合城市道路交通有向图，制定3条优化规则，分别 是限制搜索区域、限制可达路径的搜索方向、地图分 建立堆栈S. 记录访问过程 级搜索，下面来分别解释这3条优化规则 1)限制搜索区域， 将源点压人栈S 建立isit数组 对于实际节点数量非常庞大的实际交通图，如 对节点进行标记 果遍历所有图中的节点，则将会导致计算量与计算 Y 时间成倍增加，因此，将交通图的搜索区域限制在一 堆栈S是否 为空 定范围内，可以达到交通诱导系统的实时性要 求) 访问当前节，点 指向相邻节点 利用已有的节点坐标信息，将搜索的区域设定 为以源点和终点连线为对角线的矩形范围内，但是 该节点visit 考虑到有时需要从源点先绕行至矩形范围以外的节 被标记 N 访问其他 点路径；因此，将矩形范围扩大一个节点范围，如图 标记该节点 相邻节点 4所示.图中的虚线范围是以源点和终点为对角线 visit] 和邻节点 的矩形，实际限制范围为虚线矩形向外扩一个节点 该节点是终点> 全部被标记> 的距离，即图中粗实线矩形范围！ 。Y Y 将该节点弹出栈， 将栈指针指 可路径 向前一节点 栈指针退回一个节点】 结束 图3可达路径搜索算法流程 图4限制搜索区域 Fig.3 The flowchart of reachable route searching algorithm Fig.4 Limit searching area 1.3.1城市交通有向图映射至邻接链表 2)限制节点的搜索方向. 在作者之前的工作中，已经解决了如何将城 源点与终点之间的距离会呈现东西方向相距较 市交通路网图抽象为城市交通有向图，但是无法以 远，或者南北方向相距较远，例如，驾驶者在由东向 数据元素在存储区中的物理位置来表示元素之间的 西行走东西向较长的道路时，一般情况下不会再想 关系.可达路径算法优化问题，首先要将实际道路的 到往西回绕道路，因此将这种相反的方向限制住.进 拓扑结构通过一定的计算机存储结构进行映射，其 一步，限制节点的2个搜索方向，即以源点和终点连 具体步骤如下： 线为向量，限制这个向量的2个分量：第1种情况， 1)设定节点信息 当源点和终点的距离为南北向相距较远时，禁止方 首先定义节点信息，包括节点号、方位、指向下 向为反向；第2种情况，限制2个方向的示意图如图 一节点、在地图中的横纵坐标 5所示 2)定义栈并将节点压入栈。 将设定好的节点，按照城市交通有向图连接关 系，压入栈中 3)建立前向关联边结构： 根据城市交通有向图，按照1.2节所示，建立前 向关联边结构。 经过这3个步骤，一张城市交通网络有向图已 节点搜索方向 经映射至计算机的存储结构中 (a)限制搜索相反方向节点示意
·170. 智能系统学报 第7卷 命名为A点和B点. 转 2)应用可达路径算法.将一级路网看作二级路 网的子集，应用本文的可达路径优化算法，计算出源 点与A点之间的最优路径，再找到一级路网中A、B 2节点之间的最优路径，最后确定B点与二级路网 节点搜索方向 中的终点之间的最优路径 (b)限制搜索双方向节点示意 开始 确定一级路网 中A点和B,点 图5限制节点搜索方向示意 N& Fig.5 Limit node searching direction diagrams 一级路网A点至 二级路网源点 驾驶者从起点出发时，有时会先向路况较好的 B点最优路径 至A点最优路径 相反方向行驶一段路程，这也可能是最优路径，因此 二级路网B点至 不限制源点的行驶方向， 终点最优路径 结東 3)路网分级搜索。 图7路网分级搜索流程 路网分级方法：交通管理部门将城市道路分为 Fig.7 Road network classification flow chart 4个级别，分别是国道以及城市快速路、城市主干 路、次干路、支路.本文选取了一级路网和二级路网， 2 算法有效性验证及应用实例 即国道以及城市快速路、城市主干路作为主要研究 2.1算法有效性验证 对象，因为低级别道路的实时交通路况不易获得，所 为了验证算法的有效性以及高效性，本文通过 以暂不将低级别路网考虑进入路径规划中。 建立北京市五环内的高等级道路路网图数据作实 实际的交通路网是庞大的稀疏网络，如果考虑 验，如图8所示.由于选取的道路等级较高，在图中 将所有的道路节点都包含进算法计算最优路径，势 共有9个高级别道路节点，编程工具采用 必会影响算法的效率；因此，采用将路网分级的方 Visual C++6.0,硬件环境为Core2CPU2G,内存 法，减少搜索节点的数量，提高算法效率，城市交通 2 GB. 路网分级示意图如图6所示， 一级路网 二级路网 图6路网分级搜索示意 图8北京市内五环路网 Fig.6 Road network classification search diagram Fig.8 Beijing road network within 5th ring map 具体搜索方法如图7所示，应用本文的可达路 由表1可知，当不加任何限制条件时，运行时间 径搜索算法，计算出源点与A点之间的最优路径， 非常慢，不满足实时性，主要是由于搜索的可达路径 再找到一级路网中A、B2节点之间的最优路径，最 数量非常庞大，当加入限制条件后，可达路径的数量 后确定B点与二级路网中的终点之间的最优路 减少许多，同时仍然能够找到最优路径，这说明不加 径415) 限制条件时，深度优先算法会找出许多不符合实际 情况的道路，因此加一定的限制条件是可行而且必 确定路网范围后，最优路径规划分为2步进行： 要的.第2条规则是限制2个方向，现将限制搜索范 1)确定节点.将距离源点和终点最近的2个二 围作为基础规则，第2条规则与只限制一个方向规 级路网节点看作源点与终点，同样，再分别确定一级 则的差异如表2所示。 路网中，距离二级路网源点和终点最近的节点，分别
第2期 陈亮，等：城市交通最优路径算法 ·171· 表1限制规则结果对比 Table 1 Limit rules results comparison 不加限制规则 限制搜索范围 最优路径 源点 终点 可达路径数 运行时间/min 可达路径数 运行时间/ms 是否在前3位 23 39 905156 15 204 45 食 8 905156 11 336707 397 食 表2单方向与双向限制结果对比 Table 2 One-direction and two-direction limit searching results comparison 单方向限制 双方向限制 源点 最优路径 终点 可达路径数 运行时间/ms 可达路径数 运行时间/ms 是否一致 19 25 528 78 146 16 是 1 6 38526 0.72×10 89 31 是 22 34 9 13 2 0.2 食 0 g 180 39 2 是 1224 227 108 20 是 由表2可知，限制双方向行驶规则的运行时间 较单方向限制的规则成倍地减少，虽然2种规则下 给出的路径排序不完全相同：但是这2种规则下给 出的最优路径是相同的，这就保证了算法的有效性， 而且大大缩短了算法的运行时间，证明了双方向限 制条件符合车辆诱导系统的实时性要求， 2.2应用实例 本文的实例选取的是从北京市大兴区的康盛园 至海淀区的北京工商大学阜成路校区 1)按照最优路径规划的步骤，首先确定节点.图 9(a)中，五角星为源点，一级道路上的节点为A点. (b)一级道路中的A点和B点 经 4 言 5究 (c)一级道路中的B点与终点 图9地图分级搜索路径 (a)源点与一级道路中的A点 Fig.9 Map hierarchical searching diagram 2)分别找出图9(a)、(b)、(c)中的可达路径， 算法的计算时间如表3所示
·172 智能系统学报 第7卷 表3可达路径计算时间 [C]/第一届中国交通地理信息系统技术研讨会.武汉， Table 3 Reachable path calculating time 中国，2007：165-173. 搜索节 REN Gang,WANG Wei.Survey on shortest path algorithms 起始点 终到点 点数 计算时间/ms in transportation modeling[C]//The First Session of the 源点 11 1.6 China Communications Symposium Geographic Information B 15 2.2 System Technology.Wuhan,China,2007:165-173. B 终点 11 1.8 [9]CALDWELL T.On finding minimum routes in a network 源点 终点 37 5.6 with turn penalties[J].Communication of the ACM,1961, 4(2):107-108. 由表3可知，算法总共的运行时间为5.6ms,主要 [10]陈亮，何为，韩力群.RBF神经网络的行车路径代价函 是由于优化后的算法将搜索的节点数控制在较小的范 数建模[J].智能系统学报，2011,6(5)：424431. 围内，从而达到了提高搜索效率的目的，通过本例，进 CHEN Liang,HE Wei,HAN Liqun.Radial basis function 一步验证了本文所提出算法的有效性与高效性. neural network modeling of the traffic path cost function [J].CAAI Transactions on Intelligent Systems,2011,6 3结束语 (5):424431. [11]刘张雷，史忠科.城市动态时间最短路径诱导系统实 本文提出了一种在城市道路中搜索最优路径的 现研究[J].控制工程，2010,17(3)：351-355 算法，与以往算法不同的是，先考虑了高等级道路网 LIU Zhanglei,SHI Zhongke.Implementation of urban 的特点，由于高等级道路节点较少，再加上可达路径 time-dependent shortest route guidance system[J].Control 算法的优化，因此能够大大降低算法运行的复杂度 Engineering of China,2010,17(3):351-355. 与运算规模，经验证能够保证算法运行的有效性与 [12]万玮，刘晔，李立宏，等.采用联合优化方式的最佳路径 高效性，然后将低等级道路网络与高等级道路网络 算法研究[J].计算机工程与应用，2007,43(30)：97- 100. 联合考虑，在源点和终点分别优化搜索可达路径，保 WAN Wei,LIU Ye,LI Lihong,et al.Reseach on optimal 证了算法应用于整个路网的可行性 path search algorithm adopting union optimization method 参考文献： [J].Computer Engineering and Applications,2007,43 (30):97-100. [1]DIJKSTRA E W.A note on two problems in connection with [13]王亚文，汪西莉，曹菡，等。.一种动态限制搜索区域的最 graphs[J].Numerische Mathematik,1959(1):269-271. 短路径规划算法[J].计算机应用研，2007,24(7)： [2]ZHAO Yilin.Vehicle location and navigation system[M]. 89-91. Boston:Artech House,1997:16-102. WANG Yawen,WANG Xili,CAO Han,et al.Shortest [3]张渭军，王华.城市道路最短路径的Dijkstra算法优化 route-planning algorithm within dynamic restricted search- [J].长安大学学报：自然科学版，2005,25(6)：6265. ing area[J].Application Research of Computer,2007,24 ZHANG Weijun,WANG Hua.Optimation Dijkstra arithme- (7):8991. tic for shortest path of urban traffic net [J].Joumal of [14]苗洋，陈奇.嵌入式环境中分层路径规划算法改进 Chang'an University:Natural Science Edition,2005,25 [J].计算机工程，2010,36(14)：243-245 (6):62-65. MIAO Yang,CHEN Qi.Improvement of hierarchical path [4]姜桂艳，郑祖舵.基于记忆机制的动态交通路径优化算 planning algorithm in embedded environment[J].Comput- 法[J].吉林大学学报：工程技术版，2007,37(5)： er Engineering,2010,36(14):243-245. 1043-1048. [15]苏海滨，张继涛.限制搜索区域的分层路径规划新算 JIANG Guiyan,ZHENG Zuduo.Dynamic traffic path opti- 法[J].河南大学学报：自然科学版，2008,38(1)：81 mization algorithm based on mnemonic mechanism[J]. 84. Journal of Jilin University:Engineering and Technology Edi- SU Haibin,ZHANG Jitao.A new algorithm of hierarchical tion,2007,37(5):1043-1048. route planning with restricted search area[J].Joural of [5]梁磊.两点间所有路径的遍历算法[J].科技信息 Henan University:Natural Science,2008,38(1):81-84. 2010,25(33):86-87. 作者简介： LIANG Lei.All paths between two points of traversal algo- 陈亮，男，1986年生，硕士研究生，主 rithm[J].Science and Technology Information,2010,25 要研究方向为人工神经网络、智能交通. (33):86-87. [6]谭浩强.C++面向对象程序设计[M].北京：清华大学 出版社，2006：2560. [7]严萧敏，吴伟民。数据结构[M].北京：清华大学出版 社，2003：18-190. [8]任刚，王炜.交通建模中的最短路径算法研究综述
第2期 陈亮，等：城市交通最优路径算法 ·173· 何为，男，1953年生，高级工程师， 韩力群，女，1953年生，教授，中国 EEE会员，中国人工智能学会理事，中 人工智能学会副理事长，主要研究方向 国人工智能学会智能产品与产业工作 为智能信息处理与图像工程，主持各类 委员会秘书长.主要研究方向为非电量 科研课题30余项，获国家发明专利3 检测技术、计算机测控技术、嵌入式技 项、北京发明创新大赛银奖1项，发表 术应用，主持或参加国家科技攻关、火 学术论文120余篇，出版著作10部. 炬计划、省部级、横向等各类科研项目 30余项，获国家发明专利3项，发表学术论文30余篇， 2012年第2届EEE云计算与智能系统国际会议 2012 2nd IEEE International Conference on Cloud Computing and Intelligence Systems 2012年第2届EEE云计算与智能系统国际会议(2 nd IEEE CCIS2012)将于2012年10月30一11月1 日在杭州召开.会议由EEE北京分会和中国人工智能学会主办，大会主席由中国人工智能学会理事长李德 毅院士、美国明尼苏达大学David H.C.Du教授(IEEE Fellow)、CISCO Fred Baker博士(CISCO Fellow)和北 京邮电大学杨放春教授(IET Fellow)共同担任. 本次会议主要围绕云计算、云存储、云安全、网络与云计算基础设施、物联网以及人工智能等方面进行广 泛的研讨.会议将聚集国内外相关领域著名学者共同探讨云计算和智能系统的发展方向，并邀请世界知名学 术带头人或企业领袖做特邀报告，为本领域专家、学者以及在校学生提供一个学术交流的平台，促进相关技 术和产业的进一步发展. 本次会议论文将被EI和STP全检，部分优秀文章可推荐发表在SCI检索的国际著名杂志，特此邀请您 在会议网站在线投稿， 根据本次会议的主题，设置了如下相关议题（不限于以下议题）： Artificial intelligence Computational intelligence Mobile intelligent service ·Internet of things Networking and cloud computing infrastructure planning Cloud management and monitoring ·Storage in the cloud Data security in the cloud Cloud computing pricing and economics ·Others 同时会议还专门设立了2个WorkShop对相关技术进行更深入的研讨： WorkShop 1-International Workshop on Future Internet Technologies WorkShop 2-International Workshop on Security in Cloud Computing 会议网址及联系方式： Website:http://conference.bupt.edu.cn/ccis 2012/. E-mail:ccis@bupt.edu.cn. Tel:86-1062281360. Fax:86-10-62282983 重要日期： 提交截止日期：2012年7月15日； 论文接受通知：2012年8月15日； 定稿上传：2012年8月30日； 会议时间：2012年10月30一11月1日