基于双向搜索的公交路径选择算法及优化模型

1、第27卷第6期吉林大学学报(信息科学版 Vol . 27No . 62009年11月Journal of J ilin University (I nf or mati on Science Editi on Nov . 2009文章编号:167125896(2009 0620579206收稿日期:2009208216基金项目:国家十一五科技支撑计划基金资助项目(2006BAC21B0124 ; 吉林省科技发展计划基金资助项目(20080527作者简介:张玉春(1965 , 女, 吉林四平人, 吉林大学副教授, 主要从事计算机应用与开发研究, (Tel 86213086802957(E 2ma

2、il zhangycjlu 1edu 1cn 。基于双向搜索的公交路径选择算法及优化模型张玉春a , 韩秀华b , 臧雪柏c (吉林大学a . 公共计算机教学与研究中心; b . 交通学院, 长春130025;c . 计算机科学与技术学院, 长春 摘要:为了解决人们出行公交路径选择问题, , , 提出一种基于双向搜索的公交网络路径选择算法。、出行费用和换乘次数等因素, 给出一个综合评价指数模型, 。基于数据库理论, 算法用数据库表示公交网络, , 易于实现, 执行效率较高。关键词:; ; ; ; 综合评价指数模型:ASelecti A lgorithm and Op ti m u m Mode

3、l of Public Trans portati on RoutesBased on T wo 2W ay SearchZHANG Yu 2chun a , HAN Xiu 2hua b , Z ANG Xue 2bai c(a . Center of Public Computer Teaching and Research; b . College of Traffic, J ilin University,Changchun 130025, China; c . College of Computer Science and Technol ogy, J ilin University

4、, Changchun 130012, China Abstract:I n order t o s olve the public trans portati on r oute choice p r oble m , the feature of public trans portati on net w ork, compares algorith m s of shortest r oute, and selecti on algorith m of public trans portati on net w ork r outes is analyzed based on t w o

5、 2way search . I n order t o select op ti m um r oute, thinking about the fact ors which are ti m e of transfers, cost of running and ti m es of transfers, a compound evaluati on index model is obtained . An exa mp le is given t o valldate possibility of the algorith m and the model . Based on the d

6、atabase theory, the algorithm exp res 2ses the public trans portati on net w ork with the database, realizes the most superi or riding pass choice with the da 2tabase inquiry technol ogy, it is easy t o realize, and t o be efficient .Key words:public trans portati on net w ork; shortest r oute; op t

7、i m um r oute; breadth first search; compound eval 2uati on index model引言当前, 我国许多大城市都存在着交通拥挤堵塞的问题, 而大力发展公共交通是解决城市交通问题的重要措施。随着我国城市建设的发展和国际交往的增多, 在当前和今后一段时期内, 城市公共交通线路都会不可避免地经常发生调整变动, 城市中各类人员对公交信息的查询需求不断增加。但我国城市公交乘客信息系统的发展处于一个落后的水平, 广大乘客可以获得信息的方式很少, 公交信息的完整性和准确性得不到保证, 而且没有专门的机构负责信息的发布和管理。如果能提供一种服务, 为市

8、民特别是外来旅游、出差、就医等急需了解本地道路情况的人们提供方便、快捷、经济、高效地利用公交线路的方案, 他们的出行和生活将更加方便。1问题的提出一般情况, 人们总是喜欢选择从起点到终点的最短路径。比如, 司机开车要从A 地到达B 地, 就会考虑走路程最短或时间最少的路径, 这是考虑路程或时间的最短路径问题。然而在公交网络模型中, 最短路径并不是决定公交出行路径选择的主要因素, 最优路径的选择会受到出行费用、出行耗时、出行距离、换乘次数等因素的综合影响。出行耗时是乘客在一次出行过程中所需的时间, 它包括车上耗时和车外耗时; 间, 比如从出发地到上车站点所用时间、车站等车时间、地所用时间。换车的

9、次数1。, 也和出行耗时相关联。, 。如果直接用图论中的方法描述公交网络、。2211一个图G 可以表示为G =(V, E , 其中V 是有穷而非空的顶点集合, E 是边集合, 可用一对顶点(v i , v j 表示。如果边是顶点的有序对, 则这个图是有向图。对G 中的一条边(v i , v j , 相应地有一个数L (v i , v j 称为边的权, 也称为边的长度。图G 连同其上的权被称为赋权图。一个顶点序列v 0, v 1, v 2, , v k , 称为从v 0到v k 的一条路经, 路径的长度L (v 0, v k =L (v 0, v 1 +L (v 1, v 2 +L (v k -

10、1, v k 。从v 0到v k 的所有路径中, 权L (v 0, v k 最小的路径称为从v 0到v k 的最短路径2。212公交网络特点公交网络是个赋权有向图, 站点是顶点, 边的权值可以是路段的长度、路段通行时间等, 同一条路段上可以有多条公交线路, 每条公交线路都有固定的行驶路线和停靠站点。公交网络有如下特点3:1 连通性。如果两条不同公交线路经过同一站点并都能在该站点换车, 则这两条公交线路是连通的, 但换车需要消耗时间和费用等。相反, 如果两条公交线路没有相交点或有相交点, 但该点不是公交站点或不是同时有站点, 则这两条公交线路是不连通的, 不连通的两条公交线路是不能换乘的。2 节

11、点特性。由于不同的公交线路即使行驶线路有重叠, 但他们的停靠站点不可能完全重叠, 所以乘客换乘时, 有时需要步行一段距离才能到达另外一条公交线路的站点。在描述公交网络时, 考虑到不同公交线路之间的换车问题, 往往需要把空间上相近但不重叠的不同线路上的站点, 合理抽象成公交网络图上的相关节点。3 最短路径意义。公交网络的最短路径有别于道路网络上的最短路径。道路网络的最短路径是两点之间最短距离或最短时间, 既为最优路径。公交网络中两点之间的路径受公交线路的制约, 从一条公交线路到另一条公交线路的换车会增加时间成本和费用成本, 所以就不能为寻找简单的最短距离的路径而随意换车。通常, 在公交路径选择时

12、, 要综合考虑出行时间、费用、方便性(如换乘 等交通阻抗, 交通阻抗值越小路径越优, 它们也被称之为最短路经因素, 是乘客选择公交线路的依据。图论中求最短路径算法着重考虑任意两个顶点间最短路径, 只要两个顶点有道路连接, 就可进行搜索, 而不考虑该路径换乘问题, 这就可能造成搜索到的路径需多次换乘, 因换乘带来的换乘时间和车票费用会增加交通阻抗。笔者给出了基于最小换乘次数的路径选择算法及综合评价指数优化模型。3公交网络最短路径常用算法比较目前, 出行决策模型方面的研究主要集中在以换乘次数最少为主要目标, 出行耗时最少(或出行距离最短 为次要目标的一个问题求解模型。求解模型的算法主要有改进的D

13、ijksta 算法和广度优先搜085吉林大学学报(信息科学版 第27卷索或深度优先搜索算法4, 5。传统的D ijkstra 算法不适合公交网络中最短路径的选择。在公交网络中, 将每个公交站点看成网络上的顶点, 每相邻站点间的路段看作一条边。如果采用D ijkstra 算法, 要计算从站点A 到站点B 之间的最短距离, 只要网络图中两个顶点之间有边存在, 它就会进行搜索, 而不考虑换乘问题, 这样搜索的路径可能是从站点A 到站点B 距离最短的, 但可能需要换乘多次才能到达, 这样会增加时间和费用消耗。因为换乘次数少是大部分乘客出行时考虑的首要因素, 所以这样的路径对于司机来说非常有用, 但对乘

14、客却不是最佳选择。改进的D ijkstra 算法可以借助于最小换乘次数矩阵, , 但D ijkstra 最短路径算法要求网络拓扑图简洁, 对于复杂的公交网络拓扑, 网络拓扑图, 这无疑增加了程序的复杂性。, 增加了算法不必要的执行次数。, , 用数据库表示公交网络, 6, 完全可以满足用户出行查询的需求。选择算法4广度优先搜索遵循从初始结点开始一层层扩展, 直到找到目标结点的搜索规则, 它只能较好地解决顶点不是很多、层次不是很深的情况。如果扩展结点较多, 而目标结点又处在较深层, 搜索量巨大, 往往就会出现内存空间不够用的情况, 影响算法的执行效率。双向搜索对广度优先的搜索方式进行了改进, 在

15、路径的搜索过程中, 初始结点向目标结点和目标结点向初始结点同时进行扩展, 直至在两个扩展方向上出现同一个子结点, 搜索结束。出现的这个同一子结点, 称之为相交点。如果确实存在一条从初始结点到目标结点的最短路径, 则按双向搜索进行搜索必然会出现“相交”, 即有相交点, 所求路径为:初始结点相交点目标结点。双向搜索对广度优先搜索加入了一定的“智能因素”, 使搜索能尽快接近目标结点, 减少了在空间和时间上的复杂度。笔者对双向广度优先搜索算法进行了改进, 把集合的思想和广度优先搜索方法相结合, 采用从两端集合同时逐步向外扩展和两个集合之间逐渐逼近, 直到两个集合有交集出现的搜索方法。集合可以是线路集合

16、也可以是站点集合。在一个庞大的交通网络中, 此方法能较块地寻找出基于最少换乘的最短路径。为了便于表明算法, 有如下规定:1 所有线路集合R =R i |i =1, 2, , n; 所有站点集合S =S i |i =1, 2, , m ; 2 R (S i 为经过站点S i 的所有线路集合, S i S; S (R i 为线路R i 上所有站点集合, R i R; 3 V (R i , R j 为R i 和R j 共同经过的站点集合, R i , R j R; 4 L (R, S 为R 中经过站点S 的线路集合; 5 矩阵C 为行、列交叉的二维表, 行为线路、列为站点, C =C ij |R i

17、 R, S j S, i =1, 2, , n, j =1, 2, , m , 且若R i 经过站点S j , 则C ij =1, 否则C ij =0。算法步骤如下。1 分别建立经过起始站点V O 、终点站点V D 的线路集合R (V O 和R (V D 。2 如果R 0=R (V O R (V D <, 则V O 到V D 可直达, 所乘线路为R 0中的任意一条, 路径为:V O R 0V D , 转到步骤7 ; 否则要换乘, 执行步骤3 。3 建立R (V O 、R (V D 中所有线路经过的站点集合S (R (V O 和S (R (V D 。4 如果S 1=S (R (V O S

18、(R (V D <, 则V O 到V D 经过一次换乘可到达, 一次换乘路径为:V OL (R (V O , S 1 S 1L (R (V D , S 1 V D , 转到步骤7 ; 否则需要两次或多次换乘, 执行步骤5 。5 分别建立与R (V O 和R (V D 中线路相交的线路集合R (R (V O 和R (R (V D 。6 如果R 2=R (R (V O R (R (V D <, 则V O 到V D 经过两次换乘可以到达。设V 21=V (R (V O ,185第6期张玉春, 等:基于双向搜索的公交路径选择算法及优化模型R 2 , V 22=V (R (V D , R 2

19、 , 两次换乘路径为:V O L (R (V O , V 21 V 21R 2V 22L (R (V D , V 22 V D , 转到步骤7 ; 否则要经过多次换乘, 认为不可到达。7 由上述步骤得到的路径是基于最小换乘次数的。路径如果有一条, 即为最优路径, 如果有多条, 求出每条路径的出行耗时或出行距离, 值最小的即为最优路径。5算法示例设有一个包含7条公交线路的公交网, 其线路矩阵如表1所示。表1线路矩阵Tab 11L ine S 1S 2S 3S 4S 5S 67S 89S 10S 11R 11111R 21R 31R 411R 5111R 6111R 711111选择起点为S 1,

20、 终点为S 7的有效路径, 其步骤如下。1 由线路表可知, 起点线路集合R (S 1 =R 1, R 4, 终点线路集合R (S 7 =R 5, R 6。2 R 0=R (S 1 R (S 7 =<, 表明从S 1到S 7要换乘。3 R (S 1 中所有线路上站点集合S (R (S 1 =S 1, S 2, S 3, S 4, S 5, S 9, S 10, R (S 7 中所有线路上站点集合S (R (S 7 =S 6, S 7, S 8, S 10, S 11。4 S 1=S (R (S 1 S (R (S 7 =S 10, 则从S 1到S 7一次换乘可到达, 路径为:S 1L (R

21、 (S 1 , S 10 S 10L (R (S 7 , S 10 S 7, 具体路径是:S 1R 4S 10R 5S 7。5 与R (S 1 中线路相交的线路集合R (R (S 1 =R 2, R 5, R 7, 与R (S 7 中线路相交的线路集合R (R (S 7 =R 3, R 4, R 7。6 R 2=R (R (S 1 R (R (S 7 =R 7, 则S 1到S 7经过两次换乘也可到达。V 21=V (R (S 1 , R 7 =S 3, S 4, S 9, S 10, V 22=V (R (S 7 , R 7 =S 10, S 11, 路径可表示为:S 1L (R (S 1 ,

22、 V 21 V 21R 2V 22L (R (S 7 , V 22 S 7, 共有8条, 分别为:S 1R 1S 4(或S 9 R 7S 10R 5S 7; S 1R 1S 4(或S 9 R 7S 11R 6S 7; S 1R 4S 3(或S 10 R 7S 10R 5S 7; S 1R 4S 3(或S 10 R 7S 11R 6S 7。6综合评价指数模型乘客选择公交线路的主要依据是线路交通阻抗。公交线路交通阻抗值是指乘客在公交线路上出行的出行时间、费用、方便性(如换乘 等综合费用指数。由上述可知, 从S 1到S 7经过一次换乘或两次换乘都可以到达。如果是基于最小换乘次数, 步骤4 得到的路径

23、是最优路径。但如果基于最少出行耗时或最短出行距离, 步骤4 得到的路径不一定是最优的。1999年在南京市的8个主要公交站点进行了一次出行时首选考虑因素的心理问询调查, 调查结果是41116%的乘客首选换乘最少, 30193%的乘客首选耗时最少10。笔者给出了一个综合考虑换乘次数、出行时间和出行费用的综合评价指数模型, 分别计算出每条路径的综合评价指数, 其值最小的路径既为最优路径。定义路径的综合评价指数M in:(R k =1T k +2M ks . t . T k =t c k +t b k +t d k +t hk 1+2=1285吉林大学学报(信息科学版 第27卷t c k =s k i

24、 =1t ck i ; th k =n k t h ; M k =n k +1i =1m k i其中R k 表示第k 条可行路径, 由s k (s k >0 个相邻路段组成, T k 和M k 分别表示路径R k 上的出行耗时和出行费用。T k 包括乘车时间t c k (行驶时间和停站时间 、步行时间t b k 、等车时间t d k 和换乘耗时t h k 。t c k i 为第i 条路段的乘车时间, n k (n k =0, 1, 2 为换乘次数, t h 为平均换乘时间, m k i 为第i 条路线的票价, 共有n k +1条线路。1和2表示权重, 1=1表示注重时效性; 2=1表示注

25、重经济性; 10且20表示注重综合性11。为换乘代价因子, 。通过求解最小的出行时间达到抑制换乘的作用。的程度确定。损失程度越大, 越不方便, 则值越大。在综合评价指数模型中含有不同指数, 其量纲也不同M k 转化为时间价值H k , 采用居民人均国民收入值进行转换12H k =M k ×480××26010000=1215M k (m in k (1, , 的综合评价指数, 取值最小的路经为最优路经。综合评价指数值越小, 、费用也越小, 也即说明路径越优。, 假设从起始站点S0148到目的站点S0485有两条可行路径, 一次换乘路径R 1和两次换乘路径R 2。为

26、了简化计算, 在这里忽略步行时间和等车时间, 根据综合评价指数模型计算的指数值如表2所示。表2站点S0148S0485路径的综合评价指数值Tab 12Stand S0148S0485r oute compound evaluati on index1(R 1 (R 2 03715621501571157515110106108810其中R 1的出行耗时为106m in, 出行费用为3元; R 2的出行耗时为88m in , 出行费用为5元。结果表明, 当1=0时, 注重经济性, 最优路径为R 1; 当1=015时, 注重综合性, 最优路径为R 1; 当1=1, 注重时效性, 最优路径为R 2。

27、这与实际生活中乘客选择出行路径的想法吻合。7结语笔者应用该算法建立了一个长春市公交查询仿真系统。该系统基于V isual Basic 610开发环境, 数据库采用M icr os oft Access2003。系统拥有近100条线路、600个站点, 权重值1和2可由乘客决定。在寻求任意给出的两个站点之间最佳路径时, 运算速度较快, 所选路径合理。由于在建模过程中简化了许多实际因素, 过于理想化, 因此, 要想建立更好的公交查询系统, 还需要把模型进一步复杂化, 并加入一些实时因素, 充分体现交通网络的动态变化特性, 更加逼真地模拟公交网络, 以满足乘客的需求。参考文献:1王建林. 基于换乘次数

28、最少的城市公交网络最优路径算法J .经济地理, 2005, 25(5 :6732676.WANG J ian 2lin . The Public Trans portati on Op ti m u m Route A lgorith m Based on the Least Transfer J .Econom ic Geography, 2005, 25(5 :6732676.2陈箫枫, 蔡秀云, 唐德强. 最短路径算法分析及其在公交查询的应用J .工程图学学报, 2001(3 :20224.CHE N Xiao 2feng, CA I Xiu 2yun, T ANG De 2qiang

29、. Shortest Path A lgorith m Analysis and Its App licati on t o Bus Route Query J .Journal of Engineering Graphics, 2001(3 :20224.3刘光明, 蔡先华, 苗聪, 等. 一种城市公交查询的算法及其应用J .交通运输工程与信息学报, 2005, 3(2 :872385第6期张玉春, 等:基于双向搜索的公交路径选择算法及优化模型584 91. 吉 林 大 学 学 报 (信 息 科 学 版 第 27 卷 4 向万里 , 刘洪升 . 城市公交网络出行路径选择的计算机算法研究 J

30、. 兰州交通大学学报 : 自然科学版 , 2006, 25 X I NG W an 2li, L I Hong2sheng Computer A lgorithm of Route Choice of Trip in U rban Transit Network J . Journal of A U . 40 (3 : 763 2 766. 87 2 91. 340 2 344. I p roved A lgorithm Based on Relational Database Technology for Querying m CHEN Hao, N I G Hong2yun. Shorte

31、st Path Searching A lgorithmbased on Set Calculation J . Computer Engineering, 2007, N on Compound Evaluation Index J . Journal of J ilin University: Infor mation Science Edition, 2008, 26 ( 2 : 180 2 185. neering and Infor mation, 2007, 5 ( 1 : 22 2 27. 33 ( 20 : 199 2 203. 2008, 26 ( 2 : 180 2 185

32、. Southeast University: Natural Science Edition, 2000, 30 ( 6 : 87 2 91. Transit Network J . Journal of Central South University: Science and Technology, 2009, 40 ( 3 : 763 2 766. network J . Journal of J ilin University: Engineering and Technology Edition, 2006, 36 (3 : 340 2 344. J . Journal of Tr

33、ansportation Engineering and Information, 2008 ( 4 : 118 2 125. YANG Xin 2 iao, WANG W ei, MA W en2teng GIS Based Public Transit Passenger Route Choice Model J . Journal of m . ( 1 : 121 2 124. 5 伍雁鹏 , 彭小奇 , 杨恒伏 . 改进的基于关系数据库技术的公交查询算法 J . 中南大学学报 : 自然科学版 , 2009, WU Yan2 peng, PENG Xiao 2qi, YANG Heng2

34、fu. 6 白子建 , 赵淑芝 , 田振中 . 公共交通网络优化的禁忌算法设计与实现 J . 吉林大学学报 : 工学版 , 2006, 36 ( 3 : 7 王世祥 , 饶维亚 . 数据库系统中公交网络换乘线路的优化选择模型 J . 计算机系统应用 , 2008 ( 4 : 112 2 116. 8 张晋伟 , 邹云 . 公交网络最优线路查询模型及软件开发 J . 交通运输工程与信息学报 , 2008 ( 4 : 118 2 125. 9 陈 昊 , 宁红云 . 基于集合运算的最短路径搜索算法 J . 计算机工程 , 2007, 33 ( 20 : 199 2 203. 12 胜学 , 范炳全 . 公交网络最优路径求解算法 J . 交通运输工程与信息学报 , 2007, 5 ( 1 : 22 2 何 27. puter System s App lications, 2008 ( 4 : 112 2 116. 10 新苗 ,