下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

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

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

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

hapyy啸天
2011-08-03 0人阅读 举报 0 0 暂无简介

简介:本文档为《公交线路查询系统算法设计与实现pdf》,可适用于高等教育领域

收稿日期:基金项目:湖北省自然科学基金面上项目,课题编号:ABA作者简介:陈文磊(),男,福州人,级数学与应用数学专业在校生·大学生园地·公交线路查询系统算法设计与实现陈文磊,肖俊超,董 勐(华中师范大学数学与统计学学院计算机科学系,武汉)  摘 要:本文针对公交线路查询系统的可优化方面,就查询者不同需求下最佳路线的选择问题进行了研究,着重探讨了出行线路需换乘情况的查询及计算实现,并建立了一个较完善的线路查询系统。关键词:公交网络直达矩阵换乘中图分类号:O  文献标识码:A  文章编号:() 引言目前,已经有较多关于公交查询系统算法的研究及实现文献,人们从不同角度运用不同方法解决了线路查询的问题,但仍存在部分考虑不周全的地方。如文献从数据库的角度完成系统的构建,但却忽略了对乘客采用步行或地铁等多种出行方式下线路选择的考虑文献运用了GIS技术及换乘矩阵处理方法,使得系统稳定性和可塑性更强,但对整体出行过程分析不够深入文献对系统平台开发进行了探究,但针对换乘次及以上的情况未能给出一个通用的算法等。因此,我们围绕公交网络及乘客的整体出行过程进行了研究针对换乘多次、出行方式多样的情况利用直达矩阵的概念给出了一个通用算法并在最后完成了公交线路查询系统的研发及实现,并使之具有较好的通用性和可塑性。 系统构建公交网络整个城市的公交网络就是一个二维拓扑空间,由多段线路连接而成。每一线路都可以看成一条有向线段,线路中站点对应着是线上的点。根据交通部门掌握的城市公交线路L、途径站点S以及每条线路通过相邻两站点所需时间t等数据,我们对整个城市的线路、站点进行了标记。其中线路为Ld,d=,,⋯,m,m为城市开通的公交线路总数站点为Si,i=,,⋯n,n为站点总数。而换乘站点即为网络中任两条有向线的交点Sr,r∈{,,⋯n}。事实上,对于从起点Si到终点Sj经过换乘k次(换乘站点分别设为Sru,u=,,⋯,k)的出行路径,可以看成是由分别途径Si→Sr,Sr→Sr,⋯,Srk→Sj的k条图 公交线路网络示例线路Ld,d∈{,,⋯,k}或其部分构成的。因此乘客出行总时间T(票价P)也转化为这k条线路对应时间(票价)之和。我们以总时间最短的原则为例,对出行路径进行优化选择。直达矩阵对于任两站点Si,Sj,如果存在线路Ld均经过这两点,我们就称这两点是可相互直达的,否则不可直达。为了研究问题方便,不妨设Si的可直达站点集合为Ui。显然满足同时经过Si,Sj条件的线路可能不止一条,而每一条线路Si→Sj所需时间tdSij也各不相同。根据线路选择原则,我们遍历所有这样的线路并选取Si→Sj所需时间最少的那条线路Lij,则称Lij为Si,Sj间的直达线路,花费时间tSij为Si,Sj间的直达时间。根据之前的分析,对于两点Si,Sj间换乘k次的情况,出行路径即由k条直达线路构成,而k个换乘站点Srh,h=,,⋯,k即为路径中k条直达线路交点。满足Si→Sr,Sr→Sr,⋯,Srk→Sj均可直达,即:Si∈Ur,Sr∈Ui,⋯,Sj∈Urk,Srk∈Uj。因此寻求其所需最短时间及第卷第期高等函授学报(自然科学版)VolNo年月   JournalofHigherCorrespondenceEducation(NaturalSciences)   June©ChinaAcademicJournalElectronicPublishingHouseAllrightsreservedhttp:wwwcnkinet对应路径就转化为求min{tSirtSrr⋯tSrkj}及最小值对应路径。由于我们的路径计算均建立在直达线路、直达时间数据上,为了提高系统查询速度,我们将所有站点间n×n个直达时间与对应n×n条直达线路以及所有站点的直达站点集合全部计算出来并采用矩阵(即二维数组)形式将其固化储存。直达时间矩阵:tStS⋯tSntStS⋯tSn⋯⋯⋯tSntSn⋯tSnnn×n直达线路矩阵:LSLS⋯LSnLSLS⋯LSn⋯⋯⋯LSnLSn⋯LSnnn×n直达站点矩阵:UU⋯Unn×n其中若站点Si,Sj不可直达,则矩阵中对应(i,j)元值为实际生活中随着交通的不断发展,公交网络添加了更多不同的交通出行方式(如地铁)。但是由于整个公交系统是建立在该二维线路网络上,其他交通出行方式的本质就是使某些站点间不可直达的情况转变成可直达的情形。因此通过不断更新直达矩阵数据,就可使上述算法依然适用。直达时间、线路矩阵生成算法建立二维数组zhidann,linemm分别用于存储数据tSij,LSij。其中Si:=起点Sj:=终点zhidaij:=tSijlineij:=LSij。如图,我们建立了直达时间、线路矩阵生成算法的流程图。直达站点矩阵生成算法:()初始化d=,i=,j=()遍历d=到d=m,若存在d使得Si,Sj均在线路Ld上,则将Si加入Uj,Sj加入Ui中,否则进入()i,返回,若i>n则进入()j,i=。返回,若j>n则算法终止这里算法复杂度为O(n)。图 直达时间、线路矩阵生成算法流程 算法实现首先把已得的直达时间、线路矩阵和直达站点矩阵数据存放到文件中,称为固化数据。每次启动系统时,先从文件中读取数据,然后再进行以下的运算:输入起终点Si,Sj判断zhidaij是否为,若为则显示“无直达线路”,否则输出直达线路与直达时间zhidaij、lineij计算换乘一次情况()遍历直达站点矩阵第i,j行,若Ui∩Uj≠<,即ϖSr,r=,,⋯,r使Sr∈Ui且Sr∈Uj,则依次计算zhidairzhidarj,转入否则Si,Sj不可一次换乘到达,转入()比较zhidairzhidarj,r=,,⋯,r,并取其最小值min=zhidairzhidarj为最短时间,且输出对应经过Si,Sr,Sr,Sj的公交线路及换乘站点Sr计算换乘二次情况()遍历直达站点矩阵第i行,对于Ui中任意一点Sr,若Sr的直达站点集合Ur中存在Sr使得Sr∈Uj,则依次计算zhidairzhidarrzhidarj,转入否则Si,Sj不可二次换乘到达,转入第卷第期高等函授学报(自然科学版)VolNo年月   JournalofHigherCorrespondenceEducation(NaturalSciences)   June©ChinaAcademicJournalElectronicPublishingHouseAllrightsreservedhttp:wwwcnkinet()比较zhidairzhidarrzhidarj,并取其最小值为最短二次换乘时间,且输出对应经过Si、Sr,Sr、Sr,Sr、Sj的公交线路及换乘站点Sr,Sr计算换乘三次情况与换乘一次、二次的算法类似换乘至k次的情况也可依此计算得到。其中算法复杂度为O(nk)。据调查,一般乘客可接受公交换乘次数最大为次,因此从出行舒适度的角度考虑,公交查询系统构建到达次换乘即可。 系统实现我们调用北京市年公交线路网络数据并在此基础上完成了系统的实现:图 公交查询系统实现 结束语本系统主要针对总时间最短情况进行综合分析,以直达矩阵为切入点完成查询系统的实现。但在用户需求多样性、算法中数据占用存储空间压缩、运算速度提高、GIS系统的引进、系统安全性稳定性开发等方面有待进一步改进和优化。参考文献姜启源,谢金星,叶俊数学模型(第三版)M北京:高等教育出版社,舒靖城市公交查询系统设计J科技信息,():李玉芝,方源敏城市公交查询系统的设计与实现J地矿测绘,,():刘伯红基于GEOManiaGDK的公交查询系统设计与实现J微计算机信息,,():http:downloadmcmeducnmcmGYtretHFUHSIUBFDYtvRtkirdugtrbjgBdochttp:downloadmcmeducnmcmGYtretHFUHSIUBFDYtvRtkirdugtrbjgBdatarar本刊更正因在年第期第页脚注(作者简介)的校对中有误:王炎(),男,资经与环境专业级本科生应更正为:“王炎(),女,级资源环境与城乡规划管理专业本科生。”特向作者、读者致歉。本刊编辑部二○○八年六月二十日第卷第期高等函授学报(自然科学版)VolNo年月   JournalofHigherCorrespondenceEducation(NaturalSciences)   June©ChinaAcademicJournalElectronicPublishingHouseAllrightsreservedhttp:wwwcnkinet

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/3

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

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利