资源描述：
《公交线路优选模型及算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第25卷第4期甘肃科技Vol.25No.42009年2月GansuScienceandTechnologyFeb.2009公交线路优选模型及算法曹永春,马明(西北民族大学计算机科学与信息工程学院,甘肃兰州730030)摘要:建立了在仅考虑公汽线路选择情况下以换乘次数最少和途经站数最少为首要目标,出行耗时、出行费用为次要目标的优化模型,设计出以Dijkstra为核心的模型求解算法,并在考虑公汽地铁混乘和步行换乘的复杂情况对模型进行了改进。关键词:最优路径;Dijkstra算法;换乘次数中图分类号:T
2、P319这些年来,城市的公交系统有了很大发展,并且1.1模型假设大部分人乘坐公共交通工具(简称公交,包括公汽、(1)从任何一个公交站点经过有限次的换乘都地铁等)出行,目前国内各大城市的公交线路达到可以到达另一个公交站点,即公交网络是连通的。几百条,使得公众的出行更加通畅、便利,但同时也(2)所有实行单一票价制的公汽票价都相同,面临多条线路的选择问题。设计和实现一个高效的并且所有实行分段计价制的公汽票价的计价方式都公交线路选择计算机自主查询系统将大大方便乘客相同。的出行;而设计这样一个系统,其核心是
3、线路选择的(3)公汽站点和公汽线路的编号都是连续的。模型与算法。(4)不考虑路面交通状况(如发车频率、拥挤度乘客选择公汽线路主要考虑换乘次数、途经站等)。数、出行耗时、出行费用等四种因素。本文根据乘客(5)换乘时间等于步行时间、候车时间、换乘耗的各种不同需求,分别建立了以换乘次数最少和途时的和。经站数最少为首要目标,出行耗时、出行费用为次要(6)假设地铁线路是双向的。目标的优化模型。并且在同时考虑公汽与地铁线路1.2符号说明及定义换乘以及站点之间步行时间的问题我们对模型进行Si:表示公汽站点了改进
4、。S0:表示起始公汽站点模型求解的难点在于最优路径算法的设计。我Sv:表示目标公汽站点们将站点看作是网络图中的节点,分别以是否能一Li:表示公汽线路线可达和一站可达作为相邻关系建立图中的边;然Ti:表示地铁线路后应用Dijkstra算法求出仅包含站点的最短路径ω:表示可达路径(这些路径已满足首要目标);再根据关联这些节点Ω:表示可达路径全部集合的公汽线路,借鉴深度优先搜索算法搜索出满足次N:表示可达路径中途经站点总数要目标的线路选择方案。M:表示最大站点数arc:表示反函数运算1模型建立定义1(一
5、站可达):若存在某一公汽线路Li,使乘客选择公汽线路主要考虑换乘次数、途经站得乘客乘坐Li车一站即可到达Sj,则称Si一站可达[1]数、出行耗时、出行费用等四种因素。文献对乘Sj,称Li是使Si一站可达Sj的线路,简称一站可达。客的出行心理进行了调查分析,其结果表明,“换乘定义2(一线可达):若存在某一公汽线路Li既次数”是大部分公交乘客在选择出行方案时首先考途经站点Si又途经站点Sj,则称Si与Sj一线可达,虑的因素,“出行距离最短”为第二目标。所以,我简称一线可达。们分别以换乘次数最少和途经站
6、点最少为首要目标注:一站可达线路和一线可达线路统称为可达线路。建立了模型1与模型2。定义3(可达路径):给定起始公汽站点S0与终第4期曹永春等:公交线路优选模型及算法55到公汽站点Sv,由S0到Sv的一条可达路径ω是指③根据式k+1k+1由公汽站点与公汽线路(或地铁线路)编号交错构l(uk+1)=min{l(Sj)
7、Sj不在T中},确定k+1成的序列即ω=S0L1S1L2⋯SN-1LNSv其中Li是使uk+1并取d(S0,uk+1)=l(uk+1)Si-1与Si一站可达的公汽线路,此外S0到Sv的
8、第i④d(S0,uk+1)<∞?条可达路径记为ωi=S0Li1Si1Li2⋯Si,Ni-1LiNiSv。记Ω是:取T=T∪{uk+1},k=k+1,转②。为S0与Sv的所有可达路径的集合。否:G中S0到Sj(Sj
9、T)的路都不存在,根据d1.3模型建立(S0,uj)(1FiFk)应用逆向追踪法可求得G中S0ni-1到u(1FiFk)的最短路,算法终止。iω=arcmin∑I(Lij≠Li,j+1)ωi∈Ωj=1(3)找出最短路中各相邻站点间的所有可达线1,Lij≠Li,j+1路(一站可达与一线可达
10、线路)。其中,I(Lij≠Li,j+1)=模型10,Lij=Li,j+1(4)在所有可达线路中应用深度优先搜索算法ω=arcminNi模型2搜索出满足次要目标(出行耗时最少与出行费用最ωΩi∈少)的最佳线路。若模型存在多个最优解,则以出行耗时与出行算法1中核心是Dijkstra算法,此算法已经非常费用最少作为次要目标进行二次选择。事实上,由成熟,此外算法1中另外一个关键是图G权值C的于换乘候车需要时间以及途经站点越多,耗时也越选取,不同的赋权方式可得不同的目标解。若图G多,所以,模
