城市道路网中蚁群最短路径算法研究

论文摘要

最短路径问题既是网络分析中的基本问题,也是与道路交通息息相关的热点问题。近年来,蚁群算法作为智能算法大家庭的一员,以其很强的发现较好解的能力,逐渐受到广大学者们的青睐,也越来越多地应用于求解各种复杂问题。论文主要以昆明市电子地图为基础,构建其道路网拓扑结构,并在该网络平台上进行蚁群最短路径算法的研究。针对蚁群算法收敛速度慢,易停滞等缺陷,提出了一系列改进方案。论文还对交通拥塞时的蚁群优化算法进行了研究。论文的研究成果主要包括：（1）基于昆明市城市电子地图,通过GIS组件和VC++进行二次开发,提取了地图中的结点信息和道路信息,完成了道路网拓扑结构的构建,为后续算法研究提供了平台。（2）以旅行商问题为例分析了蚁群算法,比较了旅行商问题和最短路径问题的差异,实现了求解最短路径问题的蚁群算法,并深入分析了参数对算法的影响。（3）针对蚁群算法收敛速度慢,搜索精度差等问题,通过改变距离启发因子的形式和信息素的更新方式对算法进行了改进,提出了基于灯光素的蚁群算法。实验结果从运行时间、解的优劣性等方面表明了改进算法的高效性。（4）利用信息素浓度模拟交通拥塞现象,设计了用于求解交通拥塞情况下的最短路径的AS-BTJ算法,并实验验证了算法的可行性。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 城市交通中的典型问题和应对措施
• 1.2 研究现状和意义
• 1.3 论文主要研究内容
• 2 最短路径问题分析
• 2.1 最短路径问题的分类和特点
• 2.2 最短路径的搜索策略
• 2.2.1 深度优先搜索
• 2.2.2 广度优先搜索
• 2.2.3 启发式搜索
• 2.3 Dijkstra算法
• 2.4 本章小结
• 3 城市道路网拓扑结构的构建
• 3.1 地理信息系统
• 3.2 GIS开发方法
• 3.3 网络拓扑构建前的准备
• 3.3.1 MapX简介
• 3.3.2 MapInfo简介
• 3.3.3 VC++使用MapX组件之前的工作
• 3.4 道路拓扑的构建
• 3.4.1 空间关系基本概念
• 3.4.2 基于MapX的道路拓扑构建
• 3.4.3 道路拓扑构建结果
• 3.5 本章小结
• 4 蚁群算法的研究及实现
• 4.1 群智能算法概述
• 4.2 蚁群算法的生物学描述
• 4.3 基本蚁群算法模型
• 4.3.1 TSP问题描述
• 4.3.2 蚁群算法描述
• 4.3.3 蚁群算法求解TSP问题
• 4.3.4 最短路径问题与TSP问题的差异
• 4.3.5 蚁群算法求解最短路径问题
• 4.3.6 蚁群算法在最短路径问题中的收敛性分析
• 4.4 蚁群算法参数分析
• 4.4.1 基本参数分析
• 4.4.2 实验参数的确定
• 4.5 本章小结
• 5 蚁群算法的改进
• 5.1 几种改进蚁群算法介绍
• 5.1.1 带精英策略的蚂蚁系统
• 5.1.2 最大-最小蚂蚁系统
• 5.1.3 最优-最差蚂蚁系统
• 5.2 蚁群算法的进一步改进方案
• ij的改进'>5.2.1 关于可见度因子η_ij的改进
• 5.2.2 对于蚁群算法选择概率的改进
• 5.2.3 关于信息素浓度的更新
• 5.3 基于"灯光素"的蚁群算法
• 5.3.1 问题分析
• 5.3.2 灯光素的初始化和更新方式
• 5.3.3 信息素浓度启发因子的改进
• 5.3.4 基于灯光素的蚁群算法实现
• 5.4 改进蚁群算法的实验
• 5.4.1 参数设置
• 5.4.2 不同算法之间比较
• 5.5 本章小结
• 6 关于交通拥塞问题的蚁群优化算法研究
• 6.1 基本问题分析
• 6.2 基于交通拥塞的蚁群算法
• 6.2.1 多路径交通分配问题
• 6.2.2 道路信息素适应性改进
• 6.2.3 距离启发信息适应性改进
• 6.2.4 AS-BTJ算法描述
• 6.3 AS-BTJ算法实验
• 6.4 AS-BTJ算法总结
• 6.5 本章小结
• 7 总结与展望
• 7.1 总结
• 7.2 展望
• 致谢
• 参考文献