基于乘客终端的公交查询系统设计

赵静

摘 要： 城市道路基础建设规模扩大的同时，道路的延伸后，随之满足人民需要的公共交通线路也在不断地增加。本文通过研究了公交换乘理论及换乘算法，从乘客终端角度设计公交查询系统，主要实现的是查询功能，包括线路、站点查询和换乘查询。并实现了多种换乘查询方式，分别从换乘次数最少和最短路径两种方式得出不同换乘查询结果，以满足不同需求用户的使用。

关键词：换乘系统 查询 换乘次数最少 最短路径

中图分类号：TP311 文献标识码：A 文章编号：1003-9082（2016）06-0007-02

一、前言

随着我国社会经济的发展，城市化进程逐渐加快，人民出行频率不断增加，道路交通容量日趋饱和，交通问题日益突出。而城市公共交通具有运量大、人均占有道路少等优点。城市公共交通的发展趋势为对快速性、舒适性、便捷性、环保等方面的要求。

先进的信息技术也促进了公共交通技术的发展，公交换乘系统是城市公共交通系统的一个子系统，发挥着比较关键的作用。为市民提供便捷的查询系统，逐渐满足市民出行多样化的交通需求，方便地提供给人们出行时选择最优的公交换乘方案，从而降低了乘客出行成本，改善了人们的出行状况。对于推动公共交通事业发展，提高公交服务水平具有一定的积极意义。

二、公交换乘理论

交通换乘行为是指出行者从某起始地到目的地的出行过程中，需要经过同种交通方式或者不同交通方式搭乘转换的全过程。而公交换乘系统正是提供的这种交通服务的必备手段。

研究换乘方式其实就是为了在地理网络中选出一个最优路径。在交通出行过程中，最优路径是从某种优化条件出发，依据搜索算法而得出的优化路线。

在本系統设计中，为实现系统换乘查询模块的功能，主要提供两种换乘查询方式。一种是基于最短路径的换乘查询方式，另一种是基于换乘次数最少的换乘查询方式。

1.基于最短路径的公交换乘算法

在本系统设计中，为实现系统换乘查询模块的功能，主要提供两种换乘查询方式。最短路径是指在换乘行为过程中距离最短，经典算法为Dijkstra （迪杰斯特拉） 算法。Dijkstra算法主要用于搜索某一个节点到路网其他所有节点的最短路径。该算法的优点是单源搜索最短，仅考虑起点站和终点站之间的最短距离，而不考虑其他节点。算法简洁，查询效率较高。搜索结束后自动立即终止。但是Dijkstra算法的缺陷是：只考虑距离上的最优解，这种求解过程导致了频繁换乘，因此给用户带来了不便和相应交通费用增加。

Dijkstra [2]算法的基本思想是：先设置起始点集合U，取属于集合U中的一个顶点，令其从源到该顶点的最短路径长度已知。初始时，U中仅含有源点。设U是G的某一个顶点，把从源点到u且中间只经过U中顶点的路径称为从到源点u的特殊路径，该路径记录在Path中，路径长度记录在数组dist中。Dijkstra算法每次从V-U中取出具有最短特殊路径长度的顶点u，将u添加到U中，同时对数组dist中进行必要的修改，相应地，修改Path。算法结束时，Dist中记录了源点到其它各点的最短路径的长度，Path中记录相应的路径，算法过程如下[2]：

假设G=（V，E）用邻接矩阵d来表示，d[i][j]表示边（vi，vj）上的权值，若（vi，vj）不存在，则置d[i][j]为∞。

（1）初始设置：U={v0}，Path[i][j]=“v0vi”，最短路径长度的初值为：Dist[i]=d[v0][vj] vi∈V-U；

（2）选择u=vj，使得Dist[vj]=Min{Dist[i]/vi∈V-U}，则vj就是当前求得的一条从v0出发的最短路径的终点。令U=U∪{j}；

（3）修改从v0出发到V-S集合上任意顶点vk得到的最短路径长度。如果：Dist[j]+d[j][k]

（4）重复操作（2）和（3），直到求得所有最短路。

算法求得从v0到图上其余各顶点的最短路径是依路径长度递增的序列。在公交线路查询时，查询起始站点为源点依次生成源点到其它各点的最短路径，在此过程中，若查询终点站点出现，则算法结束，即求得最短路径及长度。

在公交查询系统中，应用Dijkstra算法求解最短路径，在数据处理上存在一定的困难，由于一个大中型城市的公交线路多达上百条，而每一条线路的公交站点数十个，因此，如果求每一个站点的最短距离会大大地增加时间复杂度，是不科学的，直接导致搜索效率降低。根据前面章节的分析，城市公交发展的一个方面是建立良好的换乘枢纽，因此，节点的选择主要设置为换乘频繁，客流较多的换乘站。

在实际交通查询中应用最短路径算法策略时，检索的起点和终不完全在交叉点上。由于Dijkstra算法主要应用于路网节点，而实际换乘点又不在网络节点上，解决方法是可以在路网上设置虚拟节点，选择位置为距离交叉点较近处为宜，如图2-1所示。

为了统一应用Dijkstra算法求最短路径，针对虚拟结点，应修改邻接矩阵，然后运用Dijkstra算法求解。算法过程如下：

（1）如果要查询的站点刚好位于路网的交叉点处，则将虚拟结点标识设置为False，并转到步骤（3）；

（2）在交叉结点表中，加入虚拟结点，在邻接矩阵中增加行和列，填入相应的权；

（3）应用Dijkstra算法，所示求解出最短路径；

（4）若虚拟结点标识为False，算法结束，否则，还原交叉结点表及邻接矩阵。

由于电子地图定位节点的问题，VB在软件设计实现过程中采用的方法是先用输入起始站和目的地站的站名后，搜索出线路，然后得出时间，接着考人工判断并进行对有路径的判断，同样，在最短路径方面也是一样，通过搜索出的线路，然后从数据库里调出时间，然后也通过人工判断，最终也得出最有路径。

2.基于换乘次数最少的最优路径方法

基于上面距离最短的换乘方式，人们考虑更多的是减少换乘次数，避免换乘频繁带来的麻烦。因此，换乘理论中，基于换乘次数最少的方式，与实际换乘系统的应用联系更为紧密。

基于换乘次数最少的换乘算法的算法思想核心是，根据调查显示，出行者出行时对于公交线路的选择时，多数优先考虑是否有直达车。如果没有直达车，则考虑一次换乘的方案，然后考虑中间站的位置。如果没有一次换乘的方案，则考虑多次换乘。基于换乘次数最少的换乘该算法的基本思想：如果确定起始站点Q、终点站Z出发，与数据库中各个线路中的站点相比较，寻找可换乘车站，得出可能的路径。

设S（I）（I=1，2，…，m）为经过起始站Q的线路集合。

T（J）（J=1，2，…，p）为线路S（I）上的所有站点的集合。

F（J，V）（V=1，2，…，g）为线路T（J）上的所有站点集合。

R（K）（K=1，2，…，g）为经过站点E（I，U）的线路集合。

Y（O）（O=1，2，…Z）为经过F（J，V）的线路集合。

G（K，W）（W=1，2，…i）为线路R（K）上的站点集合。

算法的步骤如下：

（1）根据出行目的，确定起始站Q，和终点站Z；

（2）分别求经过起始站Q的所有线路集S（I），以及经过终点站Z的所有线路集T（J）；

（3）经过判断条件S（I）与 T（J）是否相等。如果相等，即存在直达线路，输出结果T（J）；如果没有则下一步。

（4）求线路S（I）上的站点E（I，U）以及线路T（J）上的站点F（J，V）；

（5）通过模糊查询，判断是否存在某一区域相同但是站点名称不同的站点；或者某一区域距离较近，短距离步行即可到达的站点。也就是要判断E（I，U）= F（J，V），即得出一次换乘的一条路径S（I），T（J）， 其中E（I，U）是中转站点。

（6）分别求经过E（I，U）的线路集R（K），和经过F（J，V）的线路集Y（O）；

（7）经过判断条件R（K）= Y（O）是否相等。如果相等，则得出两次换乘的一条可行路径S（I）， R（K），T（J），经过的中间换乘站点为E（I，U）和F（J，V），输出结果，结束运算。

依据哈尔滨市公交管理部門现有公交线路及现有站点的基本数据，哈尔滨市的公交线路可达性较强，最多情况下换乘2次即可到达出行目的地，因此，在本设计中，仅研究换乘两次的换乘查询形式。

算法的流程为：输入起始站点和终点站，判断数据库中各线路是否经过这两点，即是否可以直达。如果不存在直达线路，会继续搜索经过中间换乘车站，实现换乘1次到达终点站的所有路径。如果直达、换乘1次都不存在，算法会将换乘次数修改为2，实现经过2个中间换乘站到达终点站的所有路径。如果直达、换乘1次、换乘2次，都没有搜索到从起始站到终点站的路径，那么系统会给出查询失败的提示。搜索换乘次数的流程图如图2-2所示。

三、公交换乘系统设计

1.系统设计目标与流程

系统设计目标是建成一个方便、实用、稳定、安全的公交查询及换乘系统。从功能角度，不仅能够为公交管理部门提供详实、准确的管理系统，而且还能够为出行者提供最新的公交查询信息以及合理的换乘路线方案。系统的建设，同时要满足这两个方面的需求，起到公交管理与出行者的沟通服务的桥梁作用。

公交换乘查询系统的设计与建立，主要能够服务于全体城市公共交通出行者，帮助出行者提供准确、安全、可靠以及最优的出行信息，从而吸引哈尔滨公共交通出行，减少拥堵，节能减排。

2.系统功能设计

城市公交查询系统能够帮助出行快速地选择出行路径、换乘路线等，既提升了出行者得效率，又优化了公交资源的配置，提高了交通运输的效率和城市的信息服务水平。目前，国内对交通查询系统进行的研究已经有很多，本设计实现了一个通用的，能够进行基于换乘次数最少、基于最短路径、站点起终点的查询。系统各功能模块设计结构图如图3-2所示。

四、公交换乘系统实现

信息查询模块主要包括线路查询与站点查询两个子模块。用户可以根据出行需要，可以查询某条公交线路，也可以按某一个公交站点查询经过的线路。

选择“换乘查询”菜单项，界面主要开始进行路线搜寻，按换乘次数最少查询，或者选择距离最短查询。其优点可提供：

（1）站点名称模糊化查询；

（2）换乘查询方式的多样化查询；

（3）换乘中间站查询；

（4）线路推优方案。

五、结论

本文所研究的算法具有通用性，可移植性强，设计的系统应用简单便捷，方便出行乘客使用，并能够为用户提供最佳出现路线，从而降低了乘客出行成本，改善了人们的出行状况。

参考文献

[1]龚翱.改进的城市公交查询算法研究[J].湖南大学计算机应用技术，2008年6月.

[2]王建聪，高利平，陈绍宽，何宇强.城市公共交通枢纽换乘组织仿真研究[J].第6卷第6期，2006.

[3]林徐勋.多方式换乘动态路径选择建模研究[N].上海交通大学2009年.