基于公交网络模型的最优路径算法研究与实现

摘要

城市公共交通是整个城市交通系统中的一个重要组成部分，它的发展水平是衡量城市现代化程度的重要标志，同时也是解决大中城市交通拥挤问题的最佳途径。而基于公交网络模型的最优路径选择是城市公共交通中的一个重要子系统，是公共交通优先的保证，它对城市结构的完善、土地使用的合理化有着重要的意义。 本文首先对国内外城市基于公交网络模型的最优路径算法的研究和实践进行了总结，在此基础上分析了城市公交系统高效运行的实现条件和影响因素。接着介绍公交网络的图的存储表示，并在分析公交网络模型的基础上将其抽象成具有拓扑性质的网络图。然后提出了用“平均换乘次数”来对公交网络的可达性进行评价，并给出了基于N次换乘矩阵和基于A*算法的平均换乘次数计算方法。如果在乘客的步行距离范围内，他们可能步行以减少公交换乘的次数，本文据此给出了一种考虑步行换乘的平均换乘次数计算方法，并且通过一个实例分析验证了该算法的有效性。 对于公交网络最优路径选择问题，本文给出了两种算法：一种是基于网络变换的最短路径算法，公交网络经过网络变换，有换乘的网络问题变换为没有换乘的网络问题，避免了计算直达矩阵与最小换乘矩阵；一种是基于前N条最短路径的以换乘次数最小为第一目标、出行距离最短为第二目标的路径选择模型，并考虑乘客在步行距离范围内步行以减少公交换乘次数的实际情况，给出了一个考虑步行换乘的双目标公交路径选择算法。 本文以长沙派诺电子科技有限公司提供的长春市城市空间数据为基础，完成了长春市公交信息查询系统的设计与开发。系统的主要功能公交网络最优路径查询，用户通过键盘输入起终点或图上点击选择起终点，然后系统就可以列出所有的以换乘次数最少为第一目标、出行路径最短为第二目标的出行方案。另外，系统还有信息查询功能即公交站点查询、公交线路查询、地名查询及公共场所查询等，并可进行精确查询和模糊查询。 最后，对本文进行了总结，并对进一步的研究提出了一些建议和展望。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景

1.2研究的意义及目的

1.2.1研究的意义

1.2.2研究的目的

1.3国内外研究现状

1.3.1国内研究现状

1.3.2国外研究现状

1.4论文的结构和研究方法

1.4.1论文的结构

1.4.2论文的研究方法

第二章公交网络模型的基本数据组织

2.1图

2.1.1图论中的基本概念

2.1.2图的表示方法

2.2公交网络模型

2.2.1公交网络的构成要素

2.2.2公交网络的特点

2.2.3公交网络表示方法

2.3公交网络抽象

2.3.1节点抽象

2.3.2弧段抽象

2.4公交网络的拓扑表示

第三章平均换乘次数的计算方法

3.1平均换乘次数的提出

3.2基于N次换乘矩阵的平均换乘次数计算方法

3.2.1公交网络的邻接矩阵表示

3.2.2算法基本步骤

3.2.3算例分析

3.3基于A*算法的平均换乘次数计算方法

3.3.1 A*算法概述

3.3.2算法基本步骤

3.3.3算例分析

3.4考虑步行换乘的平均换乘次数计算方法

3.4.1算法基本假设与思路

3.4.2算法基本步骤

3.4.3算例分析

第四章公交网络最优路径选择

4.1经典最短路径搜索算法

4.1.1 Dijkstra算法概述

4.1.2改进的Dijkstra算法

4.2基于网络变换的公交网络最短路径选择

4.2.1网络变换方法

4.2.2算例分析

4.3基于换乘次数最少的最短路径选择

4.3.1利用Dijkstra算法求解前N条最短路径问题

4.3.2基于前N条最短路径算法的双目标公交路径选择

4.3.3算例分析

4.4考虑步行情况的双目标公交路径选择

4.4.1起终站点均不是“中间站点”的算法步骤

4.4.2起终站点至少有一个是“中间站点”的算法步骤

第五章基于MapX的城市公交信息查询系统设计

5.1系统目标

5.2系统平台选择

5.2.1实验数据

5.2.2开发工具——Visual Basic 6.0

5.2.3数据库平台——Access 2003

5.2.4 GIS控件——MapX 5.0

5.3系统实现过程

5.3.1地图的获取

5.3.2坐标系的定义与转换

5.3.3数据与属性数据的关联

5.4系统总体框架

5.4.1系统开发结构

5.4.2系统界面组织

5.4.3系统功能实现

第六章总结和展望

6.1总结

6.2展望

参考文献

致 谢

攻读学位期间主要的研究成果