城市道路最优路径算法研究

论文摘要

近几十年来,随着我国经济的发展,交通运输业得到了空前发展,交通运输业的发展一方面促进了物质交流和人员往来,大大缩短了出行的时间,提高了工作的效率；另一方面交通拥堵问题,环境污染问题也随之而来。交通拥堵和交通事故频发越来越严重地困扰着世界各国的大城市,为了提高运输网络使用效率,解决交通拥挤和交通安全问题,有必要进行对城市交通的实时最优路径的研究,以方便出行者。随着科学技术的发展,我们可以将计算机技术,通讯技术,网络技术和嵌入式技术等运用到交通领域,通过各种技术的综合运用,为人们的出行提供足够的信息支持。由于是提供的实时信息,因此整个城市的车辆流动实现了自适应的功能,对于整个城市的交通也实现了最充分的利用,从而能缓解交通拥堵的状况。Dijkstra算法,Floyds算法,A*算法都是贪心算法,是静态的最短路径算法,无法反映当前的实际情况,蚁群算法是对蚂蚁觅食行为的模拟,能有效的对外界情况变化做出反应,因此能更有效的对外界情况的变化作出调整,具有实时性的的特点,对实时最优路径的选择最适用。论文介绍了人们对最优路径选择的研究情况,介绍了交通系统中的数据的表示和存储方式,通过对Dijkstra算法,A*算法进行了研究,对这两个算法有了深入的了解,对他们的优缺点也有了清晰的认识,在此基础上我们引入了新的算法——蚁群算法,对蚁群算法在最优路径选择上的应用进行了理论研究并对其进行了改进,通过试验对Dijkstra算法,A*算法和改进的蚁群算法进行了比较,A*算法明显要比Dijkstra算法效果要好,而改进的蚁群算法在问题规模较大的情况下效果是最好的,而且数据量越大,优势越明显。

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 课题来源
• 1.2 研究意义
• 1.3 研究背景和国内外现状
• 1.4 课题的研究内容与组织结构
• 第二章 道路网几种存储结构的比较
• 2.1 道路网的表示和术语
• 2.2 道路网的几种存储结构的比较
• 2.2.1 几种路网存储结构的介绍
• 2.2.2 性能的比较
• 2.3 路网要表示的信息
• 第三章 最短路径求解中用到的相关技术
• 3.1 美国和欧洲的全球定位技术
• 3.2 地理信息技术
• 3.3 交通流诱导技术
• 3.3.1 交通流诱导系统的结构
• 3.3.2 交通流诱导系统的交通信息采集方式研究
• 第四章 几种常见最短路径算法比较
• 4.1 Dijkstra算法优缺点
• 4.2 Floyd算法优缺点
• 4.3 对Dijkstra进行改进的A*算法
• 第五章 蚂蚁群算法在求解最优路径中的应用
• 5.1 蚁群算法
• 5.1.1 蚁群算法介绍
• 5.1.2 蚁群算法原理
• 5.2 蚁群算法在最优路径选择中的应用
• 5.2.1 蚁群算法解决旅行商问题
• 5.2.2 蚁群算法求最优路径的实现
• 5.3 对蚁群算法的改进
• 5.3.1 蚁群算法的不足
• 5.3.2 对蚁群算法的改进
• 5.4 改进的蚁群算法与其他算法的比较
• 5.4.1 蚁群算法参数的设置
• 5.4.2 改进的蚁群算法与其它算法性能的比较
• 第六章 总结与展望
• 参考文献
• 攻读学位期间的研究成果
• 致谢