文献阅读

随着我国经济的发展，城市交通在促进各种资源交换发挥着越来越重要的作用．据统计中国每年因交通堵塞造成的GDP损失达到5％一8％．采取合理的交通路径的规划，能够对交通堵塞预防起到一定的积极作用．车辆路径问题最早是由Dtzig和J．Ramser于1959年提出的．至此之后，国内外学者对车辆路径问题进行了广泛而深入的研究．特别是蚁群算法的提出，该算法与其他算法相比不仅能够智能搜索全局最优而且具有鲁棒性、正反馈、分布式计算、易于与其他算法融合等优点．蚁群算法求两地之间的最优路径，必须考虑像天气、路质、路况车流、突发事件、司机个人偏好等许多不确定的因素，只有这样才能给出满足实际情况的方案．

作为智能交通系统的重要组成部分，车载导航系统由于其在解决交通运输问题中的作用得到了广泛的关注和不断的发展，如缓解交通拥堵，提高交通效率，降低驾车出行成本等。许多国家相继开展了在此领域的研究工作，并已产生了许多产品。

车辆动态自主导航系统中的核心技术包括：数字地图技术，最优路径规划技术，地图匹配及智能导航技术，无线数据传输技术?等。地理信息系统(Geography Information System，GIS)是管理和研究空间数据的技术系统，可以实现对空间数据按地理坐标或空间位置的各种处理、对数据的有效管理等等。路径规划是车辆导航系统中最基本的功能之一，是帮助驾驶员在旅行前和旅行中寻找行驶路线的过程，是车辆导航的一个基本问题，也是实现导航功能的前提条件，其核心是对最优路径的求解。最优路径是指在道路网络中满足某些优化条件的一条路，如距离最短、运输费用最低、行驶时间最短等，通过路径规划找出最优路径，具有巨大的经济效益。

随着计算机处理速度以及无线通讯技术的快速发展，车辆导航系统历经了从静态导航到动态导航的转变过程，这两者的最大区别是静态导航系统进行最优路径规划及导航所用的是静态的交通历史数据或者是纯粹的地理信息数据，而动态导航系统会利用实时更新的动态交通信息对车辆进行路径规划和导航，从而使得导航的结果更加准确合理口。

动态导航系统的实施方式可以有：中心广播式，交通信息中心只负责向一定区域范围内以广播的方式发布公共的实时交通信息，车载单元自行接收这些信息并且进行路径规划，中心对车辆没有任何控制；中心控制式，交通信息中心按照车载单元的导航服务请求进行路径规划，并且将结果返还给车载单元。静态导航系统没有对实时交通信息的利用，其具体内容除了没有利用实时交通信息外和动态导航系统大体类似。

近几年来，随着国民经济的发展，城市中机动车辆渐渐增多，交通需求在不断增加，公路交通流量也越来越大，由此导致了交通拥堵的频繁发生，城市交通正面临着越来越大的压力。在这种形势下，基于静态地图的自主导航虽然可为驾驶员规划一条“最短”路径，但却无法避开前方道路可能发生的交通拥挤。而动态导航则不同，系统获知出发点与目的地之问的交通状况，经过规划得到一条满足用户需求的合理路径。这种导航方式不仅可以有效的避开拥堵，节省出行成本，而且对整个路网有着良性影响。

车辆导航系统中的最短路径搜索问题可以归结为图论中的最短路径问题,解决该问题的经典算法是Dijkstra算法,该算法采用贪心策略,即每一步都选择与源节点构成局部路径距离最短的节点作为当前扩展节点来形成当前局部最短路径,进而得到全局的最短路径。是一种静态的局部最优算法。该算法简单、易于实现,然而把该算法应用在求车辆导航系统中的最短路径搜索问题却存在如下的局限性:首先,因为需要反复遍历所有节点,在网络节点和路径较多的情况下,搜索效率就会大大降低,有时甚至找不到最短路径,再者,对于路径权值随时间动态变化的动态网络,如反映路径堵塞和畅通信息的实时交通系统网络就不适用.

蚁群算法是由意大利学者Dorigo M等人于1991年从自然界蚂蚁群体觅食行为得到启发,提出的一种模拟蚂蚁行为的模拟进化算法人工蚁群算法,简称蚁群算法。这种算法具有分布计算、信息正反馈和启发式搜索的特征,算法具有模拟生物界群体觅食的能力,并且能够在实际的路径搜索过程中对外界的影响做出动态的响应,因而在交通最优路径选择中具有极大的可能性和适应性。

然而使用传统蚁群算法求最短路径问题却存在搜索速度慢,易于陷入局部最优解等缺陷,为此本文针对交通网络最短路径问题的特点,在传统蚁群算法中引入搜索方向机制和搜索热区机制提高算法搜索性能。

对于基于抽象的网络图的最短路径问题(shortestPath Problem，简称sPP)的求解方法，由于其在通信、交通、计算机网络、运筹、管理等多门学科中的多种应用需求，多年以来得到了充分的关注并取得了大量研究成果。在这诸多的研究中，大都是基于网络图路径权值为常量的静态算法。网络路径权值随时间发生变化的动态最短路径查找算法随着计算机处理速度不断提高以及应用需求的不断增加，近年来得到了更加广泛的关注。

在网络图中两特定结点之间的最短路径：此问题也即源点-汇点最短路径问题，最经典韵算法就是Dijkstra所提出的算法，此算法依照路径的长度依次产生从起始结点到网络图中所有结点的最短路径。自Dijkstra算法提出以后，又历经了多人在具体实施方法上的改进，使其求解速度大幅提高。解决此问题其他常用的算法包括Bellman，Ford，Moore等人分别提出的动态规划(Dynamic Programming)算法，也称为Bellman—ford算法，该算法解决网络中单源点最短路径问题；Pape，Pallottino等人各自提出的增长图(Graph．Growth)算法；Glover等人提出的结合以上各算法思想的域阀(Threshold)算法。Hart．eta1提出了A*启发式搜索算法。

对网络图中所有结点对之间的最短路径问题：解决较好的两个方法是Floyd提出的一个算法一一Floyd算法，以及另一个被Dantzig提出的算法。两者的计算复杂度相同，都是可以优先选择的算法。

Dijkstra算法只能解决无负边权重的最短路径问题，在欧几米得网络(例如交通路网)中，通过对Dijkstra算法使用下限函数的方法称为欧几米得试探法，欧几米得试探法解决欧几米得图中的源点-汇点最短路径问题。欧几米得试探法是A*算法的一个特例，Dijkstra算法是一种下限为O的A*。

在网络图中计算源点到汇点间依照路径长度产生的前k条最短路径：对此问题最早的解决算法是Hofhnan，Pavley提出的，Dreyfus对此算法作了进一步的改进，另一个应用广泛的经典的解决此问题的算法是Shier提出的。最近，Eppstein提出的采用k个最短路径的隐式表达计算的最短路径算法性能有了比较显著的提高。从Dijkstra算法到Hoffman，Pavley提出的算法都为基于顺序的算法。但Chandy and Misra算法是一种计算k个最短路径问题的并行算法，其时间复杂度比顺序算法要小。

在网络图中计算起点和终点之间历经几个中间结点的最短路径：此类问题的经典解决算法包括Dreyfus提出的算法以及Beardwood，Bajaj，Ibaraki等人提出的算法。

这些经典的最短路径求解算法的研究成果解决了大量的相关基础理论问题。近些年来，许多的工作集中在对算法在计算机上的具体实施方案的改进上，以期有更好的运行效率。还有就是对算法在特定的领域的应用研究上，针对特定领域出现的新问题，将某些经典算法加以适应性的改进从而得到理想的结果。如在交通网络的应用研究，就要考虑道路交通网络中的交通限制信息以及交通状况动态变化特性。

       蚁群算法是模拟蚁群行为的一种随机搜索优化算法，主要由四个部分组成[5]：选择策略；信息量的局部更新；求局部最优解的局部搜索算法；信息量的全局更新。

用基本的蚁群算法求解最短路径问题的主要实现步骤如下:

（1）信息初始化：算法开始运行时，赋予每条边上相等数量的信息量。

（2）选择策略：位于第i 个节点的蚂蚁I，按以下选择策略选择边（i，j ）：

       (1)

其中， ={和i 相连的节点}-{蚂蚁k 已访问过的节点}，即每个蚂蚁对每个节点最多只允许访问一次，对不连通的点，则赋给一个足够大的惩罚值；argmaxt（i，s）表示在与i 相关联的边的集合中，具有最大信息量的边的另一节点；为给定参数，0< <1，q 是（0，1）内服从均匀分布的随机变量；h 依照以下概率在=-argmaxt（ i，s）内随机取值：

                   (2)

（i，s）表示边（i，s）上的信息量，式（2）采用轮盘赌的方式实现。若=0.9，式（1）表明和i 相关联的信息量最大的边以高概率0.9 被蚂蚁选中，其余的边以0.1 的概率按式（2）参与选择。

（3）局部更新信息量：当蚂蚁选中边（i，j）后，就更新边（i，j）上的信息量：

每当蚂蚁选中一条边后，就按（3）式更新减少边上的信息量，从而增加蚂蚁选择其它边的概率。

（4）局部搜索：当m 只蚂蚁从S 到T 搜索完后，则求得m个解。为了尽可能遍历所有解,分别在这些解的邻域中，采用局部搜索算法（例如2-OPT），求出局部最优解。

（5）全局更新信息量：当所有的m 只蚂蚁都得到局部最优解后，全局更新边上的信息量：

是给定参数，0<<1，表示随着时间的推移，以前留下的信息逐渐消逝，用参数1- 表示信息消逝程度；是边（i，j）上的信息增量；是蚂蚁k求得的局部最优解；wconst 是常量。

（6）求全局最优解：到当前迭代次数为止，所建立的所有局部最优解中，值最小的解作为当前迭代次数的全局最优解。

从一系列的实验结果发现，用基本蚁群算法求解最短路径过程中常出现两个问题：搜索陷入局部最优解，即搜索进行到一定程度后，所有的个体发现的解基本完全一致，出现停滞现象，不能再对解空间进一步搜索，导致可能无法找到全局最优解；收敛到全局最优解的时间长，求解结果反复在局部最优解和全局最优解之间振荡。

为了解决出现的问题，文章从蚁群算法的选择策略、局部搜索算法以及信息量的全局修改三方面进行改进。

（1）分析式（1）知，若参数值较大（如接近1），则多数蚂蚁易选择信息量最大的边，这样在搜索过程中可能容易出现多数蚂蚁搜索到相同的路径，使得搜索到的解空间较小，不利于发现全局最优解，算法容易收敛到局部最优解。若较小（如接近0），则信息量最大的边被选择的概率小，其它边被选择的概率大，能扩大搜索到的解空间，但搜索呈现一定的盲目性，不容易收敛。综合考虑这两个方面，采用变参数，即的值和迭代次数cycle 有关，是迭代次数的分段函数：

              (5)

式中，分别为迭代次数；是最大迭代次数；0.8< <1，0< <0.4。式（5）表明，算法开始运行时，以较大的概率选择信息量最大的边，直到迭代到第次。此后，为了防止搜索陷入局部最优解，便于发现全局最优解，以较大的概率在局部最优解的邻域中搜索其它解，直到迭代到第次。为了使算法收敛到全局最优解，次后再以较大的概率选择信息量最大的边，直到运行结束。

（2）选择合适的局部搜索算法，能扩大搜索空间，有利于发现全局最优解。受遗传算法的启发[7]，将变异思想引入到局部搜索算法，给出一个具有变异特征的局部搜索算法。设蚂蚁I 搜索到从S 到T 的路径为： 。分别为图中的节点。给定变异概率，在n 次循环中，产生n 个（0，1）内均匀分布的随机数。若第个随机数 <，则第个节点要发生变异。设存在节点，和相连外，有w 个节点，，…，，和相连。进行w 次循环，产生w 个（0，1）内匀分布的随机数，若第个随机数（ 为给定的选择概率），则用代替，得到一个解。若路径的值，则用作为蚂蚁k 搜索到的局部最优解。如果该算法和常用的2-OPT 局部搜索算法相结合，则更能加大对解空间的探测力度。

（3）为了使算法较快地收敛到全局最优解，采用下式对信息量全局更新：

          （6）

是全局最优解，即最短路径的距离值。式（6）表明，经过次迭代后，只修改全局最优解边上的信息量，使最短路径边上的信息量增加较快，算法容易收敛到全局最优解。

蚁群算法是一种模拟进化算法，是受到对真实蚁群行为的研究的启发而提出的。为了说明蚁群系统的原理，先简介一下蚂蚁搜索食物的具体过程。象蚂蚁这类群居昆虫，虽然单个昆虫的行为极其简单，但群体却表现出复杂的行为，能找到由蚁巢到食物源的最短路径。仿生学家经过研究发现，蚂蚁个体之间是通过一种称为外激素（pheromone）的物质进行信息传递的。蚂蚁在运动过程中，能够在它所经过的路径上留下该种物质，而且在运动过程中能够感知这种物质，并以此指导自己的运动方向，蚂蚁倾向于朝着物质强度高的方向移动。因此，由大量蚂蚁组成的群体行为便表现出一种信息正反馈现象：某一路径越短，走过的蚂蚁越多，路径上留下的信息物质越多，则后续蚂蚁选择该路径的概率就越大，并且留下相应的信息物质。最后，蚂蚁个体之间就是通过这种信息物质交流，搜索到一条从蚁巢到食物源的最短路径。

最短路径问题是智能交通中交通网络分析中的一个重要问题，也是一个研究热点。它是资源分配、路线设计及分析等优化问题的基础，具有重要理论意义和实际应用价值。有许多研究者曾对最短路径算法进行了大量的研究，并取得了很大的进展，提出了很多解决这类问题的方法。其中传统的算法有，Dijkstra算法、A·算法及其改进算法等等；还有近几十年来，通过模拟或揭示某些自然现象而产生了一些新颖的启发式智能算法，如遗传算法，模拟退火算法，禁忌搜索算法、蚁群算法等。

城市道路网有道路路线．交叉路口等物理属性，同时也具有路线长度、通行时间、路况等各种其它逻辑属性。用节点来表示城市道路网中的交叉路口，连接两节点之间的边表示路路线，并将路线的长度、通行时间，路况等属性表示为该边的权值，那么就可以把道路网络抽象为一个带权有向图。给定一个带权有向图G为二元组G=(V，{E})，其中V是包含n个节点的集合，E是包含h条边(弧段)的集合，<i，j>是E中从节点i至j的边，w{{是边<i，j>的非负权值。设s，T分别为V中的起始节点和目标节点，则最优路径问题就是指在带权有向图G中，寻找从指定起始节点到目标节点的一条具有最小权值总和的路径。

智能交通系统（Intelligent Transportation System,ITS）就是充分利用现代通信、定位、传感器及其他与信息有关的技术来减少交通拥挤，提高道路通过量，改进交通安全状况，快速实现交通信息的采集和传递，在人、车、路之间构造最优时空模型，从而达到合理地分配交通资源，改善地面交通条件的目的。

ITS的发展离不开地理信息系统GIS（Geographic Information System）的支持.GIS是以地理空间数据库为基础,在计算机软件的支持下,对空间相关数据进行采集、管理、操作、分析、模拟和显示，适时地提供动态信息，因此GIS是支持ITS发展的一种关键技术。在GIS中，数字地图不仅要以X、Y二维坐标的形式表示出来，而且图形要素之间具有拓扑关系，这是ITS中实现地图匹配、路径查询、路径引导等功能模块的基础。

作为智能交通系统的重要组成部分，车载导航系统由于其在解决交通运输问题中的作用得到了广泛的关注和不断的发展，如缓解交通拥堵，提高交通效率，降低驾车出行成本等。许多国家相继开展了在此领域的研究工作，并已产生了许多产品。

车辆动态自主导航系统中的核心技术包括：数字地图技术，最优路径规划技术，地图匹配及智能导航技术，无线数据传输技术?等。地理信息系统(Geography Information System，GIS)是管理和研究空间数据的技术系统，可以实现对空间数据按地理坐标或空间位置的各种处理、对数据的有效管理等等。

路径规划是车辆导航系统中最基本的功能之一，是帮助驾驶员在旅行前和旅行中寻找行驶路线的过程，是车辆导航的一个基本问题，也是实现导航功能的前提条件，其核心是对最优路径的求解。最优路径是指在道路网络中满足某些优化条件的一条路，如距离最短、运输费用最低、行驶时间最短等，通过路径规划找出最优路径，具有巨大的经济效益。

随着计算机处理速度以及无线通讯技术的快速发展，车辆导航系统历经了从静态导航到动态导航的转变过程，这两者的最大区别是静态导航系统进行最优路径规划及导航所用的是静态的交通历史数据或者是纯粹的地理信息数据，而动态导航系统会利用实时更新的动态交通信息对车辆进行路径规划和导航，从而使得导航的结果更加准确合理口。

动态导航系统的实施方式可以有：中心广播式，交通信息中心只负责向一定区域范围内以广播的方式发布公共的实时交通信息，车载单元自行接收这些信息并且进行路径规划，中心对车辆没有任何控制；中心控制式，交通信息中心按照车载单元的导航服务请求进行路径规划，并且将结果返还给车载单元。静态导航系统没有对实时交通信息的利用，其具体内容除了没有利用实时交通信息外和动态导航系统大体类似。

搜索热区是指由源节点和目标节点为对角节点所组成的矩形区域,在实际求最短路径问题时,求得的最优轨迹节点的位置,其落在由源节点和目标节点为对角节点所形成的搜索热区的概率往往要大大高于落在非搜索热区内的概率。因此在蚁群算法中引入搜索热区的概念后不但使得搜索的速度大大提高,而且不易搜索陷入局部最优解。

参考文献

1.       赵亦林 编著 《车辆定位与导航系统》        北京：电子工业出版社1999．1

2.       陈述彭等．地理信息系统导论[M]．北京：科学出版社，1999．5

3.       颜波．车载动态自主导航系统中的动态最优路径规划[D]．[硕士学位论文]．北京：清华大学汽车工程系，2004

4.       司功闪．地理信息系统中路径分析系统的设计与实现[D]．[硕士学位论文]．湖南：国防科学技术大学研究生院，2003

5.       卢照敢，杨天行．地理信息系统中空间关系自动构建技术研究[J]．长春工程学院学报(自然科学版)，V01．3，2002．4

6.       吴信才．地理信息系统原理与方法[M]．北京：电子工业出版社，2002．3

7.       邹伦等．地理信息系统基础一原理、方法和应用[M]．北京：科学出版社，2001．2

8.       朱文兴等．城市交通网络中的路径优化研究[J]．山东大学学报(工学版)．2005．35(1)：74—77

9.       陆锋，卢冬梅，崔伟宏．交通网络限制搜索区域时间最短路径算法[J]．中国图像图形学报，1999，4(10)：849—853

10.   陆锋．最短路径算法：分类体系与研究进展[J]．测绘学报，2001，30(3)：269—275．

11.   王开义，赵春江，胥桂仙等．GIs领域最短路径搜索问题的一种高效实现[J]．中国图像图形学报，2003，8(8)：95l一956．

12.   陈壁峰，陆吴娟，黄樟灿．车辆自导航系统的动态最优路径搜索模型及算法[J]．武汉理工大学学报(信息与管理工程版)，2002，24(3)：46—48．

13.   段莉琼，朱建军，王庆社，马玲．改进的最短路径搜索A$算法的高效实现[J]．海洋测绘，2004，24(5)：20一22．

14.   许志海，张绍云．交通限制条件下的最短路径算法分析与优化[J]．信息过程大学测绘学院学报，2005，22(1)：62—64．

15.   工秋红，赵忠杰．汽车驾驶智能化中路线规划及导航的最佳路径求解法[J]．西安公路交通大学学报，1999，19(3)：88—90

16.   彭飞，柳重堪，张其善．车辆定位与导航系统中的快速路径规划算法[J]．北京航空航天大学学报，2002，28(1)：70一73

17.   爱信艾达株式会社．路线搜索装置以及路线搜索方法[D]．中国：cN1657877A，2005，8，24

18.   交通预测．com公司．一种提供旅行时间预测的方法[D]．中国：cN1434946A，2003，8，6

19.   张小国，王庆，万德钧．基于电子地图的路径最优算法研究[J]．中国惯性技术学报，2001，9(1)：44～49

20.   陈曦，傅明．基于多Agent的动态路径规划方法研究[J]．计算机工程，2002，21：228—229，235

21.   丁胜昔，张其善．城市复杂道路网的路线规划算法[J]．遥测遥控，2004，25(1)：36—39

22.   韩刚，蒋捷，陈军，曹元大．车载导航系统中顾及道路转向限制的Dijkstra算法[J]．测绘学报，2002，31(4)：366—368

23.   宋延，石建军，许国华．适用于路径规划系统的动态路网描述模型[J]．交通与计算机，2004，22(5)：28—3l

24.   55]石小法等．交通信息影响下的动态路径选择模型研究[J]．公路交通科技，2000，17(4)：35—37

25.   54]刘彦良，王洪涛．复杂网络的优化模型及最短路径求解[J]．天津理工大学学报，2006，22(1)：33—35

26.   Dijkstra．E．A note on two problems with graphs[J]．Nume rical Mathematics1959．Vl：267～271

27.   R．K．Ahuja，K．Mehlhorn，J．B．Orlin，et a1．Faster Algorithms for the shortestpath problem[J]．J．ACM．1990，V37：2 13～223

28.   R．K．Ahuja，K．Mehlhorn，J．B．Orlin，et a1．Faster Algorithms for the shortestpath problem[J]．J．ACM．1990，V37：2 13～223

29.   Cherkassky，B．V．，G01dberg，A．v．，Radzik，T．shortest Paths Algorithms：Theory and Experimental EValuation[J]． Computer science Department，

30.   Stanford University’rechnical Report．1993，V93·1480

31.   R．E．Be儿man．On a routing problem[J]．Quart．Appl．Math．1958，V16：87～90

32.   L．R．Ford．Network Flow Theory[J]．The Rand corporation：1956．p923

33.   U.Pape.Implementation and emciency of Moore algorithms for the shortest route problem[J]．Math Prog．1974，V7：212～222

34.   T. Williams, R.J. Murphy, F. Walther 《A Free-Space Optical Terminal for Fading Channels》     Free-Space Laser Communications 2009.07

35.   Frederick G. Walther, John D. Moores  《A Process for Free-Space Laser Communications System Design》  Free-Space Laser Communications  2009.03

36.   Shlomi Arnon  《An underwater optical wireless communication network》   Free-Space Laser Communications   2009.09

37.   K. Kagawa and J. Tanida  《Free-space optical data transmission using wavelength-division multiplexing with a dedicated CMOS image sensor for indoor optical wireless LAN》     Free-Space Laser Communications  2009.04

38.   Kaiyun Cui, Gang Chen, Qunfeng He, Zhengyuan Xu  《Indoor optical wireless communication by ultraviolet and visible light》   Free-Space Laser Communications 2009.09

39.   Robert J. Murphy, Alicia M. 《A Conical Scan Free Space Optical Tracking System for Fading Channels》  Free-Space Laser Communications 2009.01 

40.   Fillard J P,M’timet H，Lussert J M,et,al.Computer simulation of super resolution point source image detection.Opt Eng,1993

41.   cherkas sky，B．V．，Goldberg， A．V．，Radzik，T．shortest Paths Algorithms Theory and Experimental Evaluation．Computer Science Department Stanford UniversityTechni cal Report．1993，V93一1480

42.   Multithreading Implementation of a Distributed Shortest Path Algorithm on EARTH Multiprocessor[A]．Thulasiraman P，Tiao x M，Gao G R．Proceedings of the 1 996 International Confcrence on Hi曲Performance Computing[C]，1 996:336—340

43.   Eppstein D．Finding the k Shortest Paths[J]．SIAM Journal on Computing，1999，28(2)：652—673

44.   Elise D，M．Hooks，Hani S，et a1．Least expected time paths in stochastic ,time—varying transportation networks[J]．Transportation Science．2000，V34:198～215

45.   Fuliping．An adaptiVe routing algorithm fbr in-Vehicel route guidance systems with real—time information[J]．Transportation Research B，2001，V35：749～765

46.   Fuliping，L．R．Rilett．Expected shortest paths in dynamic and stochastic trafnc networks[J]．Transportation Research B，1998，V32：499～516

47.   R．Hall，The fastest path through a network with random time—dependent travel times[J]．Transportation Science．1986，V20：182～1 88

48.   D.Shier．An algorithms for Finding the k shortest paths in a network[J]．Networks．1979．V9：195～214．

49.   W．HoffInan，R．Pavley．A Method for the Solution of the Nth Best Path Problem[J]．J.Acm．1959，V6：506～514

50.   Stuart E．Dreyfhs．An appraisal of some shortest—path algorithms[J]．Operations Research，1969，V17：395～412