文献综述--刘思佳

《文献综述--刘思佳》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、燕山大学本科毕业设计（论文）文献综述课题名称：智能车辆路径优化技术研究学院（系）：车辆与能源学院年级专业：07车辆程学生姓名：刘思佳指导教师：M完成日期：2011.3.12一、课题国内外现状智能车辆(IntelligentVehicle，IV)是一个集环境感知、规划决策、多等级辅助驾驶等功能于一体的综合系统，致力于提高车辆的安全性与通行效率,是贺能交通系统(IntelligentTransportationSystems,ITS)的重要组成部分，也是国际上车辆工程领域研宄的热点和汽车工业±汽长的新动力。辅助驾驶是IV的核心功能，而路径优化技术正是实现这一功能

2、的关键技术1h31。由于问题特征、网络特征的纷繁复杂、目前国内外己有的路径优化算法表现出多样性的特点

3、41。总体来说，最优路径问题可按问题类型、网络特性和求解技术进行分类。1)按问题类型分类的路径优化技术151孅优路径M题Art路衧格柃考虑蚌叫曜抗KMA段书目节点1)按网络特征与表示方法分类的路径优化技术［61整体袢征NAME5U方法1级颼1囑1有坏11不定1讀托逆怀11卞R解M格网解M樂权fl助検挞接杜1)按照实现技术分类的路径优化技术［7］通优世求析技求1欞®计1扇闻求「硬fl供：时术1鱒方味拿扶术线竹崦赵不场A矩舞賴，代》技农静滷fJW拖扑方过槽刪新技

4、求堆结构联结表帱序桶结构标句说定障城接近法urtbi*t-fuururila*i-fuur肪解址nu^Eaii■<«坩二、研究主要成果目前，在车辆路径优化方面的相关技术成果主要集中在经典最短路算法，包括Dijkstra算法、Bellman-Ford-Moore算法、Floyd算法、泊发式搜索(HeuristicSearch,A*)算法等。1)Dijkstra算法關Dijkstra算法是由E.W.Dijkstra于1959年提出的一个适用于所有弧的权均为非负的最短路算法，也是目前公认的求解最短路问题高效的经典算法之一。它可给出从某指定结点到阁中其它所有结点的最

5、短路。其时间复杂度力o(n2),n力结点个数。2)Bellman-Ford-Moore算法11011J该算法分别由Bellman,Ford和Moore在20世纪50—60年代提出。其吋间复杂度是o(nm),m是边/弧数。目前这样的时间复杂度在所有带有负权弧的最短路算法中是最好的，但其实际运算效果却不及Dijkstra算法。3)Floyd算法［⑸31Floyd算法是一个求阁中所有结点对间最短路的算法，由Floyd于1962年提出。其时间复杂度为o(n3),虽然与对每一结点作一次Dijkstra算法的时间复杂度相同，但其实际运算效果要好于后荠。4）A*算法114

6、10前最流行的启发式搜索算法是由Hart、Nilsson、Raphael等人首先提出的A*算法。该算法的创新之处在于选择下一个被检查的结点时引入了己知的全局信息，对当前结点距终点的距离做出估计，作为评价该结点处于最优路线上的可能性的量度，这样就可以首先搜索可能性较人的结点，从而提高了搜索过程的效率。三、发展趋势0前，智能车辆路径优化技术的研究热点及趋势体现在

7、15

8、:1）应用动态交通信息目前静态的最优路径算法（计算起终点之间的距离最短路）己经成型，但随着城市交通拥挤现象的加剧，仅能指引行驶方向的静态路径计算结果已经无法满足出行者的时效性需求，应用通信技术在导

9、航终端、手机、PDA,直至智能车辆屮引入动态交通信息，进而计算避开拥挤的最优行驶路线，是当前的研究热点。2）并行计算随着电子地图数据量的增加，传统的串行计算机的计算负荷也随着越來越人，最优路径计算必须向并行化方向发展，以满足火量的实吋最短路径查询的需要。四、存在问题最优路径选择是每个出行者都要面对的问题，在网络系统中最优路径选择就其本质而言，就是选取合适的路阻函数，将路网合理地优化，再选择合适的算法计算出满足一定条件的最优路径。当前通用的经典最短路径算法没冇考虑到实际交通出行特点，均把整个路网中的所冇路段都纳入搜索范围，随着电子地图数据量的增加，必然会浪费人

10、量的计算时间（基于广州市路网，利用车载导航装置调用Dijkstra算法进行一次路径计算需要90秒），其结果也通常不能为驾驶员所接受。这就要求我们从另一个角度来考虑问题：即通过优化路网结构、幵发符合出行者出行特性的最优路径算法。五、主要参考文献1杨兆升.智能运输系统概论[M].北京：人民交通出版社，20032赵亦林.车辆定位与导航系统[M].北京：电子工业出版社，19993肖位权.图论及其算法[M].北京：航天工业出版社，19934付梦印等.智能车辆导航技术[M].北京：科学出版社，20095杨兆升.城市交通流诱导系统[M].北京：中国铁道出版社，20046马

11、道松.动态路径诱导系统中行车路线优化和实施技术研宂[