基于遗传算法的动态交通路径诱导研究

摘要

随着科学技术的进步,路径诱导系统这一概念的出现为交通出行问题带来了解决新思路。将路径诱导系统应用在城市交通中,便是城市交通诱导系统,其作为智能运输系统的核心内容,也是解决现存交通问题最行之有效的方法。路径诱导的原型是图论中的最短路径问题。目前常用的处理方法有：经典的Dijkstra算法和各类仿生算法。Dijkstra算法只能显示单目标即距离的最短路径的路径问题,而仿生算法中的蚁群算法和粒子群算法都难以给出多个最优解,故这些算法不适合实现动态交通诱导的K条最优路径。K条最优路径遗传算法在算法运行时间和最优结果上皆有优势,所以本文选择在K条最优路径遗传算法上加入动态交通目标值来实现交通的动态路径诱导。系统算法是在利用K条最优路径遗传算法实现多目标优化问题的基础上利用隶属度函数和计时器来模拟交通实时路况产生拥堵数据这一目标值,利用多目标优化的思想将其转化为除路径长度外的第二个目标值,利用其改变路径评判函数来动态调整路径诱导,可满足用户根据出行需要,使用户可在显示的人机交互界面上选择实时路径。本文利用数值试验验证动态交通诱导的k条最优路径遗传算法的合理性,并在构建好的地图上显示出系统运行结果。算法结构简明,收敛速度快。本算法特别适合于在大规模交通网络中求解任意两点间的实时多条最优路径。

目录

摘要

Abstract

1 绪论

1.1 交通诱导系统的背景

1.2 动态交通诱导系统的研究现状

1.3 课题研究的主要意义

1.4 课题研究的主要内容

1.5 本章小结

2 动态交通诱导的设计

2.1 框架构成

2.2 设计组成

2.3 动态交通诱导的底层基础

2.3.1 图形基础

2.3.2 属性数据库

2.3.3 图形基础与数据库管理系统的连接

2.4 本章小结

3 求解路径问题算法概述与比较

3.1 Dijkstra算法

3.1.1 Dijkstra算法基本原理

3.1.2 Dijkstra求最短路径的步骤

3.2 蚁群算法

3.2.1 蚁群算法基本原理

3.2.2 蚁群算法求最短路径的步骤

3.3 粒子群算法

3.3.1 粒子群算法基本原理

3.3.2 粒子群算法求最短路径的步骤

3.4 遗传算法

3.4.1 遗传算法基本步骤

3.4.2 遗传算法求解最短路径问题

3.5 求解K条最优路径问题

3.6 求解K条路径的算法比较

3.7 多目标优化问题

3.7.1 多目标遗传算法

3.7.2 多目标遗传算法计算路程长度和时间的实例

3.8 动态交通诱导系统的算法设计

3.8.1 改进的K条最优路径遗传算法

3.8.2 K条最优路径遗传算法实现多目标优化

3.8.3 系统的算法流程

3.9 算法运行结果比较

4 交通诱导系统动态性的设计

4.1 模拟产生交通数据

4.1.1 隶属度函数

4.1.2 一维隶属函数的形式和参数化

4.2 计时器的触发

4.3 求解动态交通诱导问题的算法流程

5 数值对比与系统运行结果

5.1 数值对比

5.2 系统运行结果

5.3 本章小结

6 总结和展望

致谢

参考文献