基于最小换乘模型的公交查询系统的设计与实现*

李 俊 陈建勋 熊文龙 杜 江

(武汉科技大学计算机科学与技术学院1) 武汉 430065)(武汉理工大学计算机科学与技术学院2) 武汉 430063)(石家庄钢铁有限责任公司自动化部信息中心3) 石家庄 050031)

0 引 言

公共交通在现代都市中起着越来越重要的作用,是人们出行的首要选择.因此有必要建立一个公交查询系统为人们提供快速、方便的出行方案.

公交查询系统在电子地图上直观的显示出站点和线路的信息,并提供了起始站点间的最优出行方案,极大地方便了人们的出行.

1 系统介绍

公交查询系统在MyEclipse平台上选用MapXtreme和Java作为开发工具,My Sql作为后台数据库.除了实现了地图的放大、缩小、漫游等GIS软件的基本功能外,还能对公交信息进行三种方式的查询:公交车站查询、公交线路查询以及出行方案查询.(1)公交车站查询时系统会列出所有在该站点停靠的公交线路,并在地图上定位显示;(2)公交线路查询时系统会列出该公交线路的详细信息,并在地图上定位显示;(3)出行方案查询时输入起点和终点,系统即可查询出以最少换乘为前提,站数最少的公交出行方案,并在地图上定位显示.

为了能在地图中查询公交信息,需要在数据库中建立三个属性数据表:公交车站表、公交线路表、公交车站路线表,通过必不可少的主关键字与图形数据一一对应关联.3个表的结构如下[1].

1)公交车站表,如表1,列出城市所有的公交车站,其中站名为主关键字.

表1 公交车站表

2)公交线路表,如表2,列出城市所有的公交线路,线路名称为主关键字.

表2 公交线路表

3)公交车站路线表,如表3,用于公交出行查询,包括公交车站信息、线路信息以及出行方案查询等.

表3 公交车站路线表

2 算法分析与实现

2.1 模型抽象与问题分析

公交网络本身所具有连通性、节点性、有向性,可将其视为一连通的有向图;考虑到人们乘车的一般心理,大多数以换乘次数最少为第一目标、站数最少为第二目标[2].因其算法如下.

1)从站点入手,构造连通有向图,即把公交线路视为“边”,若两公交站点中有共同线路就相连.从中选取与换乘次数、站点个数相关的最优乘车出行方案.

2)在保证换乘次数相同的前提下经过的站点最少.

2.2 换乘矩阵

把站点视为"节点",把线路视为“边”,若两站点中有共同线路就相连,构造连通有向图,记为G(V,E).式中:V,E分别为G的节点集合和边集合.然后利用图论理论对网络换乘进行分析,建立换乘矩阵 H=(hmn),式中:m,n属于V;hmn为从节点m到节点n的最少换乘次数.

图1 一个简单的公交网络图

对图1建立初始换乘矩阵.如果任意两个站点m,n之间可以直达,则hmn=1,否则hmn=0.这样就可获得初始换乘矩阵H0(6×6).

假设公交网络有q个站点.仿照参考文献[3]提出的无向图换乘矩阵算法,结合公交网络有向图的实际,可得换乘矩阵(q×q)的算法如下.

1)初始换乘矩阵H0首先输入所有站点,如果任意两个站点m、n之间可以直达,则hmn=1,否则 hmn=0(m、n=1,2,…,q).这样就可获得初始换乘矩阵H 0.

2)一次换乘矩阵H1初始换乘矩阵H0中若hmn=1则保持不变.对于H0中的任一hmn=0,如果存在一个k(k=1,2,…,q),使得hmk=1且 hkn=1,则 hmn=2;否则保持不变.对 H0中的所有hmn进行上述运算,就可得到一次换乘矩阵H1.如果H 1中所有 hmn≠0,则停止,否则继续下一步.

3)二次换乘矩阵H2一次换乘矩阵H1中的 hmn若1≤hmn≤2则保持不变.对于 H1中的任一hmn=0,如果存在一个k,使得hmk=2且hkn=1,则hmn=3;否则保持不变.对H1中的所有的hmn进行上述运算,就可得到二次换乘矩阵H 2.如果 H2中所有hmn≠0或者H 2=H 1,则停止,否则继续下一步.

4)n次换乘矩阵H n 假设已得到n-1次换乘矩阵 H n-1,H n-1中的hmn若 1≤hmn≤n-1则保持不变.如果H n-1中的任一hmn=0,如果存在一个 k,使得hmn=n且hkn=1,则hmn=n+1;否则hmn=0保持不变.对H n中的所有的hmn进行上述运算,就可得到n次换乘矩阵H n.H n中所有hmn≠0或者Hn=Hn-1,则停止,否则继续下一步.

为了便于对换乘次数理解,需要特别说明的是:0表示所对应的2站点不能连通,非0元素减1表示2站点间实际的换乘次数.

3次换乘矩阵为

即为根据算法得到的最终换乘矩阵.也就是说图1代表的公交网络经过3次矩阵运算就可以得到最终的换乘矩阵.在解决了换乘次数问题之后,下面的算法就是解决在换乘次数相等的条件下站点数目的问题.

2.3 站点最少算法

对 H 3而言,

对任意2个站点m与n,分别选出所有经过站点m及站点n的线路,其中经过站点m的所有线路集合记为Lm,经过站点n的所有线路集合记为L n.

2.3.1 直达车算法

若hmn=1,此时表示从m到n有直达车.对任意Li∈Lm∩Ln,若此时m,n在这条线路中的位置分别为im,in,则经过的站点为Cnm=|inim|.这样的Li有r条,则统计 r个Cnm.

2.3.2 一次换乘算法

若hmn=2,此时必须转一次车才可以到达终点.对任意的 k∈﹛1,2,…,q﹜∧(k≠m)∧(k≠n),若存在这样的k,使得 hmk=1且hkn=1,那么找出同时经过站点m,k的线路集合L mk(r 1条),同时经过站点k,n的线路集合Lkn(r2条).按照直达车算法分别算出r 1条站点m,k间的站数Ckm,r2条站点k,n间的站数Cnk.

m,n间总站数Cnm=Cnk+Ckm,统计 Cnm的值(最多个数为r1×r2).

2.3.3 n(n≥2)次换乘算法

若hmn=n+1,此时必须转n次车才可以到达终点.对任意的 k∈﹛1,2,…,q﹜∧(k≠m)∧(k≠n),若存在这样的k,使得 hmk=n且hkn=1(hmk=1且hkn=n类似),那么找出同时经过站点m,k的线路集合Lmk(r1条),同时经过站点k,n的线路集合L kn(r 2条).按照n-1次换乘算法算出r1条站点m、k间的站数Ckm,按照直达车算法算出r2条站点k、n间的站数Cnk.

m,n间总站数Cnm=Cnk+Ckm,统计 Cnm的值(最多个数为r1×r2).同法可以算出hmk=1且hkn=n时m,n间总站数Cnm,统计若干个Cnm的值.

在换乘次数相同的前提下,求出集合Cnm中最小的N个,则这N个结果对应的N种线路组合便是站数较短的线路.

2.4 算法分析

把所有公交站点当成节点,然后构造换乘矩阵,矩阵规模比较庞大.当然,复杂的公交网络可能要经过更多次矩阵运算才能终止.但是在实际中,两站点经过太多次换乘到达也没有实际意义,所以可以人为定义最高换乘次数(比如2或者3).这样就极大减少了运算时间.

换乘矩阵运算一次后,以后查询路径不需要重新计算,以一次的计算代价来换取以后查询的高速度.

得到换乘矩阵之后,可以比较方便的进行站点个数计算.以一次换乘算法为例,hmn=2即可确定一次换乘.从换乘矩阵的指定元素得到线路,从线路上得到站点间个数.而文献[4]则需要从起始站点得到经过该站点所有线路集合,再从线路集合中每个站点出发,找到包含任一站点的线路集合,再与经过终点站的线路集合比较,两个集合有交集才能确定一次换乘.

3 系统实现

以公交线路信息查询和出行方案查询为例来展示系统实现的功能.

3.1 公交线路信息查询

如图2在“线路查询”中,输入要查询的线路名称,点击“查询”,左边列表框会出现该线路的所有站点,及收发班时间、票价等基本信息,右边地图上会定位并显示该线路.

图2 公交线路信息查询

3.2 出行方案查询

输入“起点”和“终点”站的名称,然后点击“查询”,左边列表框会出现推荐的出行方案信息,右边地图上会定位并显示该出行方案.方案一如图3,方案二如图4,在2个方案都有一次换乘的前提下,方案一只有5站路,比方案二8站路要好.

4 结束语

论文设计了以最小换乘为前提,以站数最少为次要条件的最优路线出行方案.该方案首先得到站站之间换乘次数矩阵,然后利用该矩阵非常方便计算出站点间经过的站点个数.

图3 出行方案查询(方案一)

图4 出行方案查询(方案二)

当然,系统可以进一步完善,主要体现在:(1)初始换乘矩阵可以进一步精简,算法可以进一步完善[5];(2)在换乘次数相等的条件下,还有时间、票价等因素影响人们的乘车习惯.要考虑到这些因素;(3)结合无线网络技术,为无线网络终端用户(如3G手机用户)提供地图搜索和导航服务.

[1]李玉芝.基于组件式GIS的城市公交查询系统的设计与实现[D].昆明:昆明理工大学国土资源工程学院.2006.

[2]张存保,李 华,严新平.基于Web GIS的城市公交问路系统[J].武汉理工大学学报:交通科学与工程版,2004,28(1):99-102.

[3]张林峰,范炳全,吕智林.公交网络换乘矩阵的分析与算法[J].系统工程,2003,21(6):92-96.

[4]李 响,张睿智.公交查询系统的数学模型[J].黑龙江大学学报:自然科学版,2008,25(4):554-557.

[5] Bi Yong,Hu Hongping.Mathematical model of best-path planning algorithms for public transportation systems[C]//2010 International Conference on Computer Application and System Modeling(ICCASM 2010),2010,13:345-348.