基于多因素分析动态路网最佳路径求解的算法研究

摘要

在当今社会经济活动中，交通运输作为主要载体，在各个行业中发挥着非常重要的作用。随着社会不断的发展和经济不断地增长，机动车辆数目急剧增加，从而使得道路的负荷量日益加重，经常出现道路拥堵、交通事故频发、环境污染严重等问题。目前，智能交通系统是解决或缓解交通问题的最有效途径，其中它的一个重要组成部分是动态诱导系统。该系统是结合实际动态的路况信息，利用智能算法为出行者搜索出一条高效、合理的最佳路径，不仅可以帮助出行者节省出行时间，而且还能缓解交通道路的负荷量，同时也能够提高能源的利用率，减少机动车尾气对环境的污染。无论是对人们的生活还是对社会发展都具有非常重要的作用。　　本文结合影响交通路网的多因素，深入研究了各种路径优化的智能算法，在此基础上提出了混合蚁群粒子群算法，并通过该算法分析了多因素动态路网下的最佳路径，具体工作如下：　　1)本文首先通过分析影响动态路网求解最佳路径的多种因素，根据出行者的需求，建立不同的模型来表示路段的权值，并深入研究了路径优化算法，重点分析了蚁群算法和粒子群算法。　　2)然后，比较与分析了这两种算法的优缺点，提出了混合蚁群粒子群算法。该算法主要是利用粒子群算法来初始化蚁群算法的参数，并混合这两种算法的优点，使蚂蚁也具有粒子的特性。通过实验验证，混合蚁群粒子群算法无论是在求解精度上还是收敛速度上都要优于蚁群算法和粒子群算法。　　3)最后，通过混合蚁群粒子群算法分析了多因素动态路网下的最佳路径，得出以下结论：①通过调整，证明了该算法在城市路网中求解最佳路径是行之有效的；②出行者的最优目标不同，最佳路径的选择也可能不相同；③即使出行者以相同的需求作为最优目标，不同时刻最佳路径的选择也可能不同。

目录

声明

1 绪论

1.1研究背景与研究意义

1.2国内外的研究现状

1.3本文的研究内容

1.4本文的组织结构

2 动态路网求解最佳路径问题概述

2.1 动态路网的表达方式

2.2 动态路网求解最佳路径问题的研究因素

2.3 动态路网最佳路径问题的分类

2.4本章小结

3路径优化问题的算法分析

3.1 Dijkstra算法

3.2启发式搜索算法一一A*算法

3.3蚁群算法

3.4粒子群算法

3.5 四种算法比较

3.6 蚁群算法与粒子群算法比较

3.5本章小结

4混合蚁群粒子群算法

4.1混合蚁群粒子群算法的原理

4.2混合蚁群粒子群算法的步骤及流程图

4.3仿真结果与分析

4.4本章小节

5 基于多因素分析动态路网的最佳路径

5.1动态路网最佳路径问题与TSP问题的区别

5.2 AC-PSO算法的调整

5.3 基于AC-PSO算法分析多因素动态路网的最佳路径

5.4 本章小节

6 总结与展望

6.1总结

6.2展望

致谢

参考文献

附录A 本文采用的道路拥堵等级数据表

附录B 本文部分主要代码

攻读硕士期间取得的研究成果