本科毕业设计论文公交线路查询算法研究与实现

1、摘 要随着中国经济的发展与社会信息化水平的推进，以计算机技术为代表的信息技术的应用已经深入到各行各业中了。公交作为国家的经济大动脉是城市的重要组成部分，在国家经济和人民生活中发挥着重要作用并与人们的生活息息相关。以西安市为例，全市现有线路200余条，站点几千个，覆盖了西安市的绝大部分区域，公交已成为市民最重要的出行方式。在关于公交的众多问题当中，公交换乘是人们最关心的问题。每一个市民所熟悉的公交线路是有限的，当去一个不熟悉的地方，如何乘坐公交车前往是市民常常遇到的问题，因此我们需要构建一个城市公交换乘系统，当市民输入出发站点与目的站点后，该系统能够根据一定的规则，例如，换乘次数最少，路程最短，

2、票价最低等，给出一些乘车的方案，市民按照乘车方案的文字描述或电子地图(GIS)的直观显示，可以准确快捷的从出发点到目的地。本文首先分析了图论及相关的背景知识，这其中包含了对公交网络进行数学建模及对其求解平均换乘次数等。在此基础上针对市民乘车的实际问题提出了多种不同的换乘算法，包括改进的Dijkstra算法，利用数据库在集合运算方面的优秀性能而提出的扩展集合算法(广度优先搜索算法)及其改进，用邻接矩阵构造换乘矩阵实现的换乘算法；人工智能方面的算法(启发式搜索算法)A*算法在换乘方面的应用及其改进算法A*！算法，基于蚂蚁算法实现的公交换乘算法，基于Web GIS的算法。最后，在分析完上述算法并比较

3、其优劣势后，在Microsoft Visual C+编程环境下实现了一种算法并对其进行分析与测试。各种测试表明，作者所开发的公交线路查询系统完全符合理论假设并有一定实用价值。关 键 词：公交换乘 数学建模 Dijkstra算法 扩展集合算法 换乘矩阵算法 A*算法 A*！算法 蚂蚁算法 Web GISABSTRACT With the development of chinas economic and the improvement of social information level, the application of information technology including

4、 computer technology have been deeply rooted in every kinds of business. Bus, as the big artery of national economic, is one of the most important parts of a city. It exerts a great important function in national economic and individuals life and has a strong relation with peoples activity. Take XIA

5、N as an example, there are more than 200 bus lines and thousands of sites there. They cover almost every region of XIAN and become the most important travel method. Bus transfer is the most concerned problem in all these problems. The bus-lines which every citizen are familiar with are limited. When

6、 we come to a place that we never come to before, how to get there with bus is the most frequent problem. So we need to build a city bus transfer system. When the users input the start site and the destination site, according to some rules, for example, the least transfer, the shortest path, and the

7、 lowest price, etc, the system can give us some suggestions on bus transfer, we can get to our destinations in the light of these suggestions with a written descriptions or map description using GIS accurately and conveniently. In this essay, the author first introduced some knowledge about graph th

8、eory and some other backgrounds, including building up a math model about bus network, resolving average transfer times based on this, etc. Based on this model, the author propose lots of different transfer algorithms, including Dijkstra algorithm and its improvement; expanding set algorithm (breath

9、 first search about graph) and its improvement which depending on the databases excellent performance on set mathematic operations, using adjacency matrix to construct transfer matrix algorithm, artificial intelligence algorithm (inspiring algorithm)A* algorithm used on bus transferring and its impr

10、ovementA*! algorithm , bus transfer algorithm based on ant algorithm, WEB GIS algorithm. At last, after analysised the algorithms mentioned above and compared the superiorities and inferiors of these algorithms, the author implement one of these algorithms in the visual C+ environment, then do some

11、analysis and tests. The tests manifest the bus transfer system the author developed fits the theories very well and has some practical values. Keywords: bus transfer math module Dijkstra algorithm expanding set algorithm transfer matrix algorithm A* algorithm A*! algorithm ant algorithm WEB GIS目 录 T

12、OC o 1-3 h z u HYPERLINK l _Toc201063205 第一章 绪 论 PAGEREF _Toc201063205 h 1 HYPERLINK l _Toc201063206 1.1城市公交问题提出的背景与意义 PAGEREF _Toc201063206 h 1 HYPERLINK l _Toc201063207 1.2我国城市公交及国内外研究现状 PAGEREF _Toc201063207 h 2 HYPERLINK l _Toc201063208 1.3研究的目的，内容及方法 PAGEREF _Toc201063208 h 3 HYPERLINK l _Toc20

13、1063209 1.4公交换乘问题及公交网络建模的概况 PAGEREF _Toc201063209 h 4 HYPERLINK l _Toc201063210 第二章 公交网络的拓扑建模 PAGEREF _Toc201063210 h 7 HYPERLINK l _Toc201063211 2.1图的相关概念 PAGEREF _Toc201063211 h 7 HYPERLINK l _Toc201063212 2.2城市公交网络模型的建立 PAGEREF _Toc201063212 h 9 HYPERLINK l _Toc201063213 2.2.1公交乘车模型 PAGEREF _Toc2

14、01063213 h 9 HYPERLINK l _Toc201063214 2.2.2公交网络的有向图结构 PAGEREF _Toc201063214 h 10 HYPERLINK l _Toc201063215 2.2.3公交网络拓扑图中的权值的设定 PAGEREF _Toc201063215 h 13 HYPERLINK l _Toc201063216 2.3公交网络性能与平均换乘次数 PAGEREF _Toc201063216 h 14 HYPERLINK l _Toc201063217 2.3.1公共交通网的技术指标 PAGEREF _Toc201063217 h 14 HYPERL

15、INK l _Toc201063218 2.3.2公共交通线路网平均换乘次数的研究 PAGEREF _Toc201063218 h 16 HYPERLINK l _Toc201063219 2.3.3平均公交换乘次数的实例分析 PAGEREF _Toc201063219 h 19 HYPERLINK l _Toc201063220 第三章 求解公交换乘问题的各类算法设计 PAGEREF _Toc201063220 h 22 HYPERLINK l _Toc201063221 3.1Dijkstra算法及其改进 PAGEREF _Toc201063221 h 22 HYPERLINK l _To

16、c201063222 3.1.1Dijkstra算法简介 PAGEREF _Toc201063222 h 22 HYPERLINK l _Toc201063223 3.1.2将Dijkstra算法直接运用在公交换乘方面所存在的问题 PAGEREF _Toc201063223 h 22 HYPERLINK l _Toc201063224 3.1.3改进的Dijkstra算法 PAGEREF _Toc201063224 h 23 HYPERLINK l _Toc201063225 3.1.4 Dijkstra算法的应用范围 PAGEREF _Toc201063225 h 23 HYPERLINK

17、l _Toc201063226 3.2扩展集合算法 PAGEREF _Toc201063226 h 23 HYPERLINK l _Toc201063227 3.2.1算法概要 PAGEREF _Toc201063227 h 24 HYPERLINK l _Toc201063228 3.2.2算法的不足 PAGEREF _Toc201063228 h 24 HYPERLINK l _Toc201063229 3.2.3算法的改进 PAGEREF _Toc201063229 h 25 HYPERLINK l _Toc201063230 3.2.4算法的应用 PAGEREF _Toc2010632

18、30 h 28 HYPERLINK l _Toc201063231 3.2.5应用领域 PAGEREF _Toc201063231 h 30 HYPERLINK l _Toc201063232 3.2.6补充：基于扩展集合思想算法的其他实现 PAGEREF _Toc201063232 h 31 HYPERLINK l _Toc201063233 3.3人工智能算法 PAGEREF _Toc201063233 h 33 HYPERLINK l _Toc201063234 3.3.1启发式搜索算法A*算法 PAGEREF _Toc201063234 h 33 HYPERLINK l _Toc201

19、063235 3.3.2蚂蚁算法 PAGEREF _Toc201063235 h 35 HYPERLINK l _Toc201063236 3.4基于WEB GIS的公交线路查询算法 PAGEREF _Toc201063236 h 37 HYPERLINK l _Toc201063237 3.4.1 GIS的概念及其发展现状 PAGEREF _Toc201063237 h 37 HYPERLINK l _Toc201063238 3.4.2 WEB GIS的概念，特点，及应用 PAGEREF _Toc201063238 h 38 HYPERLINK l _Toc201063239 3.4.3基

20、于WEB GIS的公交最短路径算法实现 PAGEREF _Toc201063239 h 39 HYPERLINK l _Toc201063240 3.4.4本算法分析 PAGEREF _Toc201063240 h 42 HYPERLINK l _Toc201063241 第四章 公交线路查询系统的设计与实现 PAGEREF _Toc201063241 h 43 HYPERLINK l _Toc201063242 4.1公交线路查询系统需求分析 PAGEREF _Toc201063242 h 43 HYPERLINK l _Toc201063243 4.2公交线路查询系统概要设计 PAGERE

21、F _Toc201063243 h 44 HYPERLINK l _Toc201063244 4.3公交线路查询系统详细设计 PAGEREF _Toc201063244 h 45 HYPERLINK l _Toc201063245 4.3.1数据结构的设计 PAGEREF _Toc201063245 h 45 HYPERLINK l _Toc201063246 4.3.2系统模块详细设计 PAGEREF _Toc201063246 h 45 HYPERLINK l _Toc201063247 4.4公交线路查询系统的编码与测试 PAGEREF _Toc201063247 h 49 HYPERL

22、INK l _Toc201063248 第五章 全文总结 PAGEREF _Toc201063248 h 50 HYPERLINK l _Toc201063249 5.1本文小结 PAGEREF _Toc201063249 h 50 HYPERLINK l _Toc201063250 5.2补充讨论 PAGEREF _Toc201063250 h 50 HYPERLINK l _Toc201063251 致 谢 PAGEREF _Toc201063251 h 51 HYPERLINK l _Toc201063252 参考文献 PAGEREF _Toc201063252 h 52 HYPERLI

23、NK l _Toc201063253 附录A 主算法的代码 PAGEREF _Toc201063253 h 53 HYPERLINK l _Toc201063254 附录B 程序中数据存储结构(头文件) PAGEREF _Toc201063254 h 57 第一章 绪 论1.1城市公交问题提出的背景与意义在中国，伴随着经济的崛起，城市也在不断发展，城镇化的水平越来越高，城市的规模也越来越大了。为了满足城市发展的需要，城市公共交通运输的覆盖面越来越广，公交线路也日渐增多，乘坐公交出行变得越来越便捷，越来越多的出行者选择公交作为自己的首选出行方案。与此同时，公交给人们带来极大的便利的时候，也因线路

24、众多，给人们在选择出行线路时带来一定的麻烦。人们在所熟知的公交线路有限的情况下，想要到达一个陌生的地点是有一定难度的，或者即使到达目的地也因不了解线路而耗费更多的时间或金钱。因此，提供方便，经济，高效，优化的公交出行线路方案，不仅能够方便本市市民的出行，对于外来游客，出差等的人的出行与生活都能带来极大的便利。对于缓解城市的交通堵塞，提高城市的交通运输效率也是有帮助的。当前胡总书记提出要建立和谐社会主义，运用科学发展观，建立此系统能够充分反映出城市建设的人性化，以人为本的思想，对于社会和谐，城市的健康快速发展是有好处的。随着车辆数的增多，城市交通问题日趋严重，行车不畅通，车辆延误，并且产生了巨大

25、的空气污染与噪音污染，与可持续发展思想不符，公交作为城市可持续发展交通的重要组成部分，在使用本系统后将吸引更多的人选择它出行，有利于可持续发展。2008年又是中国的奥运年，有许多外国朋友来到中国，西安作为中华文明的代表，世界四大古都之一，必然会迎来许多的外国游客，本系统能够展示一个现代化的城市的信息化的风貌，有利于提升城市形象，有利于招商引资，促进城市的繁荣。对于建立信息化社会，实现企业，行业，社会三层的信息化，抢占信息时代的制高点，是有一定贡献的。公交作为城市动态大系统中的一个重要组成部分，是城市发展中不可缺少的物质条件与基础产业，也是联系社会生产，流通和人民生活的纽带。没有城市公交的高速运

26、转，就没有城市的现代化。通过世界上绝大多数发达国家的城市发展模式与经验来看，优先发展公共交通已经被大多数国家作为解决大，中城市交通问题的最佳策略。它是城市可持续发展的保障，因此在我国各大城市建立高效的，功能强大，人性化的公交系统刻不容缓。1.2我国城市公交及国内外研究现状截至1994年底，全国城镇人口为34301万人，占全国人口的28.26%，百万人口以上的大城市有32个，按目前的城市化进程，预计在2010年或稍后，城市人口可达6.5亿，城市化水平在50%左右。展望城市未来的发展，城市客运交通的发展必须与之相配套。对大城市自身而言，还呈现如下的特点：1.大城市自行车拥有量趋于饱和，越来越多的私

27、家车的出现加重了交通拥堵；2.城市用地扩大，导致公交出行距离增加，换乘问题至关重要；3.道路网络设施供应不足，路网容量不足，结构不合理；4.公交管理手段落后，还没有全面信息化，智能化。西方国家对这些方面重视的较早，如美国，日本，欧洲诸国等，他们已投入了极大的人力，财力在城市公交网络的构建上，现在已经形成了使用计算机网络与通信系统进行管理的智能交通系统ITS（Intelligence Transport System），从而可以实时，准确，高效的在大范围内全方位的进行运输综合管理，使得人，车，路三者之间的关系更加和谐统一，极大的改善交通状况。 智能交通系统(Intelligent Transpo

28、rt System简称ITS)ITS是一个广泛包括各种技术的统称，是在较完善的道路设施基础上，将先进的计算机、电子技术、信息技术、传感器技术和系统工程技术集成，运用于地面交通的实际需求，建立起全方位、实时准确、高效的地面交通系统。它能使交通基础设施发挥出最大的效能，提高服务质量，使社会能够高效地使用交通设施和资源，从而获得巨大的社会经济效益。智能交通系统不但可能解决交通的拥挤，而且对交通安全、交通事故的处理和救援、客货运输管理、公路收费系统等方面都会产生巨大的影响。 1995年3月美国交通部首次正式出版了“国家智能交通系统项目规划”，明确规定了智能交通系统的7大领域和29个用户服务功能，并确定

29、了到2005年的年度开发计划。其中7大领域包括：出行和交通管理系统、出行需求管理系统、公共交通运营系统、商用车辆运营系统、电子收费系统、应急管理系统、先进的车辆控制和安全系统。应用发展较快的几个方面分别是，车辆安全系统(占51%)，电子收费 (占37%)，公路及车辆管理系统(占28%)，实时自动定位系统(占20%),商业车辆管理系统(占14%)。日本组成了由四省一厅参加的全国统一智能交通系统开发组织(VERTIS)，并于1996年制定了“推进ITS总体构想”。并推出了一个投资预算达7.8兆亿日元，为期长达20年的发展计划，包含了智能子系统部分应用、改善基础设施建设及系统和产品的研究开发。同时日

30、本国内丰田、三菱、东芝等100多家企业也联合设立智能运输系统的开发和经营机构，加大智能交通产品开发的力度。近年，日本投入了15亿日元开发了全国公路电子地图系统，打开了车辆电子导航市场。 而我国的城市公交信息系统的研究处于相对落后的水平，广大乘客获取信息的渠道与方式很少，公交信息的完整性与准确性得不到保证，而且没有专门的机构负责信息的发布与管理。我国的公交信息系统的现状如下：1.乘客获取的公交信息很少，而且以常规的手段为主。 我国乘客一般获取公交信息的手段有交通图，向熟悉的人问询等。乘客获得公交信息很少，除去线路，站点等信息，有关班次，车辆到离站时间的信息基本没有。2.乘客出行中获取信息困难，基

31、本上没有实时信息。除杭州等少数几个城市的乘客可以通过分布于城市中的若干电子站牌获得一些公交车辆的运营信息以外，在其他城市，出行中的乘客无法获得任何实时信息。3.缺乏专门的交通信息发布管理机构，乘客获得的信息的准确性得不到保证。目前，我国大多数城市对于交通信息的发布没有专门的管理机构和规章制度。在服务需求量较小时尚可应付，而随着从业人员与企业的增多，城市交通信息服务变得混乱和低效，有些甚至是对乘客的误导。4.我国公交信息系统与网络的结合是低层次的。在我国一些城市出现了基于网络的公交信息服务系统，如西安公交网，中国公交查询网等，可提供一定的信息查询服务，但总体上还处于一个较低的层次，信息是静态的，

32、不能实时动态的满足需求1。 1.3研究的目的，内容及方法本文研究的目的就是针对乘客公交信息系统中的核心问题公交线路换乘问题提出一些算法，以期能够更快，更人性化的提供给乘客们公交出行方案，使得乘客能更便捷的到达目的地。本文的创新之处就在于系统的总结归纳并提出了解决公交换乘问题的各种算法，比较算法的优劣势，分析其应用场合，针对不同的场合提出不同的算法。在内容安排上，本文分为五章来叙述。本文的第一章主要是介绍一些背景知识及概况，在第二章中我们将此问题抽象成数学模型，利用图论分析，加入各种参变量，求解模型，获得各种有用结论，如最大换乘次数等。在此基础上运用算法分析的知识，对其时间复杂度，空间复杂度，N

33、P完全性等问题逐一分析。第二章主要是在数学理论上分析此问题的深层次内涵，从理论高度上统揽全局。第三章是本文的核心章节，包含了以第二章为基础而引出的各种算法。基本上以每一种算法为一小节分别加以论述。第三章将以这样几种算法为主：利用数据库在集合运算方面的优秀性能而提出的广度搜索算法(扩展集合算法)及其改进，用邻接矩阵构造换乘矩阵实现的换乘算法；人工智能方面的算法：启发式搜索算法A*算法在换乘方面的应用及其改进算法A*！算法，基于蚂蚁算法实现的公交换乘算法，基于Web GIS的算法。当然，其中还会包括一些对它们的改进算法，也会不断的对其反复比较论证。部分算法将给出伪代码的描述，并会有选择性的实现这其

34、中的一种算法，这也将作为下一章的基础。作者选择Visual C+集成开发环境实现算法，在此基础上，第四章将主要阐述公交换乘系统的具体实现方案(模块设计)及相关描述，同时叙述了用软件工程的方法将其实现的过程及其测试。第五章是全文的总结与拓展。曾经有计算机科学家定义计算机科学为研究算法的科学2。研究算法无疑是计算机科学的重要领域，也是本文的核心内容，贯穿始终。这是本文的最重要的分析方法算法设计与分析。对于本文所涉及的问题，运用组合数学中的图论的相关理论也是重要的手段。另外，在算法实现的时候，充分运用软件工程，UML的思想与方法，形成格式良好的代码和相关文档。1.4公交换乘问题及公交网络建模的概况公

35、交网络中乘客出行路径选择的问题，可以表述为在公交网络(可以抽象为一张有向图)中，乘客任意的给定两点，程序给出一套最优出行路线的方案。求解公交换乘的算法是公交线路信息系统的关键技术，也是智能公交系统与公交网络优化等问题的重要研究领域。国外对公交换乘问题的研究是伴随着公交客流分配领域的研究而发展起来的，Anderson J在1977年就提出了一种称为Volvo方法的公交路径选择算法，该算法将乘客换乘次数最少作为乘客出行路径选择的首要目标，而将不同路线的发车频率作为第二目标进行路径搜索；Spiess和FLorian于1989年提出了公交网络出行策略理论，即将两点间吸引乘客乘坐的某种线路组合称为一种出

36、行策略，以各种策略发车频率的高低作为乘客选择某种策略概率的计算依据，该方法的缺点是需要枚举所有的出行策略；Nicholas Koncz 等于1996年提出了公交网络静态多路径优化的算法，对公交网络中一次和二次换乘的问题进行了详细的描述，但该算法不能处理二次以上换乘的情况；而国外关于公交路径选择算法的最新研究成果是Gentile等于2004年提出的站点实时信息条件下的公交乘客路径选择算法。在国内，上世纪90年代后，随着一些大城市的公交信息系统的建立，国内的一些学者也开始对公交网络路径选择问题进行研究。张国伍于1992年在扩展Floyd算法的基础上，提出了公交网络多条最短路径算法；王祖祥等于199

37、3年研究了公交网络中乘客换乘次数最少的约束条件下的最短路径算法，并给出了多条路径集的生成技术；肖宏年等于1995年对公交网络中的换乘现象进行了细致的分析，并提出了以换乘次数最少为目标的换乘矩阵算法。之后国内对公交网络路径搜索算法的研究大多是对换乘矩阵算法的改进，但该类算法的缺陷是算法执行时间随着换乘次数的增加成指数式增长，一般要设置一个最大换乘次数的限制才能使用，这也是国内大多数此类系统的算法基础。杨新苗等于2000年进行了公交乘客心理调查，提出了以Dijkstra算法为基础，以换乘次数与出行距离作为双重约束的最优路径搜索算法；此外，近年来一些学者将人工智能算法启发式算法，遗传算法等引入到该类

38、问题的研究中。但从总体上来说，国内外学者在对公交出行线路问题的研究中，由于换乘现象总是得不到有效的描述，因此至今仍未出现一种既能合理的反映乘客出行公交路线选择心理特点，同时又具有很高执行效率的算法。综上所述，换乘现象能否被合理描述，是制约公交乘客出行时有效选择最优路径的关键，这一点在很大程度上依赖于对公交网络进行适当的数学拓扑模型的建立。公交网络比单纯的线路网络要复杂得多，比如其中可能存在“共线”的情况，即在两个站点之间存在多条线路并且使用同一路段的情况，这也是对公交网络建模中的难点，还有公交网是有方向性的，分“上行”，“下行”等。早期的研究者大多采用道路网络的建模方式描述公交网络，在这方面，

39、Dial(1971)，Leclercq (1972)，Sheffi Y(1985)，De Cea(1989)等完成了一些基础工作；Nguyen等人将图论中的有向超级图理论引入公交网络的研究中，提出了公交超级网络模型，该模型能够使用一个统一的数据模型同时描述公交站点，公交线路，上车弧，下车弧，换乘弧等；Anez等提出了用对偶图描述公交网络的方法，但数据冗余较大。我国对公交网络抽象建模的研究起步较晚。杨新苗等根据FTA的研究结果，结合我国的城市道路网络特点，提出了一种基于GIS的公交网络表示方法；陆忠等(2002)使用节点弧段模型对公交网络拓扑建模，并针对交叉口附近公交站点相邻的几种情况进行分类，

40、提出了相邻公交站点合并的原则；黄正东(2003)在Choi等人的研究基础上，再用动态分段技术在道路网络上标示出站点与公交线路，并针对有些公交线路上下行不重合的现象提出了有向线的概念3。 第二章 公交网络的拓扑建模网络模型的设计主要包括三个方面：软件模型设计，数学模型设计，数据库设计。软件模型主要解决网络的逻辑表现方式，数据结构和提供给上层应用的程序接口。它与具体数据结构和算法无关。数学模型主要解决的是路径搜索算法的问题，用数学的方法来抽象网络模型的特征，提供快速路径搜索的解决方案，图论给我们提供了很好的工具。应该说明的是，数学模型的建立与算法的设计是紧密相连的，本章主要论述的是数学模型的建立，

41、算法的设计将在下一章中阐述。数据存贮结构的设计是模型持久化的依据，与软件模型和数学模型都相关，它为各种算法提供了信息支持。2.1图的相关概念我们称G=(V,E)为图，如果：(1)V是一个非空的有限集合，(2)E是V中元素的无序对组成的有限集合。把V中的元素叫做图的顶点，E中的元素叫做图的边。称G=(V,E)是有向图，如果：(1)V是一个非空的有限集合，(2)E是V中元素的有序对组成的有限集合。把V中的元素叫做图的顶点，E中的元素叫做图的有向边或边。定义一：图G=(V,E)的一个顶点与边的交错序列，且边的端点为和 ，i=1,2,k,则称为一条道路(Path)，和 分别称为的起点和终点。特别的，若

42、中所有的边均不相同，则称其为简单道路。以为起点，为终点的道路称为道路。定义二：对于图G=(V,E)，构造一矩阵，其中，则称矩阵A是图G的邻接矩阵。定义三：信号流图是一种顶点与弧都具有权值的有向图。在工程系统中，特别是线性系统(线性网络)中得到广泛的应用，成为分析线性系统的一种有力工具。 信号流图的几种运算：(1)加法规则(并联法则)两个顶点间m条同向边可以用一条与它们同向的边代替，该边的增益为m个同向边的权的和。(2)乘法法则(串联法则)M+1个顶点若有边相连，则可用有向边代替，的增益为有向边的权的乘积。(3)顶点消去法则 一般的，以x为终点的有向边和以x为始点的有向边，其增益分别为和 。则可

43、将顶点x消去，得有向边： 其增益分别为： (4)反向法则 对于有向边改变为，其上的权值a变为。 (5)自环消去法则一般的，对于有m条以x为终点的有向边和自环的顶点x，如将m条有向边上的增益除以（1-环的增益），则可将自环消去，以x为起点的有向边的增益不变2。以上这些法则是进行公交网络分析与化简的重要原则，故先列举出来。2.2城市公交网络模型的建立城市公交网络包含两个最基本的元素就是线路和站点，本系统内的所有交通工具都包含这两个元素，并且具有相同的基本特征：每个站点都有若干条线路经过，经过站点的这些线路用名字唯一标识；每条线路由一系列站点组成，并按一定的次序经过这些站点，一条线路上的所有站点都可

44、以用名字唯一标识。路径搜索是建立在线路和站点的关系上的，搜索的结果应该是站点和路径的集合，表示如何乘车和怎样经过各个站点。在这个抽象层次上可以将不同种类的交通工具统一起来，将公交网络用线路和站点的集合来表示。同时，不同类型的交通工具的线路和站点也有自己的特点，像地铁、城市轻轨之类的有轨交通工具，机动性较小，速度快，准时，而且受路面条件和交通状况的影响很小，但是车次较少；轮渡是某些城市特有的交通工具，用于渡江，线路固定，速度慢，没有中间站点，这两种交通工具的行驶状况基本上可以看作是静态的，相对来说公交网络就复杂得多，而且也是城市公交系统的主要部分，下面详细分析这种网络的特点和表示方法。2.2.1

45、公交乘车模型选择公交出行，乘车方案有多个，因此，出行者要做出选择。出行者考虑的因素很多，如换乘次数，旅途时间，费用等，绝对不能简单的抽象成最短路问题，那样做是没有意义的。研究表明一般的出行者以换乘次数最少为优先考虑的目标，公交网络的设计也以减少平均换乘次数为重要目标，本文是以最小换乘次数为首要目标的。在构造此模型时，以最小途经站数为第二目标。这样，构造的公交乘车的一般模型如下所示：给定起点站和终点站，可行的公交路径集为：TR= ，表示的是在起点选择线路到达，再换乘到达，直至最终到达。换乘次数，途经总站数。出行者的目标函数：，目标函数性质： 4。 2.2.2公交网络的有向图结构一般来说，在交通枢

46、纽位置的地段会有很多公交线路经过，为了不至于在同一个站点停靠太多的汽车而阻塞交通，会在相隔不远的几个地方建立几个车站，让公交车分别停靠于不同的线路来减轻线路密集的压力，这些站点通常具有相同的名字，这些站点之间距离不远，一般认为在它们之间步行是可以接受的，这一点在搜索路径的时候尤其重要。例如，西安的南门站有东西南北四个。 A B C (在交通拥挤的路口有可能站点A，B，C名字相同)图2.1同名但不同位置的站点公交线路是比较复杂的，一般可以分为以下三类：(1)完全的双向线路。这种线路有两个端点站，在这两个端点站之间双向行车，而且两个方向上的行车路线是相同的，经过同样的站点序列和街道序列，但是线路上

47、同一个名字的站点都是分列街道的两旁，所以同一个名字对应两个在地理位置上不同站点。这种线路一般来说在两个方向上的交通状况是不同的，因为他们分别在左行线和右行线上行驶。 A1 B1 C1 D1 A2 B2 C2 D2 图2.2完全的双向线路(2)环形线路。这种线路的行车路线是单向的环形，线路内可以用名字唯一标识一个在地理位置上唯一的站点，这种线路表示起来比较简单。 图2.3环形线路(3)部分路段是单行线的线路。有些在两个端点站之间双向行车的线路，在个别比较窄或者比较拥挤的路段会实行单向行车，而在其他的路段则跟完全的双向线路一样，因此在这样的线路中两个方向上的站点序列和街道序列会有部分不同，但是总体

48、特点跟完全的双向线路类似。 A1 B1 C1 D1 A2 B2 D2 E 图2.4部分路段是单行线的线路综上所述，对于站点，并不能简单的用名字来唯一的标识，所以要引入一个正整数m来标识唯一站点，对于双行线的线路两边的同名站点是否需要区分则由地理信息数据的分辨率和具体应用的需要来决定。同样，这些因素还决定双向线路上每个方向的线路是否用不同的公交线路来表示，为了满足这种要求，公交线路也不能用名字来唯一标识，同样需要增加一个唯一的正整数ID值。另外，对于同一名字的线路上同名站点是否需要区分应该取决于同名线路是否区分方向。城市的交通状况是非常复杂多变的，整个城市公交网络是一个规模比较大的动态网络系统，

49、而公交网络的最优路径搜索本质上是一个多目标的决策问题，人们在查询的时候往往是多种情况综合考虑，其中主要的因素是乘车时间、票价和转车的次数，这些因素有些是网络的静态特性或者在比较长的时期内是静态特性，比如转车次数和票价，另一些是随着交通状况的动态变化而变化的，比如乘车时间。而定义查询条件本质上就是定义一个以这些因素为自变量的函数，这样就能够将多目标决策转化成用函数值表示的单目标决策。如果用赋权图模型来表示公共交通网络将非常直观而且很适合于最优路径搜索的问题，若能够将查询条件转换成图的边权值，则最优路径搜索就可以化为赋权图的最短路问题。由于公交线路包含多种类型，而且在公共汽车网络中，不同方向的行车

50、路线可以会有不同的行驶情况，所以应该有有向图来表示。公交网络的有向图有多种不同的表示方法，以下是几种比较合理的有向图模型是：1)令图G=(V,E)表示公交网络，V是公交站点的集合，若站点到有边当且仅当(1)到可以步行到达，或者(2)有公交线路从到，并且没有中间站点。 不允许包含中间站点 步行 (第一种情况的边) (第二种情况的边) 图2.5第一种有向图模型的边定义 2)令图G=(V,E)表示公交网络，V是公交站点的集合，若站点到有边当且仅当(1)站点到有线路直达，或者(2)存在一条道路 ，到之间有车直达并且允许从步行至，或者(3) 存在一条道路 ，到之间有车直达并且允许从步行至。 (第一种情况

51、的边) (第二种情况的边) (第三种情况的边)图2.6第二种有向图模型的边定义(允许包含中间站点)“可以步行到达” 的概念的解释：上面分析公交站点的时候提到有些站点相距很近，之所以分别设置两个站是为了分流过多的经过线路，这样的站点之间就是 “可以步行到达”的，这么处理为了让路径搜索的结果更合理，因为人们在实际乘车的时候一般情况下是不会拒绝这种步行的，而且这样有可能得到比在原地等车好得多的方案，而界定相距多少是很近则可以由具体的应用来决定，也可以动态的设置亦可以根据实际经验来静态设定5。2.2.3公交网络拓扑图中的权值的设定上述有向图的边表示的是站点之间的连接关系，而边的权值则用来量化这种关系，

52、是路径优先等级的衡量标准，上文中已经分析了人们在查询过程中所关心的各种因素。我们会碰到的各种因素是分担在各条线路之上的，假设由集合C表示。令W1=f(C)，W1就用来表示综合了C中的各种因素的每条线路上的权值。在上述有向图模型2)中的情形(1)里，C就是从到的综合因素，而在情形(2)中，由于有步行的路段，W1还应该加上以步行距离d为自变量的函数值来表示人对步行的厌恶程度及步行的时间，即W1=f(C)+g(d)。情形(3)与情形(2)类似进行计算。转车次数是一种针对站点的权值，而一般的路径搜索算法都是针对边权值的，因此有必要将转车次数转换为边权值，增加一个转车权重W2到每条边上，转车权重的折算方

53、法最终是折算成对C中每个变量的另一种赋值方案，令它的修改量的集合为，采用W1对C的量化关系f，得到最后的边权值表达式：W= W1 +W2=f(C)+f()+g(d) 式(2-1)。需要注意的是，在建立了初步的模型之后，应按照前述信号流图的几类化简法则，对公交网络进行化简， 如果图中有多条从到的平行边，则W1取其权值之和； 并且对网络进行消去与自环合并的工作，得到一个化简后的模型。如果将W1看成一般意义下的交通费用(时间和经济两方面的开销)，则这种边权值表达式可以写成“边权值=普通交通费用+转车权重”。这样做的优点是将转车次数和其它的权值统一起来考虑。而且量化了转车的影响，如果将W2设成动态配置

54、的话还可以根据查询者的不同要求来选择，这样的结果更符合实际情况，比如如果多转车可以显著减少乘车时间的话，那么这种方案应该比少转车的方案更优化。g(d)和W2的设定突出了心理作用在路径搜索中的影响，正如心理因素在经济中的影响一样，这种因素使人们在考虑方案的可行性的时候不仅仅考虑诸如时间和费用等客观条件，还会考虑主观的对旅途舒适程度的一种喜好，这种喜好可以通过量化成边权值的方式来体现。实际的公交网络应该是一个实时的动态网络，对应的有向图的边权值应该是动态变化的，其动态性主要体现在以下两个方面：(1)系统本身的动态性。由于路面的交通状况是实时变化的，所以对系统中主要的公交运行网络来说，两个站点之间的

55、行驶时间也是实时变化的，包括路口的交通信号灯、堵车、临时路面维修等情况都会影响行驶时间。(2)查询条件的动态性。不同的查询者对影响权值的各种因素的关注程度不同，这将引起所有的函数关系，如f和g等发生变化，而且还有可能需要人为的限制一些线路，比如指定要通过哪座桥或者不通过哪座桥或者避开某些堵车的路段等，另外不同的查询者可能对转车次数和其他因素之间的制约关系有不同的看法，这将影响W2的取值5。2.3公交网络性能与平均换乘次数2.3.1公共交通网的技术指标为了评价公交网络的性能优劣，必须使用一些技术指标来进行评价。主要的指标有如下几种6： (1)城市公共交通网线路密度 它的定义是公共交通线路通行的街

56、道长度与城市用地面积之比，计算公式为： （） 式(2-2) 式中： 线路网密度 L公共交通线路网长度 F城市面积 (2)公共交通线路网非直线性系数 它定义为乘客实际乘车路程与乘车起始点之间的直线距离的比。对于棋盘式街道网： 图2.7 棋盘式街道网示意图非直线性系数：； 式(2-3)对于辐射式街道网： a c 中心点 起点 终点图2.8 辐射式街道网示意图非直线性系数：； 式(2-4)对于环形街道网： R R 图2.9 环形街道网示意图非直线性系数：。 式(2-5)(3) 城市公共交通线路重复系数它定义为营业线路总长度与线路网长度之比值，在公共交通发达的城市一般为1.25至2.5之间。计算公式：

57、。(4)公共交通换乘系数换乘系数是衡量乘客的直达程度。根据客流起点与到终点流量图或主要集散点，在其间设置大站快车线，尽量减少乘客换乘。大城市不应超过1.5，中、小城市不应超过1.3。 (5)城市公共交通线路长度市区公共汽车、电车主要线路的单程长度，一般为8-10km，不超过13km，或取车辆运送时间30-40min的行程为宜；大城市的直径线路，包括郊区线路，最长不宜超过60min的行程，中小城市的郊区线路不宜超过40min的行程。线路过长会带来如下问题：行车时间较难保证，准点率下降；沿线客流不容易均匀，使平均载客量降低。(6)城市轨道交通线路的布置方式在市中心区范围，地下铁路应采用埋设式，快速

58、有轨电车宜采用埋设式或高架式；在城市边缘地区，地下铁道线可铺设在地面上，但必须全封闭，快速有轨电车宜采取地面独立路基的方式。(7)规划公共交通线路网的站点覆盖面积按300m步行半径计，不得小于城市用地的面积50%，按500m半径计算，不得小于90%。2.3.2公共交通线路网平均换乘次数的研究所谓平均换乘次数就是任何一个人从公交路网的任何一个站点到另外任何一个站点，所需要的换乘公交车的平均次数，这里包含了所有的公交线路和站点。公交网络的宏观设计指标之一平均换乘次数能够在一定程度上反映公交网络设计和实施的现状，平均换乘次数反映了公交网络的可达性。有很多的方法来求解平均换乘次数。以下考虑存在步行情况

59、下的平均换乘次数的计算方法7。本算法基于如下假设：假设一：不考虑出行者从最初出发点到达第一个公交站点的步行，假设出行者的最初出发点是整个公交网络中的一个公交站点。假设二：由专家给出一个步行换乘距离，如果两个站点距离在步行换乘距离之内时，称这两个站点为邻近站点。假设任何出行都会最大化的利用邻近站点减少换乘。假设三：假设出行者从一个站点到达它的邻近站点都选择步行，不考虑出行者通过自行车到达邻近站点或者其它交通方式到达邻近站点的影响，因为如果出行者通过自行车到达邻近站点或者其它交通方式到达邻近站点，不容易判断邻近站点的距离长度。假设四：在分析站点对之间的换乘次数时，不考虑不同路线不同车次以及不同车次

60、的发车频率的影响，只考虑网络拓扑结构对网络换乘次数的影响。假设五：在城市范围内，任意两个站点间的换乘次数小于10次，实际上对于绝大多数现代城市来说，任意两个站点间的换乘次数大于或者等于10次是不可思议的，提出本假设是为了方便下面算法的计算。基于以上的分析与假设，可以按照如下思路考虑存在步行的情况下，任何一个公交站点间的平均换乘次数：首先把公交网络转换成一个有向图，图中的顶点为公交站点，图中任意两点之间如果有边相连则代表这两个公交站点有线路相连通，边上的箭头代表了线路的方向。将所有的边都赋值，如果两个站点有公交线路连通，边的值赋1;如果两个站点步行连通距离在步行换乘距离以内，将两站点的有向边赋予