一种基于集合信息论的公共交通线路搜索方法

摘 要：通过创建启发式搜索方法，利用公共交通站点线路集合，将各站点包含的特定信息集合经过运算，形成新的集合，同时根据在运算过程中产生的新信息再分析计算，从而得到最佳路线。使用PHP及MySql数据库综合编程实现该模型算法，并以通过实际数据进行仿真实现说明方法的可靠性和有效性。

1 引言

随着我国城市化的发展，市民对方便出行需求的迫切愿望与都市交通日益拥堵的现状形成强烈反差。为此各地纷纷建立立体公共交通系统来应对这一问题。但是，在复杂公共交通系统下，如何快速寻找到一条经济、合理、方便的最优乘车路线或换乘方案，又成为困扰城市居民和外地旅客的新问题。

为此，笔者思考设计一种公共交通信息系统，通过该系统公众可以方便的选择出行路线以及方式。该系统的核心就是构建“最佳路径”算法。由于算法服务对象是信息系统，而计算机系统最喜欢抽象的数据，这样应用集合论比应用形象线路图的图论来解决问题更方便直接。

设计中笔者利用集合的逐步向外扩展、两个集合之间逐渐逼近的搜索方法, 在一个庞大的无向交通网络中, 寻找出一条最佳路径的算法。该算法对图的搜索方法提出了一个新的思路, 并更容易在计算机上实现。

2 问题分析及模型建立

在构建模型的过程中笔者主要从三个方面进行了思考。首先，仅从公交线路方面考虑，如何给出任意两公共汽车站点之间线路选择问题的一般数学模型与算法；其次，若同时考虑公汽与地铁线路，如何进行有效选择；最后，假设知道所有站点之间的步行时间，如何建立任意两站点之间线路选择问题的数学模型。

2.1 问题一分析及模型

对于第一个问题，先根据直接到达，换一次车，换两次车把能够从一个目的地到达另处一个目的地的所有路线求出来，又此问题是一个多日标大规化问题，可根据出行耗时第一原则，建立一个所花时间最短的数学模型，再根据出行费用第二的原则，建立一个出行费用最少的数学模型。在求从一个目的地到另一个目的地时， 假设乘客从A站乘公交车去B站，首先，看A站是否有公交车直接到B站。如果有一条或多条直达公交线路，则从中选择线路距离最短的公交车，如（图1.1）。如果没有，则看经过A站的公交车和经过B站的公交车有没有交叉点，若有交叉点C，则选择在交叉点C转车到达B站，如（图1.2）。如果经过A站的公交车和经过B站的公交车没有交叉点，则先乘经过A站的某一路公交车到达某一站C，看经过C站的公交车与经过B站的公交车有没有交叉点D，若有，则在D站转车到达B站，如（图1.3）。另外，有可能存在多种两次换乘的方案，如（图1.4）所示。此时，需要判断哪种方案距离最短，然后选择距离最短方案。如果经过C站的公交车与经过B站的公交车没有交叉点，说明经过两次换乘还不能从A站到达B站。

站点与线路的集合模型

目标函数

其中，

若 不全满足以上约束条件则取。

为站点线路总集，他包括所有公交线路和站点。

:所有公交线路集；

:第路车行经的所有站点集；

:起始站点集，包含所有经过的公交线路；

:终点站点集，包含所有经过的公交线路；

:线路相交矩阵；

2.2 问题二分析及模型

笔者假设在问题一的基础上增加两条地铁线，这样就可以把这两条地铁线及所有的地铁站点像公交车线路及公交车站点一样来处理，便于统一运算。也是容易让计算机统一处理，唯一不同的是地铁的站是公交站的集合，把地铁可以经过的公交车站统一作为地铁的站集合如（图2）。而一个地铁站附近的车站共用一个站号。可见公交汽车每个站的编号是唯一的，而地铁拥有的站可以有相同编号的若干个站。

若模型一中即为

时，则扩展与，具体实现如下:

将所有通过的线路上的站点记为，将过但不过的线路记为，则不仅过还过其它的站点记为；

同理可对进行扩展，即将所有通过的线路上的站点记为，过但不过的线路记为，则不仅过还过其它的站点记为，如图4.2。

3 模型求解

3.1模型一求解

（1）当即

时，

根据相交矩阵可以判定与，是否有交点，有则找到通路；

选择线路为：，转乘1次，此时，可以从终点回溯，取出其换乘路径，如（图5.2）；

特别地，时，即在同一条线路上时，如（图5.1）;

选择线路为：，转乘0次，两站可直达；

(2)若，则扩展与；

3.2 模型二求解

（1) 当即

时，

选择线路为：

，转乘3次，如(图4.2)；

特别地

，时，即在同一条线路上时，如(图4.1)

选择线路为：

，转乘2次；

根据相交矩阵可以判定与，是否有交点，有则找到通路；

此时，可以从终点回溯，取出其换乘路径；

（2）当即

时，

则集合再次对自身进行回调扩展，方法同与。

3.3模型三求解

通过前面步骤 在最少换乘算法求出了，换乘2次（含2次）以下的所有可达路线。

4 模拟仿真

为检验该方法的实用性，在设计完成后，笔者在系统中录入520条公交线路信息，两条地铁线路信息。假设要搜寻站点s3359到站点s1828的乘车方式，首先如图7在输入页面键入相关站点。

让后点击查询得到如图8的查询结果

按照这种程序，通过系统验证了以下几条路径

5 结束语

该模型是通过集合扩展来逐步逼近求交集，来求得满足条件的结果。在假设至多两次转乘的情况下，求得的结果。比如有人对系统要求得到时间最省的线路，有可能该算法给出的不是真正的最少。该模型和算法可能得到的仅仅是一个局部最优解，但是针对要求给系统开发提供算法和模型是相当完美的，因为要获得全局的最优，那样只会加大系统运算开销。而且该模型抽象程度高，便于计算机运行，代码实现十分容易。再者，对模型和算法来讲，可以通过增加和删除集合，来适应现代城市每日都在改变的公共交通环境。比如在系统对公交线路选取最佳线路的时候，可以通过集合其他信息系统的信息来进行路径选择。在有一条线经过一个交通拥挤的小片区时，系统得到这个信息后，可以适当减少相应站点集合，系统自动过滤掉该线路。特别的是，当城市临时加开公交线路时，该模型只需要增加相应集合，即可增加新路径的选择。

参考文献

[1]严蔚敏,吴伟民.数据结构[M].第2版.北京:清华大学出版社,188页～193页,1992.

[2]傅冬绵.交通问路系统中最短路径的新算法[J] 华侨大学学报(自然科学版) ,22卷,第2期,139页～142页,2001.4

[3]曾国荪.南昌市公交线路优化方法[J].江西师范大学学报,23卷第1期:53页～ 56页1999.5.

作者简介：曾维，四川绵阳人，男，成都理工大学信息科技与技术学院,讲师，研究方向是电子材料和电子技术.