动态路径诱导系统涵义及算法简介
摘要：本文从智能交通系统出发，介绍了国内外智能交通动态路径诱导系统的发展现状，总结了动态路径诱导系统的各组成部分，绘制出CDRGS的框架图；并对实现动态路径诱导系统的模型算法进行了介绍和对比。
关键词：智能交通系统；动态路径诱导；中心式诱导系统；动态路径诱导算法
The introduction of dynamic route guidance system
meaning and algorithm
Abstract：Under the intelligent transportation system, this paper introduces the current situation of intelligent transportation dynamic route guidance system at home and abroad. This article summarizes the component of dynamic route guidance system and draws the frame-chart of CDRGS. The essay compares the algorithms which could realize the dynamic route guidance
Keyword：ITS; dynamic route guidance; CDRGS; algorithm of dynamic route guidance
随着全世界范围内的经济发展、社会进步、城市化进程的加快，人们对交通运输的需求也明显增长与提高，交通运输与社会经济生活的联系也越来越紧密。尤其在大中城市，随着机动车数量的不断增加，交通堵塞、交通事故等问题愈来愈严重，并且由此而引起的能源浪费、环境污染等问题己成为影响社会发展的消极因素。如何解决这些问题已经受到人们越来越多的关注。
1 背景及意义
据统计，目前我国私人汽车拥有量近5年来年均增速超过30%，2009年我国有近1亿人拥有私人小汽车。由于道路资源的有限性，交通拥堵己成为中国大中城市的普遍现象。另据国家环保总局的一项报告称，在中国的大雾天气中，汽油造成的污染占79%，汽车尾气排放正使蓝天变少。汽油和柴油在发动机燃烧时会产生100多种有害物质，危害人体健康。城市中每1000辆汽车每天就排放300公斤一氧化碳、100-200公斤碳氢化合物、50-150公斤氮氧化物。一辆汽车从上路行驶到报废排出的有害气体比其自身的重量大3倍。交通问题作为全球所共同面对的问题，也引起了世界各国的高度重视，城市交通环境的改善已迫在眉睫。一般来讲,改善城市交通不外乎两个方面：一是拓宽现有的道路和修建高等级公路或多修路；二是充分利用现有的交通资源，通过现代高科技使其发挥更高的运转效率。显然,采用传统的多修路和控制车辆增加方式来解决这些问题都十分困难，只有借鉴发达国家的经验，尽快开发应用能够改善道路通行性能的系统和产品，才有可能尽快解决这一日益严重的问题。智能交通系统（Intelligent Transportation Systems, ITS）正是在这种条件下产生和发展起来的。
智能交通系统目前尚无公认的定义。这一方面是因为不同的研究者从不同的角度考虑，对智能交通系统的认识不同；另一方面，智能交通系统本身正处于迅速发展时期，其内涵和外延都处于发展变化之中。
美国手册对智能交通系统给出了如下定义：
智能交通系统由一系列用于运输网络管理的先进技术以及为出行者提供的多种服务组成。ITS技术的基础是以下三大核心要素：信息、通信和集成。信息的采集、处理、融合和服务是ITS的核心。无论是提供信息网络的实时交通状态的信息，还是为制定出行计划提供在线信息，ITS技术都能使管理者、运营者以及个体出行者变得更为信息灵通，相互间能够更为协调,做出更为智能化的决策。
我国智能交通系统体系框架研究报告中对智能交通系统给出了如下定义：在较完善的基础设施（包括道路、港口、机场和通信等）之上，将先进的信息技术、通信技术、控制技术、传感技术和系统综合技术有效得集成、并应用于地面运输系统，从而建立起大范围内发挥作用的、实时、准确、高效的运输系统。
智能交通系统的主要目标就是要充分有效地利用现有的交通资源，使其利用效率最大化。智能交通系统将从缓解交通拥挤、减少交通事故、降低交通环境影响以及提高生产效率等方面产生可观的经济效益。
具体来说,智能交通系统的社会经济效益主要体现在如下几个方面： （1）减少交通拥挤和行车延误；
（2）减少交通事故的发生率、死亡率； （3）产生发展和就业机会的增加； （4）能源消耗量减少、污染程度降低。
2 国内外研究综述
2.1国外车辆路径诱导系统研究情况
车辆路径诱导系统的研究最早始于日本((1973年)，一个称为CACS(Comprehensive Automobile Traffic Control System)的项目首先进行了基于RF射频通信的车载路径诱导系统的开发实验，并得到了可以减少13%的行程时间的结论。在1990年开始的VICS(Vehicle Information and Communication Systems)项目在日本建立了世界上第一个进行交通信息服务的通信系统。VICS采用三种通信方式:安装于道路主要路段的红外信标、安装于乡村区域的道路和高速公路的短波信标以及调频副载波广播。VICS播发的实时交通信息包括:主要地点间的行程时间、交通拥挤、法规、事故、广域的最优路径选择信息和道路施工、天气情况及停车场信息等。目前，高档的VICS车载接收机结合了差分GPS和FM调频副载波接收功能，可以进行车辆导航和路径诱导。日本目前正在部署一种与VICS兼容的加强的交通管理系统UTMS(Urban Traffic Management Systems)，它由5个子系统组成，其中的路径诱导系统是一种交互类型的中心决定式的路径诱导系统，它使用来自于多个信息源的实时交通信息和行程时间数据进行中心决定式的路径诱导。路径诱导系统将交通信息中心收集到的检测器数据转换为路段行程时间数据，以此决定最优路径，所以即使在没有大量探测车辆的系统运行的早期阶段也能够实现动态诱导。该系统在日本东京和长野己经开始运行，但是目前只能在交通主干道上进行动态诱导。日本的动态路径诱导系统DRGS是世界上第一个投入使用的中心式路径诱导系统i。
欧洲的DRGS研究最初是基于红外信标通信展开的。德国和英国分别在80年代末期开发出了用于示范的LISB (Lei-tand Information System Berlin)系统和Autoguide系统，而后英国推出了世界上第一个商用车载路径诱导系统Traffic Master(目前己发展成为具有提供语音信息功能的Traffic mate)。进入90年代，德国西门子公司基于LISB开发的Euro Scout系统(在美国称为AliScout，是一种B-CDRGS)得到一定的应用，但是缺点是需要大量投资用于安装路边的红外信标。目前，德国的STORM项目致力于开发双模式DRGS，即在安装红外信标的区域开发基于红外信标的路径诱导，同时在广域内开发基于RDS-TMC(Radio Data System Traffic
Message Channel)交通广播的路径诱导。目前基于ALERT一协议的交通数据频道RDS-TMC广播已经或者即将在英国、德国、意大利等11个欧洲国家开通，它能够向用户提供交通事故、拥挤、道路施工等信息;另外隶属于PROMETHEUS计划的DMRG(Dual Mode Route Guidance)将静态的自主导航和基于RDS-TMC广播联合起来成为动态的分布式路径诱导系统，扩展的系统可以用GSM代替RDS-TMC系统。从实际应用方面看，依据RDS-TMC设计的安装于高档桥车上的商用路径诱导系统(CARMINAT DYNAGUIDE)等现在不但可以显示/提示交通信息，亦可以实现分布式的动态路径诱导ii。
90年代后，美国开始展开对ITS的研究，并先后进行了Pathfinder, TravTek,iii ADVANCEiv, SEIFTv等以动态路径诱导系统为主要内容的现场运营实验。TravTek系统实现的路径诱导是基于拥挤和事故等实时交通条件进行的，并具有为出行者服务的“黄页”信息，尤其适用于对该地区不熟悉的旅行者使用;在美国芝加哥进行的ADVANCE项目(1991. 7~1996. 12)，为动态路径诱导系统建立了系统性的研究基础，该系统是一种基于实时交通条件(当前路段行程时间)的分布式路径诱导系统;美国随后进行的SW工FT项目(1994. 8~1997. 12)使用高速的调频FM副载波向传呼机式手表、车载专用电台、便携式微机提供实时交通信息，便携式微机可以显示诸如事故报告、检测器数据等信息，可实现分布式的路径诱导;TravInfo项目(1993. 4~ 1998. 12)通过一系列设备，如传呼机、出行者咨询电话系统、车载导航系统和Internet主页向出行者提供及时而准确的多方式信息和动态路径建议，由于无线Internet服务蓬勃发展，因此，基于Internet的这种I-CDRGS富有开发与实用前景。目前美国各地广泛布置了区域性的多方式出行者信息系统，可以提供实时的交通信息，而且Internet上的交通信息资源在美国已十分丰富vi。
2.2 国内车辆路径诱导系统研究情况
我国对车辆路径诱导系统的研究起步较晚，目前正处于对定位系统、电子地图、双向通信等问题的研究阶段，投入使用的基本上都是以无线电广播为基础的初级诱导手段。基于GPS、集群通信的诱导系统正处于研究和实验阶段，而比较全面的城市车辆路径诱导系统的研究还处于初级阶段。
由上海交警总队和同济大学于1995年6月完成的多段接力式动态标志路线诱导系统通过可变标牌和交通广播电台实现交通流的诱导。由于可变标牌路仅显示单一路段交通信息，只适用于诱导路线比较单纯的高速公路网络，而在行驶路径较为复杂的城市路网中则会因为诱导路径过短而容易产生误导现象。该系统采用在相邻交叉口前连续设置显示多路段交通信息的可变标牌，就好像接力棒一样，通过各个交叉口上的多路段动态交通信息，把车辆诱导到不拥挤的路段上，直至目的地。
哈尔滨工业大学运用GPS和集群通讯系统设计的实验性指挥调度系统，适合于公安，消防，电力等特殊交通集团作分组调度使用。 由清华大学，北京人民广播电台和中科院遥感所共同研制的车辆定位导航系统利用调频广播副载波传送差分GPS信号，供车载GPS接受修正自己的位置，目前只能提供车辆定位信息和静态地理信息vii。 总体来说，我国对路径诱导系统的研究和应用大部分是以无线电广播为基础的初级诱导系统，基于GPS、集群通信、可变标牌的诱导系统正处于研究和试验阶段，而缺少对城市路径诱导系统比较全面的研究。
3 路径诱导系统的构成
车辆路径诱导系统，是应用全球定位系统技术(GPS, Global Positioning System)、电子交通图(Electronic Map of Traffic Network)、计算机技术、多媒体技术和通信技术的综合系统。它是出行者信息系统ATIS (Advanced Traveler Information System)中的一部分。采用该系统使
得车载计算机能够自动显示车辆位置、交通网络图和道路交通状况，还可根据需求向用户提供最优路径引导指令和丰富的实时交通信息，或者通过获得的实时交通信息帮助驾驶员找到一条从出发点到目的地的最优路径，它能帮助驾驶员避开拥挤和事故路段，避免因不熟悉城市交通环境而迷路，另外由于有了适时的路线指引，驾驶员可以将精力集中在驾驶操作上，从而有助于提高交通安全水平，减少交通事故。
车辆路径诱导系统的主要硬件设备是由GPS接收机、辅助导航传感器(陀螺仪、磁罗盘、里程表等)、动态信息接收机、车载PC机、显示装置、人机交互设备等组成的。典型的车辆路径诱导系统如图1所示，由八个主要功能模块构成。
图表 1 CDRGS框架图
4 几种常见的路径诱导算法分析
动态路径诱导就是要为行驶在道路网中的车辆提供从当前位置到目的地之间最方便和快捷的路径,即所谓的“最短路”。这里“最短路”有两种理解：一种是基于已有道路基础上的行驶路程距离最短路，这种“最短路”根据已有的路网结构和图论的知识便可以找到，而且是静态不变的；另一种便是考虑了实时道路交通流状况的行驶时间最短或路阻最小路径，计算这种“最短路”有以下两个前提：一是由前面提到的动态交通分配得到交通流的实时分布情况，另外则是要建立一定的行驶时间函数或路阻函数，将交通流的分布状况或其他因素加入到行驶时间或路阻的计算当中,从而根据计算结果来选择“最短路”并作为诱导路径提供给驾驶员。理论上说，这种最短路是随交通流而动态连续变化的，但实际操作是只能作 离散处理，将系统工作时间划分为若干个时间段，并在一个时间段里计算找出几条动态最短路提供给驾驶员选择。
动态路径诱导系统（Dynamic Route Guidance System，DRGS）的开发是研究智能交通系统的一个重要方面。路径诱导系统根据变化的交通状况为出行者提供到达目的地的最优路线，对车辆进行在线诱导，以防止交通阻塞与拥挤，减少延误,最终使交通流在路网上达到合理的分配，从而提高整个路网的通行能力viii。路径诱导系统中确定起讫点之间最优或次优
路线的算法称为路径诱导算法。传统的路径诱导算法有Dijkstra算法、Floyd算法、启发式搜索算法、K-最短路径算法。 4.1 Dijkstra算法
Dijkstra算法是由荷兰数家E.W.Dijkstra于1959年提出的一种适用于非负权值网络的单源最短路算法ix,是目前求解最短路问题的理论上最完备/应用最广的经典算法，它可以给出从指定节点到图中所有其他节点的最短路径。它是一种基于贪心策略的最短路径算法,它的主要思想是按照路径长度逐点增长的方法构造一棵路径树,从而得到从该树的根节点(即指定节点)到其他所有节点的最短路径。具体做法是：设集合存放已经求出的最短路径的终点，初始状态时，集合中只有一个源点V1。以后每求得一条最短路径(V1,V2,…,Vk)，就将加入到集合S中,直到全部顶点都加入S中为止\4.2 Floyd算法
Floyd算法x是在1962年由Floyd提出的。它可以直接求出图中所有顶点对之间的最短路径和最短路径长度。Floyd算法的时间复杂度为O(n3)。该算法在各种优化问题中得到了较为广泛的应用，并且这种算法的解是全局最优的。但是这种算法需要耗费巨大的存储量(需要建立邻接表或者是邻接矩阵)，计算费用大(与网络节点数成立方关系)，所以只适合解决范围小，节点数少的稠密图。一般来说在城市路网中，节点数比较庞大，因此不适合采用。除此之外，Floyd算法主要针对带权有向图而言，对于无向图，它并没有考虑。 4.3启发式搜索算法
启发式搜索是基于知识的搜索策略，即通过选定一种估价函数，在搜索过程中的每一步，寻找估价函数数值最高的节点作为下一个搜索节点。利用启发式信息的有效方法是计算启发式函数，该函数估价每一生成节点处于最佳路径解上的可能性，从而优先搜索可能性大的节点，达到提高搜索效率的目的。基于启发式搜索的最短路算法主要有A*算法、双向搜索算法、分层地图算法、cost算法、分支界定法等。 4.4 K-最短路径算法
在诱导系统中由于预测存在误差，根据预测的行程时间所计算的最短路径未必真实，而且只推荐唯一路线可能引致误导，还容易导致车流积聚。可见，性能优良的车辆诱导系统应同时计算出次动态最短路径、第三动态最短路径、?、第K动态最短路径等，作为发布路线引导信息的基础。学术上称同时计算若干条最短路径的问题为K最短路径问题。常见的K-最短路径算法是由Dijkstra算法发展起来的二重扫除法xi。这是一种非确定性多项式时间复杂度的算法。但是这种常用的K-最短路算法对大型交通网络难以满足实时性的要求，并且给出的K条路径比较接近，重复路段较多，有时甚至出现环路。而遗传算法、神经网络等软计算方法的计算时间对网络尺寸不敏感，解决大规模网络中K路最短问题具有一定优势xii。苏永云等人xiii研究了路径权值在优化过程中跨时段动态变化的问题，给出了改进的矩阵算法和改进的A*算法来求解K-最短路径问题。
本章讨论了Dijkstra算法、A*算法及其改进算法、双向搜索算法、基于分层地图的搜索算法、k-最短路径算法等。这些算法又有着各自的优缺点，适合不同条件下的路网。除了这些算法以外，新近出现了用遗传算法解决路网中最优路径的方法。但是由于路网中节点数的庞大，用遗传算法不好确定初始种群，因此现阶段用遗传算法解决路网中最优路径问题还处于摸索阶段，由于时间等因素的限制，本文对遗传算法未做深入研究。
5 结语
随着城市化水平的不断加快，交通问题日益突出，智能交通系统成为各国城市解决交通问题的首选方案，路径诱导系统是智能交通系统的一个重要组成部分，是解决城市交通问题的最为有效的手段之一。道路网地理信息系统的数据结构、空间数据与拓扑结构的存储与
动态路径诱导系统涵义及算法简介
