P2P在公交查询中的应用

摘 要 公交线路查询问题在公共交通中是一个重要的问题。针对以往的公交换乘算法，提出了一种以站点信息为中心的建模方法，该模型采用P2P思想中端到端对等通信的方式优化查询，可以实现换乘4次的优化线路， 并用VC++实现了该算法。通过对公交网络的实际计算，结果表明该算法不但可以提供更好的线路，而且还能适应公交系统动态性的需求，因此算法具有很强的实用性和通用性，在公交网络中可以广泛采用。

关键词 公交换乘 站点信息 P2P 动态性

从实际出发，结合公众出行心理，公汽线路选择应优先考虑两站点之间是否有直达车，若有，则直接输出直达车辆，若无，再搜索换乘路线。从查询系统设计角度考虑，当输入起始点后，系统内部通过查询应自动搜寻换乘次数最少的路线，若换乘次数相同时有多种转乘方案，则系统应显示所有转乘路线方案（包括转乘次数、行程总时间，途径总站点数，转乘站点及路线，是否始发，行程总费用，转承站点负载压力）以供查询者自主选择。文献[1]和文献[2]都是采用邻接矩阵的算法，他们都可以提供多大4次换乘的最优路线。但基于邻接矩阵的模型不能满足客户对于线路动态信息的需求，以及物联网[3]业务实现的可能性。文章提出了以站点信息为中心的建模思想，每个站点作为独立的个体，并通过站点之间的交互搜索（P2P[4]）查询线路。该系统无论对于本地建模还是站点信息网际互联都有很好的适用性。

1 数据处理-三种公交线路抽象处理

公交线路分三种，下面将这三种线路进行数据处理：

（1）下行线、上行线原路返回

这种线路有两个端点站，在两个端点之间双向行车，而且两个方向上的行车品种线相同，经过同样的站点序列。由于线路的方向不同，因此，下行线和上行线可以抽象成两条线路处理。

（2）线路为环行线

实际中环形路线一般是双环，但在这两条线路进行抽象时，为保证任意两站点距离最近，把每条线路再抽象成2条：

（3）下行线与上行线经过站点不同

由于下行线与上行线经过站点不同，显然，该种线路需要抽象成两条线路处理。

2 P2P优化查询算法

2.1 符号说明

S：起始站

D：终点站

Sl：站点S的线路集合

Dl：站点D的线路集合

Sls：经过S可直达的站点集合

Dls：可直达D的站点集合

2.2 集合表示

在文献[5]中提出了公交换乘上确界的概念，即任选一站点最多可经过几次换乘可以到达整个网络的其他任一站点。这里给出了上确界值为4的集合表示方式：

（1）直达的集合表示：

2.3 算法分析

该公交查询系统的效率取决于Sls、Dls及Tls的大小，假设Sls、Dls平均大小为d，则直达查询和1次换乘查询的时间复杂度为O（l）。2次和3次换乘的时间复杂度为O（d2）。4次换乘的时间复杂度为O（d4）。系统设计中由起始站、终点站引出相关站点，逐步扩大搜索范围，这使得搜索量大大减少，同时也提高了计算速度。

3 算法的实现与应用

利用该算法对某公交系统进行计算，线路信息来源于2007年高教社杯全国大学生数学建模大赛B题[6]：乘公交，看奥运。该公交网络巨大，共有3957个站点513条线路。下面以2007CUMCM高社杯特等奖论文获得的公交线路信息，通过Visual C++编程，得出该算法的换乘方案，并将结果进行比较，见表1。

从表1结果来看，从S3359S1828，该算法给出了所有换乘1次的查询结果。可以根据用户不同的需求提供更好的选择。

4 结束语

文章提出的以站点信息为中心的建模思想，每个站点作为独立的个体，并通过站点之间的交互搜索查询线路，在有效的公交换乘上确界内能够快速的找到更多条可达路径。公交系统中需要考虑的其它因素有很多，比如换乘次数、路径距离、乘车时间等。设计一个符合实际需求的评价标准，选择最优化的路径将是一下步工作的重点。另外随着物联网业务的发展，智慧地球的概念更深入人心。把站点作为研究对象，能够把更多的影响因素引入到公交系统中，如路况实时信息、道路信息、公交车行驶信息等， 更有利于推动物联网业务的发展。