公共交通系统最佳路径算法

第34卷第2期2004年3月东南大学学报(自然科学版)JOURNALOFSOUTHEASTUNIVERSITY(NaturalScienceEdition)Vol34No2Mar.2004王莉李文权(,210096):在分析城市道路网络最短路径算法(SP算法)和公交网络的特点的基础上,提出公共交通系统最佳路径算法.首先引入直达矩阵(T矩阵)和最小换乘矩阵(Q矩阵),讨论公交网络节点间换乘问题,得出最少换乘算法.利用Q矩阵确定节点间最少换乘次数,评价公交网络方便可达性.其次结合最少换乘算法,对最短路径算法(Dijkstra算法)进行改进.在标号过程中,利用Q矩阵对待检验T标号点进行筛选,减少T标号计算量,得到一条综合考虑路径长度和换乘的最佳路径.最后用一个简单的算例进行验算,说明该算法适用于一般公交网络,特别是换乘代价较高的公交网络.:公交网络;最短路径;最佳路径;矩阵;最少换乘:U491:A:1001-0505(2004)02026404BestroutingalgorithmforpublictransportationsystemsWangLiLiWenquan(CollegeofTransportation,SoutheastUniversity,Nanjing210096,China)Abstract:Thispaperpresentsabestroutingalgorithmforpublictransportationsystemsonthebasisofanalyzingtheshortestpathalgorithminurbantrafficnetworkandthecharacteroftransitnetwork.TmatrixandQmatrixareintroducedtodiscussthepathplanningproblemandtheleasttransferalgorithmisobtained.ByusingQmatrixtheleasttransferbetweentwonodescanbedeterminedandtheperformanceofthetransitnetworkisevaluated.Byintegratingthealgorithmintoshortestpathalgorithm,abestpathinconsiderationofpathlengthandtransfercanbefound.Finally,asimplenumericalexampleisgivenwhichshowsthatthisalgorithmisappliedtogeneraltransitnetworkespeciallytoahightransfercostnetwork.Keywords:transitnetwork;shortestpath;bestpath;matrix;leasttransfer:20030624.:(50078015).:(1979),,;(),,,,[e-mail]..,,.,(),.,,..(),[1].,2.2,,,..,.2,,.(shortestpath,SP)Dijkstra[2]()PSP(partitioningshortestpath)DBFS(dynamicbreadthfristsearch)[3].,SP.,2,SP,.1,,.G=(N,A),N,A.;.,[4,5]:S;R;K(r,s)rs,rs,K=0,K=1,K(r,s1)K(r,s2)0rs2,s1,s2s1;R(s)s,R(s)={rK(r,s)0,rR};C(r1,r2)r1,r2,C(r1,r2)={sK(r1,s)0K(r2,s)0,sS};D(s,t)st,D(s,t)={rK(r,t)K(r,s)0,rR}.221(T)T.Ti,jijn,Ti,j=nij0i=j1.1~15,R1~R5,.11~9TT=011100100001010011000000000000000100000000111000010100000000000000000001000000000T2=001010111000000112000000000000000000000000001000000111000000000000000000000000000Tn(n-1)ij[4].T21,5=115,2.Tk,jkj,Tni,j=kTn-1i,kTk,j22(Q)Q,Qi,jTni,j0n,n[1,).Qi,j-1ij.1QQ=1112122122122112113413411122123111231231112223223212212311111221231211112112,2.Q4,15=34152.Q,.Qij,ij,,i,jQij.,T,Q.Tki,j,pk,Tpi,j0.T21,3=113,2,(13).T1,3=1,Q1,3=1.23o,d.o=d,;Qod=1,D(o,d),265第2期王莉,等:公共交通系统最佳路径算法;Qod=2,m,Qom=1,Qmd=1.D(o,m)D(m,d),,m;Qod=3,2m1,m2,Qom1=1,Qm1m2=1,Qm2d=1.D(o,m1)D(m1,m2)D(m2,d),,m1,m2.3SPDijkstra.Dijkstra,.o,(T),(P),dP,od.,.,,.,Q,,,.Dijkstra:oP,Po=0,T,Ti=.WTVPi,iTj,0K(r,i)K(r,j)QjdQ0,rW,jV.,Q0.TVj,Tjmin[Tj,Pi+dij],,dij(i,j).PTQ,P.,,dP,.41,1~15..().:tR=t0+tp(1),tRR;t0;tp.,t0=ta+tb+td+th(2),ta;tb;td,,tf,td=tf/2;th,.tp,tp=n480=n14802608000=15n(min)(3),n;8000,5d/.,,,,,tR=ta+tp=(i,j)Rtij+15n(4),tij,.21.2Dijkstra,1~15Rs:147101314111215,3.(4)tRs=(i,j)Rstij+15n=18+152=48(min)3Dijkstra266东南大学学报(自然科学版)第34卷Dijkstra:,P1=0;Ti=,i=2,3,,15.1,1:WTV,1P,T2,4.K(R1,1)K(R1,2),Q2,15=12,K(R4,1)K(R4,4),Q4,15=32(,,Q02,).W1={R1},V1={2}.2:T,T2=4.3:P,P2=4.2,1:WTV,2P,T1,3,4,5,6.K(R1,2)K(R1,1),K(R1,2)K(R1,3),Q3,15=2,K(R2,2)K(R2,5),Q5,15=12,W2={R2},V2={5}.2:T,T5=4+3+15=22.3:P,P5=22.,15P,P15=36.Rb:125891215,4.(4)tRb=(i,j)Rbtij+15n=21+15=36(min)=P1542:tRbtRs,RbRs,.5,,...TQ,.Dijkstra,QT,T,.(References)[1]deDOrtuzarJ,WillumsenLG.Modellingtransport[M].England:JohnWiley&SonsLtd,1994309317.[2].[M].:,19957983.[3],,.[J].,1994,16(5):4349.WangSunan,SongWei,JiangWensheng.Comparisonoftheshortestpathalgorithms[J].SystemsEngineeringandElectronicTechnology,1994,16(5):4349.(inChinese)[4]LiuCL,PaiTW,ChangCT,etal.Pathplanningalgorithmsforpublictransportationsystems[A].In:Procofthe4thInternationalIEEEConferenceonIntelligentTransportationSystems[C].Oakland,USA,200110611066.[5]LiuCL.Bestpathplanningforpublictransportationsystems[A].In:Procofthe5thInternationalIEEEConferenceonIntelligentTransportationSystems[C].Singapore,2002834839.267第2期王莉,等:公共交通系统最佳路径算法