第42卷 第3期2007年6月西 南 交 通 大 学 学 报J OURNAL OF SOUTHW EST JI A OTONG UN I VERSI T YV o.l 42 N o .3Jun .2007收稿日期:2005 05 31作者简介:何迪(1980-),女,博士研究生,主要研究方向为城市交通,电话:028 ********,E m a i :l hel u cy_1980@yeah .net 通讯作者:严余松(1963-),男,教授,博士,电话:028 ********,E m ai:l yanyu s ong @文章编号:0258 2724(2007)03 0315 05基于矩阵分析的公共交通网络最优路径算法何 迪1, 严余松1, 郭守儆2, 郝 光1(1.西南交通大学交通运输学院,四川成都610031;2.西南交通大学土木工程学院,四川成都610031)摘 要:为了更符合实际情况,即充分考虑换乘次数是乘客选择公共交通网络的决定因素,运行时间是其重要因素,分析了乘客心理特征,用G IS 技术建立了公共交通网络模型,构建了适合公共交通分析的直达矩阵和最小换乘矩阵.在此基础上,结合路段、节点运行时间,提出了公共交通网络最优路径算法,并用一个简单的算例对算法进行了说明.关键词:公共交通网络;地理信息系统;最佳路径中图分类号:U 491 文献标识码:AOpti m al R outi ng A l gorith m for Public Traffic N et workBased onM atrix Anal ysisHE D i 1, Y AN Yusong 1, GUO Shoujing 2, HAO Guang1(1.Schoo l o f T raffi c and T ransportation ,South w est Ji aotong U niversity ,Chengdu 610031,Ch i na ;2.Schoo l o f C i v ilEng .,South w est Jiao tong U niversity ,Chengdu 610031,Chi na)Abst ract :In order to ta ll y w ith the actua l sit u ation further ,.i e .,transfer ti m es are a deter m i n i n gfacto r and travel ti m e is an i m portant facto r i n passengers cho ice o f a route in a pub lic tra ffic net w or k,the psycho log ical characteristics of passengers w ere ana l y zed ,a public traffic ne t w ork m ode l based on GIS (geog raph i c al i n f o r m ation syste m )w as established ,and the pa t h p lann i n g m atri x and the least transfer m atrix used to the ana l y sis of public traffic w ere constructed .On the basis o f t h e above w orks ,an opti m al routi n g a l g orith m fo r public traffic net w orks w as proposed by consi d er i n g the link travel ti m e and the ti m e at bus stops .Fina ll y ,a si m ple exa mp le w as g iven to sho w th is a l g orit h m.K ey w ords :public tra ffi c net w ork ;G I S (geog raphical i n for m ation syste m );opti m al rou te目前应用较广泛的公路网络最短路径算法有D ij k stra 算法、Floyd 算法和M oo re Pape 算法.由于城市公交线网的特殊性,公交网络与公路网络最优出行路径算法有很大不同,文献[1]中就指出了公路网络的最优算法应用到公交网络的不足.常见的公交网络最短路径算法是采取对初始和终止站点线路集合向外扩展,逐渐逼近的搜索算法[2],该模式以换乘次数最少为目标,需要进行集合的逐步扩展、排序、求交等,具有搜索速度慢和目标单一的缺点.笔者在分析乘客心理和对公交网络G I S (geog raph ical infor m ati o n syste m )描述的基础上,引入特殊矩阵,并将时间因素引入到模型的计算当中,得到最优出行路径.该算法较以往将出行距离作为权重的算法更符合乘客选择出行路径的实际情况,同时结合G I S 技术和特殊矩阵的应用,避免了大量的重复计算,一方面提高了搜索速度,另一方面也简化了算法.西 南 交 通 大 学 学 报第42卷1 最少换乘次数方案1.1 乘客心理的分析乘客具有以下的心理特征:(1)要求便利[3],总希望能够获得更加方便的换乘条件,同时尽可能减少换乘次数;(2)要求时效,都希望在尽可能短的时间内完成乘车活动,能够获得准时快捷的服务.其他还有舒适、实惠、对乘车安全的要求、对大众心理的附和等心理特点.杨新苗等[4]1999年在南京市的8个主要公交站点进行了公交出行心理问讯调查,调查表明公交乘客选择出行路线时主要考虑的因素有3个:首先是换乘最少,其次才是时间最少、路程最短,此外在鞍山、无锡进行的调查也得到类似的结果.本文算法以换乘次数最少作为优化的首要目标,出行时间最短作为第二要求,这在一定程度上满足了乘客出行选择路径的要求.同时在求解最小换乘次数中引入最少换乘矩阵简化算法,提高算法的时效性.1.2 公交网络的GIS 描述公交网络是由一系列节点,连接节点的路段以及公交线路组成,用G 表示公交网络,G =(N,S,R,W N ,W S ),其中:N ={N i1 i n }是节点集合,n 是节点数;S ={S j 1 j m }是路段集合,m 是路段数,S 中包括步行和公交运行路段;R ={R k 1 k u }是公交线路集合,u 是线路数;W N ={W N i 1 i n,N i N }是节点的非负权值的集合;W S ={W S j 1 j m,S j S }是路段的非负权值的集合.由于城市(尤其是大城市和特大城市)公交网络站点、线路繁多,实际网络十分复杂,利用G I S 所具有的地理分析特性,构建公交站点表、公交路段表、公交线路表等公交网络结构数据表,得出公交网络的G I S 描述,作为分析计算的基础.1.3 直达矩阵对于有n 个节点的公交网络,结合公交网络的G I S 描述,利用G I S 特有的地理分析特性,得出相应的n 阶矩阵A =( rs )n n ,其中:rs =0, 若节点r ,s 间无线路相连;a rs ,k , 若节点r ,s 间可通过第k 条线路相连.(1)式中:r ,s 代表公交网络G 的两个节点,r ,s N;k 代表第k 条公交线路,k R.称A 为网络G 的直达矩阵,由A 的定义可知,若 r s 0, rs 实际上表示公交站点间的一条直达路径.图1所示公交网络,共有6个节点,4条公交线路,即n =6,u =4. rs 的计算步骤如下:图1 公交网络F i g .1 P ublic traffi c net work(1)根据线路R 1所经过的节点计算其邻接矩阵A 1.如果线路R 1经过z 个节点,则其中有C 2z 个项取值非零,其余项均为零;(2)与步骤(1)方法相同,计算线路R 2,R 3, ,R u 的邻接矩阵A 2,A 3, ,A u ;(3)将各线路邻接矩阵相加得公交网络邻接矩阵A =uk=1A k .图1所示公交网络的直达矩阵为A =0a 12,1a 13,1a 14,3a 15,3000a 23,10a 25,400000000000a 45,2+a 45,3a 46,200000a 56,200.1.4 换乘矩阵为了得到一次换乘矩阵A ,对直达矩阵A ,定义 乘法 运算A =( 2rs ),其中:316第3期何迪等:基于矩阵分析的公共交通网络最优路径算法2rs= nx=1rx x s, r s;0, r=s.(2)式中:x代表公交网络G的一个节点,x N.为了使 2rs表示从节点r到s一次换乘路径的全体,但又不包含从节点r出发,经过某条线路到达换乘节点x,又从该换乘节点x返回r的情形,规定 2r s=0[5],则矩阵A 为一次换乘矩阵(其元素代表一次换乘的路径).类似地可定义二次换乘矩阵A =( 3r s)(其元素代表二次换乘的路径)及更高次换乘矩阵.由于公交网络规划中,一般设定公交路网中任意两个公交站点之间最多二次换乘到达,因此只需计算到A 即可.考虑到公交网络的特殊性,需对A 和A 矩阵做下列修正:(1)若 2r s或 3rs中某一项包含元素a rx,k a xs,k,即r,x和s三点都在线路k上,且通过线路k可以从节点r 到达节点x,再从节点x到达节点s,则将该元素合并为a rs,k,即通过线路k可以直接从节点r到达节点s;(2)在 2r s中除去直达的路径(即矩阵A 中存在仅包含单个a rs,k元素的项),同样的,在 3rs中除去一次换乘的路径;(3) 2rs取值非零,若 r s取值亦非零,则令 2rs=0(即若节点r到节点s有直达路径,则不考虑一次换乘路径).同样的, 3r s取值非零,若 r s或 2r s有一项取值亦非零(根据上一条, r s和 2rs不可能同时取非零值),则令 3r s=0.经过修正,减小了计算量,提高了运算效率.图1的一次换乘矩阵为A =00000a14,3a46,2+a15,3a56,2 00000a25,4a56,2 000000000000000000000000,二次换乘矩阵为A =01.5 最少换乘矩阵根据直达矩阵和换乘矩阵的定义,可直接得到最少换乘矩阵C=(c rs)n n,C=A+A +A ,(3)图1的最少换乘矩阵为C=0a12,1a13,1a14,3a15,3a14,3a46,2+a15,3a56,2 00a23,10a25,4a25,4a56,2 0000000000a45,2a45,3a46,200000a56,2 000000.通过最少换乘矩阵C可以确定站点间的最少换乘次数[6],直接得出换乘站点编号,克服了传统算法通过站点、线路集并集运算求换乘站点的缺点.通过输入节点编号,直接搜索C矩阵即可得到换乘站点最少的路径集,避免了大量的重复搜索.2 权重系数的确定考虑到同一公交站点当其为一条公交线路经过的一点和两条公交线路的换乘点时有不同的阻抗,且换乘时耗是通勤中影响时间最优的重要因素,因而在拓扑网络中用带权值的节点模拟站点时耗[7],并对路段赋以权值.317西 南 交 通 大 学 学 报第42卷2.1 节点非负权值W Ni的确定由于通过矩阵C可以直接找到换乘次数最少的路径集,所以在确定节点权值时对换乘站点不再增加惩罚量,只考虑基本的换乘时间消耗.同时根据站点是否为换乘节点,即节点的出边和入边是否在同一线路上,得站点N i的权值W Ni =f(S in,S out,N i)=t s(S in,N i), 若节点N i在路径中不是换乘节点;t w(S ou t)+t s(S ou t,N i), 若节点N i是路径中换乘节点.(4)式中:S in是节点的流入路段,S in S;S ou t是节点的流出路段,S ou t S;t s(S in,N i)是公交车在站点N i最少停留的时间,由路段S in所属线路上站点N i的上下车人数决定;t w(S ou t)是乘客在站点N i的候车时间,可取路段S ou t所属线路发车间隔时间的一半.2.2 路段非负权值W Sj的确定以往的算法大多是选择了易于量化的节点间距离作为路段权值,但这与实际情况差别较大[8],为此,选择时间因素作为路段权值的度量标准.根据路段性质的不同,分步行路段和公交运行路段两类,分别确定权值如下:(1)步行路段权值 当S j是步行路段时,路段权值为W Sj =S jv p,(5)式中:S j是步行路段的距离(街道中心线的长度);v p是步行的速度(考虑到集中在1.0~1.3m/s的行人步速占全部行人步速的60.7%[9],取步行速度为1.1m/s).(2)公交运行路段权值 当S j是公交运行路段时,路段权值为W Sj =S jv b, 若路段S j中没有信号灯交叉口;S jv b+t d(S j), 若路段S j中有信号灯交叉口.(6)式中:S j是公交运行路段的距离;v b是公交车的平均运行速度;t d(S j)是公交车通过公交运行路段S j在交叉口延误的时间,取为该路段上所有交叉口红灯时间之和的一半.上述模型在考虑时间因素时,实际上已经考虑了出行距离.3 算法步骤本算法中首先保证换乘次数最少,在此基础上选择连接起讫点及两者之间一系列连通节点序列的时间最短的路径作为最优出行路径.利用最少换乘矩阵C,以及节点和路段权值,根据城市交通网络最短路径基本处在起始点和终点一定范围内的特点[10],加入步行分析[9],得到公交网络最优出行路径算法过程如下(O代表起点,D代表终点):(1)如果OD点间的距离S OD<300m,则进行步行分析,如果存在合适的步行路线,则建议出行者步行到达,否则转(2);(2)搜索给定的O和D点附近的公交站点集O(r)和D(s),其中r O(r),s D(s).对于任一满足条件的(r,s)节点对,从矩阵C中找出所有的c rs项,若存在直达路径集(即有 rs非零项),则计算各路径总的时耗,时耗最短的路径为最优出行路径,否则说明没有直达路径,转(3);(3)若c rs项存在一次换乘线路集(即有 2rs非零项),则计算各路径总的时耗,时耗最短的路径为最优出行路径,否则说明没有一次换乘路径,转(4);(4)若c r s项存在二次换乘线路集(即有 3rs非零项),则计算各路径总的时耗,时耗最短的路径为最优出行路径,否则说明没有合适路径,算法结束.以图1所示公交网络为例,假设O点为节点 ,D点为节点 ,S OD>300m,不需进行步行分析和搜索O和D点附近的公交站点集,直接从最少换乘矩阵C中找出c16项.由c16=a14,3a46,2+a15,3a56,2可知有两条路径可供选择:318第3期何迪等:基于矩阵分析的公共交通网络最优路径算法319 ( )乘公交线路R3从节点 到节点 ,并在节点 处换乘公交线路R2到达节点 ;( )乘公交线路R3从节点 到节点 ,并在节点 处换乘公交线路R2到达节点 .根据已确定的节点权值和路段权值,比较路径1和路径2的时耗,较短者即为最优出行路径.增加节点权值后,路径时耗不再是以往路段权值的简单叠加,而是路段 节点权值的叠加.图1中节点 到节点 之间的两条路径,经过的站点和路段都是相同的,因此路段权值相同,但由于采用了不同的换乘方案,一个在节点 处换乘,一个在节点 处换乘,公交车在换乘站点的停靠时间不同决定了有不同的路径时耗,从而确定出最优路径.4 结束语通过乘客心理的分析和公交网络的G I S描述,结合公交网络的GIS描述和连接矩阵的方法,引入最少换乘矩阵,将换乘次数最少作为优化的首要目标,出行时间最短作为第二要求,并确定了节点权值和路段权值,在一定程度上满足了乘客出行选择路径的要求.随着先进的交通信息技术的发展,在今后的研究中应尽量加入实时因素,如分时段确定权值,从而对同样的OD点,在不同时刻可能有不同的最优路线.这一特性更符合交通网络的动态变化特征,也更能满足乘客的需求.参考文献:[1] W ONG S C,TONG C O.Esti m a ti on o f ti m e dependent or i g i n desti nation m atrices fo r transit net w ork[J].T ransportati onR esea rch B,1998,32(1):35 48.[2] 翁敏,毋河海,杜清运,等.基于公交网络模型的最优出行路径选择的研究[J].武汉大学学报,2004,29(6):500503.W ONG M i n,W U H eha,i DU Q i ngyun.A n opti m a l route cho ice based on pub li c traffic net work m odel[J].G eom atics and Infor m a tion Sc i ence o fW han U niversity,2004,29(6):500 503.[3] 李林波,吴兵.出行者心理因素对公共交通发展的影响[J].重庆交通学院学报,2004,23(3):94 97.L I L i nbo,WU B i ng.E ffects o f trav eler psycho l ogy fac tors on deve l op m ent o f publi c tra ffic[J].Journa l of Chongqi ng Jiao tong U n i versity,2004,23(3):94 97.[4] 杨新苗,王炜,马文腾.基于G IS的公交乘客出行路径选择模型[J].东南大学学报,2000,30(6):87 91.YANG X i n m i ao,W ANG W e,i M A W enteng.G IS based pub lic transit passenger route cho i ce m ode l[J].Journa l of Southeast U n i versity,2000,30(6):87 91.[5] 曹晋华,程侃.可靠性数学引论[M].北京:科学出版社,1986:109 113.[6] 王莉,李文权.公共交通系统最佳路径算法[J].东南大学学报,2004,34(2):264 267.W ANG L,i L IW enquan.Best routi ng a l gor it hm f o r publi c transportati on system s[J].Journa l o f Sout heastU n i versity,2004, 34(2):264 267.[7] 陆忠,钱翔东,张登荣.基于最短路径查询的城市公交网络拓扑建模研究[J].遥感信息,2001,(1):11 14.LU Zhong,Q IAN X i angdong,Z HANG D eng rong.A pplica ti on o f shortest pat h search i ng fo r urban pub lic tra ffic net w ork m ode li ng[J].R e m ote Sensi ng Infor m ation,2001,(1):11 14.[8] 李曙光,苏彦民.基于G IS的城市公交路网最优路线算法研究[J].中国公路学报,2003,16(3):83 86.L I Shuguang,S U Y an m i n.R esearch on opti m a l path fi ndi ng a l go rith m of urban transit net wo rk based on geographic inf o r m ati on syste m[J].Ch i na Journal o fH i gh w ay and T ranspo rt,2003,16(3):83 86.[9] 裴玉龙,张亚平.道路系统仿真[M].北京:人民交通出版社,2004:169 172.[10] 吴必军,李利新,雷小平.基于城市道路数据库的最短路径搜索[J].西南交通大学学报,2003,38(1):80 83.WU B ij un,L I L i x i n,LEI X iaop i ng.Shortest pa t h searching based on city road database[J].Journa l of South w est Jiao tong U n i ve rs i ty,2003,38(1):80 83.(中文编辑:秦萍玲 英文编辑:付国彬)。