《开题报告文献阅读.doc》由会员分享，可在线阅读，更多相关《开题报告文献阅读.doc（10页珍藏版）》请在金锄头文库上搜索。
1、文献阅读随着我国经济的发展，城市交通在促进各种资源交换发挥着越来越重要的作用据统计中国每年因交通堵塞造成的GDP损失达到5一8采取合理的交通路径的规划，能够对交通堵塞预防起到一定的积极作用车辆路径问题最早是由Dtzig和JRamser于1959年提出的至此之后，国内外学者对车辆路径问题进行了广泛而深入的研究特别是蚁群算法的提出，该算法与其他算法相比不仅能够智能搜索全局最优而且具有鲁棒性、正反馈、分布式计算、易于与其他算法融合等优点蚁群算法求两地之间的最优路径，必须考虑像天气、路质、路况车流、突发事件、司机个人偏好等许多不确定的因素，只有这样才能给出满足实际情况的方案作为智能交通系统的重要组成部
2、分，车载导航系统由于其在解决交通运输问题中的作用得到了广泛的关注和不断的发展，如缓解交通拥堵，提高交通效率，降低驾车出行成本等。许多国家相继开展了在此领域的研究工作，并已产生了许多产品。车辆动态自主导航系统中的核心技术包括：数字地图技术，最优路径规划技术，地图匹配及智能导航技术，无线数据传输技术等。地理信息系统(Geography Information System，GIS)是管理和研究空间数据的技术系统，可以实现对空间数据按地理坐标或空间位置的各种处理、对数据的有效管理等等。路径规划是车辆导航系统中最基本的功能之一，是帮助驾驶员在旅行前和旅行中寻找行驶路线的过程，是车辆导航的一个基本问题，
3、也是实现导航功能的前提条件，其核心是对最优路径的求解。最优路径是指在道路网络中满足某些优化条件的一条路，如距离最短、运输费用最低、行驶时间最短等，通过路径规划找出最优路径，具有巨大的经济效益。随着计算机处理速度以及无线通讯技术的快速发展，车辆导航系统历经了从静态导航到动态导航的转变过程，这两者的最大区别是静态导航系统进行最优路径规划及导航所用的是静态的交通历史数据或者是纯粹的地理信息数据，而动态导航系统会利用实时更新的动态交通信息对车辆进行路径规划和导航，从而使得导航的结果更加准确合理口。动态导航系统的实施方式可以有：中心广播式，交通信息中心只负责向一定区域范围内以广播的方式发布公共的实时交通
4、信息，车载单元自行接收这些信息并且进行路径规划，中心对车辆没有任何控制；中心控制式，交通信息中心按照车载单元的导航服务请求进行路径规划，并且将结果返还给车载单元。静态导航系统没有对实时交通信息的利用，其具体内容除了没有利用实时交通信息外和动态导航系统大体类似。近几年来，随着国民经济的发展，城市中机动车辆渐渐增多，交通需求在不断增加，公路交通流量也越来越大，由此导致了交通拥堵的频繁发生，城市交通正面临着越来越大的压力。在这种形势下，基于静态地图的自主导航虽然可为驾驶员规划一条“最短”路径，但却无法避开前方道路可能发生的交通拥挤。而动态导航则不同，系统获知出发点与目的地之问的交通状况，经过规划得到
5、一条满足用户需求的合理路径。这种导航方式不仅可以有效的避开拥堵，节省出行成本，而且对整个路网有着良性影响。车辆导航系统中的最短路径搜索问题可以归结为图论中的最短路径问题,解决该问题的经典算法是Dijkstra算法,该算法采用贪心策略,即每一步都选择与源节点构成局部路径距离最短的节点作为当前扩展节点来形成当前局部最短路径,进而得到全局的最短路径。是一种静态的局部最优算法。该算法简单、易于实现,然而把该算法应用在求车辆导航系统中的最短路径搜索问题却存在如下的局限性:首先,因为需要反复遍历所有节点,在网络节点和路径较多的情况下,搜索效率就会大大降低,有时甚至找不到最短路径,再者,对于路径权值随时间动
6、态变化的动态网络,如反映路径堵塞和畅通信息的实时交通系统网络就不适用.蚁群算法是由意大利学者Dorigo M等人于1991年从自然界蚂蚁群体觅食行为得到启发,提出的一种模拟蚂蚁行为的模拟进化算法人工蚁群算法,简称蚁群算法。这种算法具有分布计算、信息正反馈和启发式搜索的特征,算法具有模拟生物界群体觅食的能力,并且能够在实际的路径搜索过程中对外界的影响做出动态的响应,因而在交通最优路径选择中具有极大的可能性和适应性。然而使用传统蚁群算法求最短路径问题却存在搜索速度慢,易于陷入局部最优解等缺陷,为此本文针对交通网络最短路径问题的特点,在传统蚁群算法中引入搜索方向机制和搜索热区机制提高算法搜索性能。对
7、于基于抽象的网络图的最短路径问题(shortestPath Problem，简称sPP)的求解方法，由于其在通信、交通、计算机网络、运筹、管理等多门学科中的多种应用需求，多年以来得到了充分的关注并取得了大量研究成果。在这诸多的研究中，大都是基于网络图路径权值为常量的静态算法。网络路径权值随时间发生变化的动态最短路径查找算法随着计算机处理速度不断提高以及应用需求的不断增加，近年来得到了更加广泛的关注。在网络图中两特定结点之间的最短路径：此问题也即源点-汇点最短路径问题，最经典韵算法就是Dijkstra所提出的算法，此算法依照路径的长度依次产生从起始结点到网络图中所有结点的最短路径。自Dijkst
8、ra算法提出以后，又历经了多人在具体实施方法上的改进，使其求解速度大幅提高。解决此问题其他常用的算法包括Bellman，Ford，Moore等人分别提出的动态规划(Dynamic Programming)算法，也称为Bellmanford算法，该算法解决网络中单源点最短路径问题；Pape，Pallottino等人各自提出的增长图(GraphGrowth)算法；Glover等人提出的结合以上各算法思想的域阀(Threshold)算法。Harteta1提出了A*启发式搜索算法。对网络图中所有结点对之间的最短路径问题：解决较好的两个方法是Floyd提出的一个算法一一Floyd算法，以及另一个被Dan
9、tzig提出的算法。两者的计算复杂度相同，都是可以优先选择的算法。Dijkstra算法只能解决无负边权重的最短路径问题，在欧几米得网络(例如交通路网)中，通过对Dijkstra算法使用下限函数的方法称为欧几米得试探法，欧几米得试探法解决欧几米得图中的源点-汇点最短路径问题。欧几米得试探法是A*算法的一个特例，Dijkstra算法是一种下限为O的A*。在网络图中计算源点到汇点间依照路径长度产生的前k条最短路径：对此问题最早的解决算法是Hofhnan，Pavley提出的，Dreyfus对此算法作了进一步的改进，另一个应用广泛的经典的解决此问题的算法是Shier提出的。最近，Eppstein提出的采
10、用k个最短路径的隐式表达计算的最短路径算法性能有了比较显著的提高。从Dijkstra算法到Hoffman，Pavley提出的算法都为基于顺序的算法。但Chandy and Misra算法是一种计算k个最短路径问题的并行算法，其时间复杂度比顺序算法要小。在网络图中计算起点和终点之间历经几个中间结点的最短路径：此类问题的经典解决算法包括Dreyfus提出的算法以及Beardwood，Bajaj，Ibaraki等人提出的算法。这些经典的最短路径求解算法的研究成果解决了大量的相关基础理论问题。近些年来，许多的工作集中在对算法在计算机上的具体实施方案的改进上，以期有更好的运行效率。还有就是对算法在特定的
11、领域的应用研究上，针对特定领域出现的新问题，将某些经典算法加以适应性的改进从而得到理想的结果。如在交通网络的应用研究，就要考虑道路交通网络中的交通限制信息以及交通状况动态变化特性。蚁群算法是模拟蚁群行为的一种随机搜索优化算法，主要由四个部分组成5：选择策略；信息量的局部更新；求局部最优解的局部搜索算法；信息量的全局更新。用基本的蚁群算法求解最短路径问题的主要实现步骤如下:（1）信息初始化：算法开始运行时，赋予每条边上相等数量的信息量。（2）选择策略：位于第i 个节点的蚂蚁I，按以下选择策略选择边（i，j ）： (1)其中， =和i 相连的节点-蚂蚁k 已访问过的节点，即每个蚂蚁对每个节点最多只
12、允许访问一次，对不连通的点，则赋给一个足够大的惩罚值；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）式更新减少边上的信息量，从而
13、增加蚂蚁选择其它边的概率。（4）局部搜索：当m 只蚂蚁从S 到T 搜索完后，则求得m个解。为了尽可能遍历所有解,分别在这些解的邻域中，采用局部搜索算法（例如2-OPT），求出局部最优解。（5）全局更新信息量：当所有的m 只蚂蚁都得到局部最优解后，全局更新边上的信息量：是给定参数，01，表示随着时间的推移，以前留下的信息逐渐消逝，用参数1- 表示信息消逝程度；是边（i，j）上的信息增量；是蚂蚁k求得的局部最优解；wconst 是常量。（6）求全局最优解：到当前迭代次数为止，所建立的所有局部最优解中，值最小的解作为当前迭代次数的全局最优解。从一系列的实验结果发现，用基本蚁群算法求解最短路径过程中常
14、出现两个问题：搜索陷入局部最优解，即搜索进行到一定程度后，所有的个体发现的解基本完全一致，出现停滞现象，不能再对解空间进一步搜索，导致可能无法找到全局最优解；收敛到全局最优解的时间长，求解结果反复在局部最优解和全局最优解之间振荡。为了解决出现的问题，文章从蚁群算法的选择策略、局部搜索算法以及信息量的全局修改三方面进行改进。（1）分析式（1）知，若参数值较大（如接近1），则多数蚂蚁易选择信息量最大的边，这样在搜索过程中可能容易出现多数蚂蚁搜索到相同的路径，使得搜索到的解空间较小，不利于发现全局最优解，算法容易收敛到局部最优解。若较小（如接近0），则信息量最大的边被选择的概率小，其它边被选择的概率
15、大，能扩大搜索到的解空间，但搜索呈现一定的盲目性，不容易收敛。综合考虑这两个方面，采用变参数，即的值和迭代次数cycle 有关，是迭代次数的分段函数： (5)式中，分别为迭代次数；是最大迭代次数；0.8 1，0 0.4。式（5）表明，算法开始运行时，以较大的概率选择信息量最大的边，直到迭代到第次。此后，为了防止搜索陷入局部最优解，便于发现全局最优解，以较大的概率在局部最优解的邻域中搜索其它解，直到迭代到第次。为了使算法收敛到全局最优解，次后再以较大的概率选择信息量最大的边，直到运行结束。（2）选择合适的局部搜索算法，能扩大搜索空间，有利于发现全局最优解。受遗传算法的启发7，将变异思想引入到局部
16、搜索算法，给出一个具有变异特征的局部搜索算法。设蚂蚁I 搜索到从S 到T 的路径为： 。分别为图中的节点。给定变异概率，在n 次循环中，产生n 个（0，1）内均匀分布的随机数。若第个随机数 ，则第个节点要发生变异。设存在节点，和相连外，有w 个节点，和相连。进行w 次循环，产生w 个（0，1）内匀分布的随机数，若第个随机数（ 为给定的选择概率），则用代替，得到一个解。若路径的值，则用作为蚂蚁k 搜索到的局部最优解。如果该算法和常用的2-OPT 局部搜索算法相结合，则更能加大对解空间的探测力度。（3）为了使算法较快地收敛到全局最优解，采用下式对信息量全局更新： （6）是全局最优解，即最短路径的距离值。式（6）表明，经过次迭代后，只修改全局最优解边上的
