城市公交网络最优路径求解算法研究

论文摘要

我国的土地资源稀缺,城市人口密集,近年来随着城市化和工业化进程的不断推进,城市公共交通通行能力较差等一系列问题日益凸显,严重制约了城市发展。作为与人民群众生产生活息息相关的重要基础设施之一的城市公共交通,优先发展城市公共交通是符合交通发展的实际和城市化进程的需要。2005年,温家宝总理和曾培炎副总理就曾分别批示,要求优先发展城市公共交通;随后,国务院办公厅转发了建设部等部委《关于优先发展城市公共交通的意见》,指出:“优先发展城市公共交通是提高交通资源利用效率,促进城市健康发展,缓解交通拥堵的重要手段。”足可见城市公共交通的重要。而从城市交通运输业的发展现状和趋势看,公交线路与资源配置网络化已成为所有城市发展公共交通的战略和长远选择,但在公交线路与资源配置网络化中如何作到覆盖面最广,有效利用率最高,这就涉及到如何用最优规划设计的方法来合理配置。攀枝花是一个沿江依山建起的城市,近年来城市交通也出现拥堵情况,但由于受到自身地理环境限制,所以在交通路网的再扩建存在一定的局限,为此我们要思考的是如何在行人出行时对公交线网进行寻优选择。本文研究的主要内容就是最优路径在城市公共交通中的应用。文章的结构按照“模型建立—算法研究”的思路来组织。在研究城市公交线网模型中,首先详细分析了城市公交网络的特点,指出道路网络模型并不适合公交网络模型。同时,指出了如何从具体的公交网络抽象成公交网络拓扑模型,详细研究了公交站点的分布情况,给出了对公交站点进行合理的抽象、合并的方法和原则。最后给出公交网络到拓扑模型的建模方案和公交网络拓扑模型的相应定义。在最优路径算法研究中,前期分析了乘客选择公交出行的主要考虑因素,提出了公交线网最优路径模型,针对此模型给出了三种典型算法——狄斯奎诺(Dijkstra)算法,K最短路径算法以及基于最小换乘次数的广度优先算法。最后对模型改进提出了简单适应度函数;对算法的改良体现在运用了遗传算法和基于遗传算法的蚁群算法。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 本课题研究的目的和意义
• 1.1.1 本课题的现实意义
• 1.1.2 本课题的理论意义和相关技术的研究现状
• 1.2 论文主要工作
• 1.2.1 设计目标
• 1.2.2 模型建立
• 1.2.3 主要工作
• 1.3 章节安排
• 第二章 公交网络拓扑化
• 2.1 图论基本知识
• 2.2 道路公交网络的特点
• 2.3 城市公交线网的实现
• 2.4 公交网络拓扑结构
• 2.4.1 可合并为同一换乘结点的几种空间位置关系
• 2.4.2 生成同一换乘结点的几点原则
• 2.4.3 攀枝花市民步行换乘距离上限的求解
• 2.4.4 攀枝花主城区（以竹湖园到公山湾路段为例）道路公交拓扑化
• 2.5 本章小结
• 第三章 城市公交线网的最优路径模型
• 3.1 对攀枝花市市民出行行为与心理的调查
• 3.2 公交线网最优路径模型的建立
• 3.3 公交线网中网络变换的实现方法
• 3.4 实例分析
• 3.5 本章小结
• 第四章 城市公交线网最优路径模型求解的三种传统算法
• 4.1 公交网络搜索模型的建立
• 4.2 模型求解的三种传统算法
• 4.2.1 狄斯奎诺算法
• 4.2.2 K 最短路径算法
• 4.2.3 基于换乘次数最少的广度优先算法
• 4.3 基于传统算法的时间评价函数
• 4.4 本章小结
• 第五章 基于遗传算法的城市公交线网最优路径求解
• 5.1 遗传算法简介
• 5.2 遗传算法的具体流程
• 5.2.1 一般遗传算法的基本步骤
• 5.2.2 遗传算法的流程图
• 5.3 基于遗传算法的攀枝花主城区公交线路分析
• 5.3.1 简述问题
• 5.3.2 染色体编码
• 5.3.3 构造简单适应度函数
• 5.3.4 三个基本算子
• 5.3.5 评价方法
• 5.3.6 仿真实验
• 5.4 本章小结
• 第六章 基于蚁群算法的城市公交线网最优路径求解
• 6.1 蚁群算法简介
• 6.2 蚁群算法的流程
• 6.3 基于遗传算法的蚁群算法
• 6.3.1 基本思想
• 6.3.2 粗搜索过程
• 6.3.3 细搜索过程
• 6.4 算法算例
• 6.4.1 算例流程图
• 6.4.2 仿真实验
• 6.4.3 算法分析
• 6.5 遗传算法与蚁群算法的比较
• 6.6 本章小结
• 第七章 总结与展望
• 致谢
• 参考文献
• 攻硕期间取得的成果