您的当前位置：首页公交线路查询系统算法设计与实现

公交线路查询系统算法设计与实现

来源：筏尚旅游网

第21卷第3期2008年6月Vol.21No.3

　　　JournalofHigherCorrespondenceEducation(NaturalSciences)　　　June2008

高等函授学报(自然科学版)

・大学生园地・

公交线路查询系统算法设计与实现

陈文磊1,肖俊超1,董　勐2

(1.华中师范大学数学与统计学学院;2.计算机科学系,武汉430079)

　　摘　要:本文针对公交线路查询系统的可优化方面,就查询者不同需求下最佳路线的选择问题进行了研究,着重探讨了出行线路需换乘情况的查询及计算实现,并建立了一个较完善的线路查询系统。关键词:公交网络;直达矩阵;换乘

中图分类号:O242.1　　文献标识码:A　　文章编号:1006-7353(2008)03-0049-03

1　引言

目前,已经有较多关于公交查询系统算法的研究及实现文献,人们从不同角度运用不同方法解决了线路查询的问题,但仍存在部分考虑不周全的地方。如文献[2]从数据库的角度完成系统的构建,但却忽略了对乘客采用步行或地铁等多种出行方式下线路选择的考虑;文献[3]运用了GIS技术及换乘矩阵处理方法,使得系统稳定性和可塑性更强,但对整体出行过程分析不够深入;文献[4]对系统平台开发进行了探究,但针对换乘3次及以上的情况未能给出一个通用的算法等。

因此,我们围绕公交网络及乘客的整体出行过程进行了研究;针对换乘多次、出行方式多样的情况利用直达矩阵的概念给出了一个通用算法;并在最后完成了公交线路查询系统的研发及实现,并使之具有较好的通用性和可塑性。

图1　公交线路网络示例

线路Ld,d∈{1,2,…,k+1}或其部分构成的。因此乘客出行总时间T(票价P)也转化为这k+1条线路对应时间

(票价)之和。我们以总时间最短的原则为例,对出行路径

进行优化选择。

2.2直达矩阵

对于任两站点Si,Sj,如果存在线路Ld均经过这两点,我们就称这两点是可相互直达的,否则不可直达。为了研究问题方便,不妨设Si的可直达站点集合为Ui。

显然满足同时经过Si,Sj条件的线路可能不止一条,

而每一条线路Si→Sj所需时间tS也各不相同。根据线路ij

2　系统构建2.1公交网络

整个城市的公交网络就是一个二维拓扑空间,由多段线路连接而成。每一线路都可以看成一条有向线段,线路中站点对应着是线上的点。根据交通部门掌握的城市公交线路L、途径站点S以及每条线路通过相邻两站点所需时间t等数据,我们对整个城市的线路、站点进行了标记。

其中线路为Ld,d=1,2,…,m,m为城市开通的公交线路总数;站点为Si,i=1,2,…n,n为站点总数。而换乘站点即为网络中任两条有向线的交点Sr,r∈{1,2,…n}。

事实上,对于从起点Si到终点Sj经过换乘k次(换乘站点分别设为Sru,u=1,2,…,k)的出行路径,可以看成是由分别途径Si→Sr1,Sr1→Sr2,…,Srk→Sj的k+1条

选择原则,我们遍历所有这样的线路并选取Si→Sj所需时间最少的那条线路Lij,则称Lij为Si,Sj间的直达线路,花费时间tSij为Si,Sj间的直达时间。

根据之前的分析,对于两点Si,Sj间换乘k次的情况,出行路径即由k+1条直达线路构成,而k个换乘站点Srh,

h=1,2,…,k即为路径中k+1条直达线路交点。满足Si

→Sr1,Sr1→Sr2,…,Srk→Sj均可直达,即:Si∈Ur1,Sr1∈Ui,…,Sj∈Urk,Srk∈Uj。因此寻求其所需最短时间及

收稿日期:2008-01-17.

基金项目:湖北省自然科学基金面上项目,课题编号:2007ABA337.

作者简介:陈文磊(1987-),男,福州人,2005级数学与应用数学专业在校生.

第21卷第3期2008年6月Vol.21No.3

　　　JournalofHigherCorrespondenceEducation(NaturalSciences)　　　June2008

+…tSrj}及最小值

高等函授学报(自然科学版)

对应路径就转化为求min{tSir+tSr

1r2

对应路径。

由于我们的路径计算均建立在直达线路、直达时间数据上,为了提高系统查询速度,我们将所有站点间n×n个直达时间与对应n×n条直达线路以及所有站点的直达站点集合全部计算出来并采用矩阵(即二维数组)形式将其固化储存。

直达时间矩阵:

tStS

…tS…tS

21222n

……tS

…tS…nnn×n直达线路矩阵:LSLS

LSLS

…LS…LS

21222n

……LS

…LS

…nn

n×n

直达站点矩阵:

U1U2

图2　直达时间、线路矩阵生成算法流程

3　算法实现

首先把已得的直达时间、线路矩阵和直达站点矩阵数

n×n

…Un

据存放到文件中,称为固化数据。每次启动系统时,先从文件中读取数据,然后再进行以下的运算:

其中若站点Si,Sj不可直达,则矩阵中对应(i,j)元值为

0.实际生活中随着交通的不断发展,公交网络添加了更多不

3.1输入起终点Si,Sj

判断zhida[i][j]是否为0,若为0则显示“无直达线路”,

否则输出直达线路与直达时间

zhida[i][j]、line[i][j];

同的交通出行方式(如地铁)。但是由于整个公交系统是建立在该二维线路网络上,其他交通出行方式的本质就是使某些站点间不可直达的情况转变成可直达的情形。因此通过不断更新直达矩阵数据,就可使上述算法依然适用。

直达时间、线路矩阵生成算法

建立二维数组zhida[n][n],line[m][m]分别用于存储数据tSij,LSij。其中Si:=起点;Sj:=终点;

zhida[i][j]:=tSij;line[i][j]:=LSij。

3.2计算换乘一次情况

(1)遍历直达站点矩阵第i,j行,若Ui∩Uj≠<,即

ϖSr1,r1=1,2,…,r使Sr1∈Ui且Sr1∈Uj,则依次计算

zhida[i][r1]+zhida[r1][j],转入2.2;否则Si,Sj不可一

次换乘到达,转入3;

(2)比较zhida[i][r1]+zhida[r1][j],r=1,2,…,r,并取其最小值min=zhida[i][r1]+zhida[r1][j]为最

如图2,我们建立了直达时间、线路矩阵生成算法的流程图。

直达站点矩阵生成算法:

(1)初始化d=1,i=1,j=1;

(2)遍历d=1到d=m,若存在d使得Si,Sj均在线

短时间,且输出对应经过Si,Sr1,Sr1,Sj的公交线路及换乘站点Sr1;

3.3计算换乘二次情况

(1)遍历直达站点矩阵第i行,对于Ui中任意一点Sr1,若Sr1的直达站点集合Ur1中存在Sr2使得Sr2∈Uj,

路Ld上,则将Si加入Uj,Sj加入Ui中,否则进入3;

(3)i++,返回2,若i>n则进入4;

(4)j++,i=1。返回2,若j>n则算法终止;这里算

则依次计算zhida[i][r1]+zhida[r1][r2]+zhida[r2][j]

,转入3.2;否则Si,Sj不可二次换乘到达,转入4;

法复杂度为O(n)。

第21卷第3期2008年6月

(2)

Vol.21No.3

　　　JournalofHigherCorrespondenceEducation(NaturalSciences)　　　June2008

zhida[i][r1]

zhida[r1][r2]

高等函授学报(自然科学版)

比较

5　结束语

本系统主要针对总时间最短情况进行综合分析,以直达矩阵为切入点完成查询系统的实现。但在用户需求多样性、算法中数据占用存储空间压缩、运算速度提高、GIS系统的引进、系统安全性稳定性开发等方面有待进一步改进和优化。

参考文献

[1]姜启源,谢金星,叶俊.数学模型(第三版)[M].北京:

zhida[r2][j],并取其最小值为最短二次换乘时间,且输

出对应经过Si、Sr1,Sr1、Sr2,Sr2、Sj的公交线路及换乘站点Sr1,Sr2;

3.4计算换乘三次情况

与换乘一次、二次的算法类似;换乘至k次的情况也可依此计算得到。其中算法复杂度为O(nk)。

据调查,一般乘客可接受公交换乘次数最大为3次,因此从出行舒适度的角度考虑,公交查询系统构建到达3次换乘即可。

高等教育出版社,2005.

[2]舒靖.城市公交查询系统设计[J].科技信息,

2007(10):14215.

[3]李玉芝,方源敏.城市公交查询系统的设计与实现

[J].地矿测绘,2006,22(1):325.

[4]刘伯红.基于GEOManiaGDK的公交查询系统设计

4　系统实现

我们调用北京市2006年公交线路网络数据并在此基础上完成了系统的实现:

与实现[J].微计算机信息,2007,23(8):2222224.

[5]http://download3.mcm.edu.cn/mcm07/GYtretHF

UHSIU875744BFDY6t6vR67tk0irdug98trbjg99/B2007.doc.

[6]http://download.mcm.edu.cn/mcm07/GYtretHFU

HSIU875744BFDY6t6vR67tk0irdug98trbjg99/B2007data.rar.

图3　公交查询系统实现

本刊更正

),男,资经与环境专业因在2008年第1期第页脚注(作者简介)的校对中有误:王炎(1986—

),女,2005级资源环境与城乡规划管理专业本科生。2005级本科生应更正为“:王炎(1988—”特向作者、

读者致歉。

本刊编辑部

二○○八年六月二十日

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文