第30卷第6期2000年11月东南大学学报(自然科学版)JO URNAL OF S OU THEAS T UNIVERSITY (Natural Science Edition)Vol 130No 16Nov.2000基于GIS 的公交乘客出行路径选择模型X杨新苗 王 炜 马文腾(东南大学交通学院,南京210096)(清华大学,北京100084)摘 要 公交乘客出行路径选择模型是公交乘客信息系统的关键技术.本文通过对公交乘客出行心理的研究,结合地理信息系统(G IS)的特点,提出了以换乘次数最少为首要目标、出行距离最短为第二目标的基于GIS 的公交乘客出行路径选择模型.为提高路径搜索效率,模型中提出了GI S 方向估价函数的概念.在南京市实际公交网络上的试算结果表明该模型实用、高效.关键词 出行路径选择模型;乘客信息系统;公共交通;地理信息系统分类号 U121X 国家自然科学基金资助项目(59838310).收稿日期:2000-02-28. 第一作者:男,1974年生,博士研究生.公交乘客出行路径选择模型的研究对于公交乘客信息系统的研究和开发有着重要的意义.乘客信息系统是智能交通系统中的重要组成部分.乘客信息系统中以提供公交信息为主的部分称为公交乘客信息系统.公交乘客信息系统最重要的一个功能是在乘客给出起迄点后,自动生成最优的出行路径方案供乘客选择.搜索与生成最优出行路径的理论模型就是公交乘客出行路径选择模型.公交乘客出行路径选择模型研究的实质是寻找乘客的出行在公交网或道路网上分布的规律.研究和建立更接近现实的模型,有利于得到更合理的公交客流分配结果.国内对乘客出行心理的研究较少,现有的出行路径选择模型多为基于/出行距离最短0或/出行耗时最少0的最短路模型,但实际的调查却表明/换乘次数0是大部分公交乘客在选择出行路径时首要考虑的因素.而且现有的模型基本上是在道路网上进行的,道路网上的最优路径,不一定是公交网上可行的路径.本文通过对公交乘客出行心理的研究,结合GIS(地理信息系统)的特点,提出了以/换乘次数最少0为首要目标、/出行距离最短0为第二目标的公交乘客出行路径选择模型,并且在南京市公交网络上进行了试算.1 公交乘客出行心理研究通过对公交乘客的出行心理、行为进行调查研究,确定模型的优化目标和约束条件.公交乘客选择出行路径的决策过程主要受到以下3个因素的作用:/换乘次数0、/出行距离0和/出行耗时0.换乘次数是指乘客在完成一次出行过程中所换乘的次数.出行距离分为车上距离和车外距离两部分.车外距离是乘客为乘车而步行的距离,它包括从起点到上车站台的距离、换乘距离以及下车后到目的地的距离.出行耗时同样也包括车上和车外两部分,只不过乘客的车外耗时还包括在站台上的等车时间.1999年在南京市的8个主要公交站点进行了一次公交乘客出行心理问询调查,共得到有效表格440份.图1是调查结果.图1 南京市公交乘客出行路径选择因素由图1可见,41116%的乘客在选择出行路径时首选考虑的是换乘最少,其次才是时间最短、路程最短.从调查得到仅有30170%的乘客不用换乘,3114%的乘客需换乘1次,26198%的乘客需换乘2次,13126%的乘客需换乘2次以上才能到达终点.换乘比例高是我国城市公交的一个普遍现象,在鞍山、无锡进行的调查也得到类似的结果.造成换乘比例高的主要原因是出行距离的增长.1986年南京市居民公交出行的平均距离为411km,到1997年达到5127km,10年增加2815%.所以本模型选用/换乘次数最少0作为首要优化目标;/出行耗时最少0虽是公交乘客考虑的第二重要因素,但因其难以准确测算,故选择易于量化的/出行距离最短0作为第二位的优化目标.2 公交网络的GIS 表示方法GIS 技术为生成和管理公交网络提供了新手段.GIS 公交网络可以表示为G =(V ,E ).式中,V 为公交站台的集合.一个公交站台可能是多条线路的上下客站点.E 为公交站台之间的联接边.若A 站台与B 站台是n 条线路的相邻上下客站,那么A 与B 之间有n 条联接边.在GIS 系统中通过公交站台表、站台联接边表以及站台经过线路表来表示公交网络.图2所示的公交网络可表示为表1~表3所示的网络结构.表1中的/站台经过线路总数0是指以此站台为上下客站点的线路总数,/站台实体0存储的是站台/点对象0.图2 公交网络示例表1 公交站台表站台编号站台名称站台经过线路总数站台实体1001A 2OB J 1002B 2OB J 1003C 1OB J 1004D 1OB J 1005E1OB J表2 站台联接边表起点站台终点站台联接边线路属性联接力实体100110023路OBJ 100110042路OBJ 100210013路OBJ 100210031路OBJ 100210033路OBJ 100210051路OBJ 100310021路OBJ 100310023路OBJ 100410012路OBJ 100510021路OBJ表3 站台经过线路表站台编号经过线路10012路10013路10021路10023路10031路10033路10042路10051路88东南大学学报(自然科学版)第30卷3 几种最短路算法的特点和不足出行路径选择模型的基础是最短路算法.常用的几种网络最短路算法有Dijkstra 算法、Floyd 算法、Moore 2pape 算法等.针对建模的需要,对几种方法进行分析如下:Dijkstra 算法是由Dijkstra 于1959年首先提出的.此算法的思想是对节点赋以标号,在迭代过程中不断更新标号.每一步的节点标号代表从起点s 至该点有向路径长度的上界.迭代结束时,节点的标号就是从s 到该点最短有向路的准确长度.Floyd 算法可求出所有点对之间的最短有向路.设U m ij 表示从点i 到点j 且不经过m,m+1,,,n(除去点i 和点j)的最短有向路的长度,则自点i 到点j 不经过点m+1,m+2,,,n (除去点i 和点j)的最短有向路有2种情况:¹不经过点m,此时有U m+1i j =U m i j ;º经过点m,此时有U m+1i j =U m im +U m mj .因此,总有U m+1i j =min {U m i j ,U m im +U m m j }.显然,当m =n 时,U m+1ij就等于网络中自点i 到点j 的最短有向路的长度.M oore 2pape 算法使用了链表管理技术.设路段节点集合为V 表示,路段ij 的路权为d i j ,l i 表示节点i 的最短路权,即从根节点r 至i 的最短距离.p i 表示i 的前节点,算法的步骤如下:¹初始化.将根节点r 置于链表T ,T 为一维有序数组,其内容为节点的编号.令p i =0 i I V, l i =0i =r] i X r,i I Vº若链表T 非空,取出T 中第1个节点i,检验所有与i 相连接的节点j.如果l i +d ij <l j ,则令p j =i,且l j =l i +d ij ,并将j 加入T ,当所有的j 都检验完后,将i 从T 中删除.»当链表T 中没有节点时,通过追踪p 找到r 到所有节点的最短路径,否则返回步骤º.在步骤º中,为提高计算效率,对j 在T 中的位置分为3种情况处理.如果j 曾在T 中出现过,但现在不在其中,将其放在当前检查的节点i 之后;如果j 从来没有在T 中出现过,则将其置于T 末尾;如果j 正在T 中时,不用增加.3种算法在道路网络上都是适用的,其缺点为:Dijkstra 算法虽可用于大型网络,但计算速度慢;Floyd 算法虽然可以快速地进行/多对多0的计算,但它不能应用于大型网络;M oore 2pape 算法由于采用了链表技术,计算速度较快,亦可用于大型网络,但它无法进行/一对一0的计算,即使用该算法时,只有访问完所有的节点后才能输出正确的结果,M oore 2pape 方法将大量的计算时间耗费在寻找起点与终点点对以外的最短线路,这显然不适用于公交网络.而且以上几种算法都没有考虑换乘问题.4 基于GIS 的公交乘客出行路径选择模型[1]研究以Dijkstra 算法为基础建立模型,并吸收Moore 2pape 算法链表管理技术的优点,建立起适合GIS 网络的公交出行最优路径选择模型.具体算法思路是:先找出起点r 周围的站点集合S,并将S 放入链表T 中,然后在每次执行过程中找出T 表中公交权值最小的一个站点i,在将i 点从T 表中删除以前,以i 点作为当前的基点向外搜寻,然后修正搜寻到的站点权值,并应用GIS 方向估价函数判断是否为有效站点,将搜索到的有效方向上的站点放入T 表,以此过程反复进行,直到搜寻到的基点为终点周围的站点为止,这时通过逆向搜索便可以得到从起点到终点的公交最优出行路线.在算法中通过公交权值的判断和赋值实现对换乘次数和出行距离89第6期杨新苗等:基于GIS 的公交乘客出行路径选择模型的控制,控制和判断的原则是优先选择换乘次数小的路径,在换乘次数相同的情况下再考虑出行距离.首先利用GIS 的地理函数,由公交站台表和站台经过线路表生成公交节点表.在节点表中,某一空间点,若为k 条线路的上下客站点,则在此点有S 1,S 2,S 3,,,S k 个公交节点.节点i,j 若为同一线路的相邻站点,则记其之间的距离为B ij ,B ij 可由站台联接边表得到.对应于公交节点i,设n i 表示从起点r 到节点i 最少的换乘次数;l i 表示从起点r 到节点i 的最短公交出行距离;p i 表示在最短路径上节点i 的前一个节点;布尔值f i 表示节点i 在最短路上与前一节点是否有线路直接相连,即从前一点沿最短路前进到该点的方式是否为步行方式,如果是步行方式,则f i 的值为True,否则为False ;e i 值则表示节点i 是否在终点周围,e i =True 表示其在终点周围;最后设N 为当前换乘次数,L 为当前出行距离.该算法的具体步骤如下:¹初始化.根据给定的起点r 和终点s 的坐标,利用GIS 的地理函数找出r 和s 周围一定范围内的公交节点集合S 和D.将S 放入链表T 中,并置其l j 值(j I T )为r 点到j 点的距离;将D 中节点的e i 值赋为True ;并令所有节点的n i 和p i 值为0,f i 的值为False ;将N 和L 也置为0.º找出链表T 中公交权值最小的节点i(首先考虑n i ,在n i 值相同的情况下,再比较l i 值的大小),将其n i 值和l i 值分别赋给N 和L,并将i 从链表T 中删除.»如果节点i 的e i 值为True ,则结束运算,输出结果,否则执行步骤¼.¼以节点i 为搜寻基点,通过地理函数搜寻其相邻节点j,相邻节点分为2种情况:一种是直接与i 相连的节点,即i 的上一站或下一站;另一种是不与i 直接相连的节点,即是从该点步行一定距离即可到达的节点,将后一种节点的f j 值设为True ,并设2点之间的步行换乘距离为W i j ,然后对找到的相邻节点权值进行修正.具体修正方法见图3.图3 公交节点权值修正方法n j 值则视该点的公交线路与到达基点时的线路是否一致,若一致,则令n j =N ,否则令n j=N +1.估价中间节点方向有效性是为了避免在无效方向上大量搜索.文献[2]提出了用GIS 方向估价函数改进搜索策略,此方法同样适用于公交网络.网络搜索过程中,定义沿着起点r 到终点s 的方向为空间有效方向,相反的方向为空间无效方向.实际应用中,可能会出现有效方向上的路径不能被采用,而必须在无效方向上的一定距离内采用某些路径.设向量p (j)表示中间节点j 的位置,p (r )和p (s)分别表示起终点的位置,h (j)=p (j)-p (r )表示节点j 相对起点的位置.以h (j)为估价函数,如果j 点在无效方向上,而且h (j)>L p (r)-p (s)时,即停止该路径上的扩展搜索,从而可以大量减少无效搜索次数.u 为可调节的系数,一般取015左右.½如果链表T 非空,返回步骤º,否则结束.算法的具体计算框图见图4.90东南大学学报(自然科学版)第30卷图4 基于GIS 的出行路径选择算法流程图算法利用GIS 地理函数搜索节点的相邻节点.这一方法突破了邻接关系的束缚,使得步行换乘的搜索和计算成为可能,实践证明这一方法适用于公交网络.保证搜索结果合理性的一个关键指标是搜索半径的确定.依据5城市道路交通规划设计规范6的规定,乘客在步行500m 以内能到达合适的公交站点.南京市的实际调查表明,乘客平均需要步行9109min 才能从起点抵达车站,而且从终点站步行到终点还需10103min .以乘客步行速度4km/h 计,乘客到站或离站的平均距离接近700m .故在确定搜索半径时,应以700m 为上限,优先搜索500m 以内的站点.按照本文提出的公交乘客出行路径选择模型,以南京市区范围的42条公交主干线为基础建立起了一个试算网络.该网络包括347个公交站台,572个公交节点,1066条公交联接边.试算的结果表明该模型实用、高效.参考文献1 马文腾.公交辅助出行决策系统:[学位论文].南京:东南大学交通学院,19992 徐业昌,李树详.基于地理信息系统的最短路径搜索算法.中国图像图形学报,1998,3(1):39~43GIS 2Based Public Transit Passenger Route Choice ModelYang Xinmiao 1 Wang Wei 1 M a Wenteng 2(1College of Traffic and Transportation Engineeri ng,Southeast Uni versity,Nanjing 210096)(2Tsi nghua Universi ty,B eijing 100084)Abstract: Public transit route choice model is the key technology of transit passenger inf ormation sys 2tem.A GIS 2based public transit route choice model is presented in this paper.It is based on a new short 2est path algorithm whic h uses the least transfer times as primary object and shortest path distance as sec 2ond object.Application in Nanjing public transit netw ork show s that it is ef ficient and practical.Key words: route choice model;passenger information system;public transit;GIS91第6期杨新苗等:基于GIS 的公交乘客出行路径选择模型。