基于蚁群算法的动态路径诱导研究

论文摘要

动态路径诱导系统(Dynamic Route Guidence System,DRGS)是智能交通系统的一个重要内容。它根据出行的起止点向驾驶员提供最优路径指引和其他丰富的实时交通信息,通过诱导驾驶员的出行行为来改善路面交通系统,防止交通阻塞的发生,减少车辆在道路上的逗留时间,并且最终实现交通流在路网中各个路段上的合理分配。最短路径选择是动态诱导系统的核心内容和主要目标,随着城市路网规模的不断扩大和交通流量的显著增加,原有的路径诱导算法已经不能满足动态路网实时性的要求。蚁群算法作为一种新兴的人工智能算法,具有良好的全局优化能力、本质上的并行性、求解时间短、易于计算机实现等优点,已被应用于高度复杂的组合优化、通信网络的路由选择、车辆调度等问题,取得了良好的效果。本文围绕最短路径选择问题,对在动态路网中求解最短路径的几个关键问题如:动态路网的模型,路网边的权值——行程时间的计算,算法的选择等进行了扼要的介绍,选择了性能更好的蚁群算法所为最短路径选择算法。本文重点分析了蚁群算法的原理,模型,以及参数的设置,并针对其存在的缺点给出了一种改进算法——基于信息素扩散的双种群蚁群算法(PDDPAS)。本文选取了三个不同规模的TSP问题对PDDPAS算法进行实验,分别对PDDPAS算法性能,参数的设置,信息素扩散的策略进行考察,并得出了相应的设置方案。结果表明,改进的PDDPAS算法具有寻优能力强,收敛速度快,参数设置稳定的优点。最后,本文将PDDPAS算法在路网地图上进行了简单的实现。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 研究的背景及意义
• 1.2 研究现状
• 1.3 本文研究内容及章节安排
• 第2章 动态路径诱导的关键问题
• 2.1 动态路径诱导的理论基础
• 2.2 动态路网的表达
• 2.2.1 动态网络模型
• 2.2.2 动态网络的最短路径问题
• 2.3 行程时间的计算
• 2.3.1 行程时间的主要参数
• 2.3.2 路段行程时间模型
• 2.3.3 路段行程时间的预测
• 2.4 人工智能算法
• 2.5 本章小结
• 第3章 基本蚁群算法
• 3.1 基本蚁群算法的原理
• 3.2 基本蚁群算法的模型
• 3.3 基本蚁群算法的流程
• 3.4 蚁群算法参数的设置
• 3.5 基本蚁群算法优缺点
• 3.6 本章小结
• 第4章 蚁群算法的改进
• 4.1 几种改进的蚁群算法
• 4.1.1 精英蚂蚁系统（ASelite）
• 4.1.2 优化排序蚂蚁系统（ASrank）
• 4.1.3 最大最小蚂蚁系统（MMAS）
• 4.1.4 最优最差蚂蚁系统（BWAS）
• 4.2 基于信息素扩散的双种群蚁群算法
• 4.2.1 信息素扩散策略
• 4.2.2 双种群策略
• 4.2.3 算法的描述
• 4.2.4 算法的流程
• 4.2.5 算法时间复杂度分析
• 4.2.6 仿真结果与分析
• 4.3 本章小结
• 第5章 PDDPAS在路网上的实现
• 5.1 路径诱导与TSP问题的区别
• 5.2 地图的使用
• 5.3 PDDPAS的具体设计
• 5.3.1 算法的具体设计
• 5.3.2 算法的流程
• 5.3.3 算法关键步骤的实现
• 5.4 PDDPAS的实现
• 5.5 本章小结
• 结论
• 致谢
• 参考文献
• 攻读硕士学位期间发表的论文