1、 摘要 摘 要 随着中国经济的发展与社会信息化水平的推进，以计算机技术为代表的信息 技术的应用已经深入到各行各业中了。公交作为国家的经济大动脉是城市的重要 组成部分，在国家经济和人民生活中发挥着重要作用并与人们的生活息息相关。 以西安市为例，全市现有线路 200 余条，站点几千个，覆盖了西安市的绝大 部分区域，公交已成为市民最重要的出行方式。在关于公交的众多问题当中，公 交换乘是人们最关心的问题。 每一个市民所熟悉的公交线路是有限的，当去一个不熟悉的地方，如何乘坐 公交车前往是市民常常遇到的问题，因此我们需要构建一个城市公交换乘系统， 当市民输入出发站点与目的站点后，该系统能够根据一定的规则，
2、例如，换乘次 数最少，路程最短，票价最低等，给出一些乘车的方案，市民按照乘车方案的文 字描述或电子地图(GIS)的直观显示，可以准确快捷的从出发点到目的地。 本文首先分析了图论及相关的背景知识，这其中包含了对公交网络进行数学 建模及对其求解平均换乘次数等。在此基础上针对市民乘车的实际问题提出了多 种不同的换乘算法，包括改进的 Dijkstra 算法，利用数据库在集合运算方面的优 秀性能而提出的扩展集合算法(广度优先搜索算法)及其改进，用邻接矩阵构造换 乘矩阵实现的换乘算法；人工智能方面的算法(启发式搜索算法)A*算法在换乘 方面的应用及其改进算法A*！算法，基于蚂蚁算法实现的公交换乘算法，基于
3、 Web GIS 的算法。 最后，在分析完上述算法并比较其优劣势后，在 Microsoft Visual C+编程 环境下实现了一种算法并对其进行分析与测试。各种测试表明，作者所开发的公 交线路查询系统完全符合理论假设并有一定实用价值。 关 键 词： 公交换乘 数学建模 Dijkstra 算法 扩展集合算法 换乘矩阵算 法 A*算法 A*！算法 蚂蚁算法 Web GIS ABSTRACT ABSTRACT With the development of chinas economic and the improvement of social information level, the ap
4、plication of information technology including 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 st
5、rong relation with peoples activity. Take XIAN 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 ever
6、y citizen are familiar with are limited. When 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 lowest price, etc, the system can give us some suggestions on bus transfer, we can get to our destinations in the
