原文传递
基于遗传算法的区域交通网络最短路径算法研究
| 论文题名： | 基于遗传算法的区域交通网络最短路径算法研究 |
| 关键词： | 公交车线网;优化设计;K最短路算法;候选路集;遗传算法 |
| 摘要： | 公交车是城市公共交通的重要组成部分之一，因此，公交车线网的优化设计就显得尤为必要了。公交车线网的优化研究旨在于在现有城市道路系统下，通过合理的布局、规划，使得城市公交车系统的运载能力得到充分的发挥，这对于提高城市的公交服务水平、效率，改善城市的交通状况有着重要意义。公交车线网优化设计问题(BusTransit Route Network Design Problem，BTRNDP)是在上世纪60年代提出的一类组合优化的多目标决策问题，经过国内外专家及学者几十年的时间的努力，逐渐形成了比较完善的研究理论体系，并在此基础上，越来越多的应用在智能交通系统上。上世纪90年代，国外学者Baaj和Mahamassani建立了一套基于人工智能的线网的优化解决方案，随后，越来越多的学者开始应用遗传算法(如标准遗传算法、并行遗传算法等)进行公交车线网优化设计问题的研究，并取得了一系列的成果，而遗传算法由于线网优化设计方法的不同，在不同层面上有各自的适用局限性。 本文由公交线网的研究背景、国内外研究现状、公交线网优化模型研究、遗传算法的研究以及算法的实现及测试等几个部分组成。 本文首先从公交车线网起讫点的选址、线网的约束条件分析(如直达客流量、乘客出行总时间成本、公交企业效益等)等几个方面研究创建公交车线网优化的数学模型，研究学习K最短路径算法以及启发式搜索算法(A*)算法，并采用二者生成公交车线网的候选路集，以此作为公交车线网优化设计问题的可行解空间。 本文分析了标准遗传算法(Standard Genetic A1gorithm，SGA)的一些缺陷(如早熟和接近最优解时收敛缓慢等)，并从遗传编码、杂交算子以及变异算子等方面尝试对标准遗传算法作出了一些改进，结合公交车线网优化的数学模型，实现了一种基于改进的遗传算法(Improved Genetic Algorithm，IGA)对公交车线网优化设计问题的求解方法。随后，本文基于VC++环境编写程序，验证了算法结果。 最后，论文对本文进行了总结，指出了论文的几个关键点，并对有待于进一步研究的问题进行了展望。 |
| 作者： | 谭强强 |
| 专业： | 计算机 |
| 导师： | 余永权 |
| 授予学位： | 硕士 |
| 授予学位单位： | 广东工业大学 |
| 学位年度： | 2012 |
| 正文语种： | 中文 |
检索历史
应用推荐
