基于换乘次数最少的城市公交网络最优路径算法.pdf

《基于换乘次数最少的城市公交网络最优路径算法.pdf》由会员分享，可在线阅读，更多相关《基于换乘次数最少的城市公交网络最优路径算法.pdf（4页珍藏版）》请在三一文库上搜索。

1、文章编号:1000 - 8462(2005)05 - 0673 - 04 基于换乘次数最少的城市公交网络最优路径算法 王 建 林 (浙江交通职业技术学院,中国浙江 杭州 311112) 摘 要:依据对公交乘客出行心理调查的统计结果,指出换乘次数最少是乘客出行时考虑的首要因素。描述了传 统的Dijkstra算法,并分析了Dijkstra算法不适合公交网络最优路径选择的原因。最后根据公交乘客可以步行小段 距离再转车的实际情况,提出一种基于换乘次数最少的公交最短路径改进算法。 关键词:公交网络;换乘次数;最优路径算法 中图分类号:F294.3文献标识码:A 1 公交乘客出行心理研究 在城市电子地图中

2、,公共交通信息模块是必不可少的,它 为各种交通信息的查询、 统计提供方便直观的手段,为市民的 出行提供了方便。在研究公交网络模型和最优路径算法时, 有必要先了解公交乘客出行时所考虑的因素,通过对公交乘 客出行心理、 行为的研究来确定模型的优化目标和约束条件。 通常乘客选择出行路线时受到以下几个因素的作用:“换乘次 数” 、“出行距离” 、“出行耗时” 、“出行费用” 。换乘次数是指乘 客在完成一次出行过程中所换车的次数。出行距离则包括车 上距离和车外距离,车外距离指的是乘客为了乘车而步行的 距离,比如说从起点到上车站台的距离、 中途换车所步行的距 离以及从下车站台到终点的距离。出行耗时指乘客在

3、一次出 行过程中所需的时间,它也包括车上和车外部分,车外耗时除 了在车外距离部分所耗的时间外还包括在车站等车的时间。 出行费用指的是乘客在完成一次出行过程中所花的车费。实 际上这几个出行因素是相互影响的,如换乘次数和出行费用 就是相关联的,特别是在一些实行一票制的城市中,这两个因 素可以说是一致的。 本文参照了在南京市做的一个公交乘客出行心理调查 统计结果1,它主要对三个因素做了调查:换乘次数、 出行距 离、 出行耗时。从图1中可以看到有41.16 %的乘客在选择出 行路径时首先考虑的是换乘最少,其次考虑时间最短,而将路 程最短作为出行时考虑的首要条件的乘客只占18.60 %。 2 城市公交网

4、络的特点 城市中公交汽车沿着道路运行,形成的公交线路网是建 立在道路网之上,依据道路建立的网络模型并不能直接应用 于公交网络,这是因为公交网络与道路网络相比有它的一些 特点。 2.1 连通性 在道路网络模型中,通常是将道路交叉点抽象成一个结 点,也就是说该结点连接着多条路段,路段与路段之间在该结 点处具有连通性。但在公交网络中,如果将公交站点视为结 点的话,那么同路公交线路在该点的连通性与不同公交线路 在该点的连通性是有差别的,这是因为不同路的公交线在同 一站点上的连通是需要换车而增加时间消耗的。另外多条公 交线路虽然可以相交于空间上的同一个点,但是该点不一定 是公交停靠站点,或者不是同时有停

5、靠点,在这种情况下不同 公交线路在这一点也不是连通的。 图1 公交乘客出行心理分析图 Fig.1 Psychology analysis of passengers trip 2.2 公交站点的特性 在公交线路网中,不同的公交线路在行程上一定会有重 叠,也就是说不同的线路上一定会有同名站点,但在公交站点 分布的实际情况中,即使是同名站点也存在空间位置相异的 情况。如果将一个公交站点视为一个结点,在进行网络分析 时,就要求把空间上相近的异线同名站点合理抽象成一个结 点。也就是在相应的网络图上不同属性的边在结点上连通, 这样才能模拟不同公交线之间的可换车情况。 2.3 公交网络中最短路径的意义 公

6、交乘客出行和汽车司机运货所考虑的因素是不同的, 汽车司机运货关心的是如何选择最近距离,最大程度的省时 省油;而公交乘客出行更多考虑的是出门的方便性和舒适性, 所以道路网络中的最短路径和公交线路的最短路径的意义是 不同的。道路网络中的最短路径只要找出两点之间路径距离 第25卷第5期 2005年9月 经 济 地 理 ECONOMIC GEOGRAPHY Vol.25 , No.5 Sep. , 2005 收稿日期:2005 - 03 - 12;修回日期:2005 - 06 - 10 为最短即可。但是在公交网络中,乘客不会为了寻找距离最 短路径而随意换车。因为从一条线路换乘到另一条线路是费 时又费力

7、的,在很多情况下,换乘另一趟车需要到另一个站 台,这就有一段的步行距离,而且在站台等车也是要消费时间 的。所以对于公交乘客来说,最短路径的意义并不在于路程 是否最短,而在于换乘的次数最少。 3 传统的Dijkstra最优路径算法 3.1 最优路径概念 地理网络的最优路径是指在地理网络中满足某种最优 化条件的一条路径。所谓最优化就是对于给定的目标函数和 约束条件使目标函数在约束条件下达到最大值或最小值4。 最优路径问题一直是计算机科学、 运筹学、 交通工程学、 地理信息科学等学科的一个研究热点。它是资源分配、 路线 设计及分析等优化问题的基础。很多网络相关问题,如最短 路径问题、 最可靠路径问题

8、、 最大容量路径问题、 可达性评价 问题和各种路径分配问题均可纳入这个问题的范畴之中。国 内外大量专家学者对此问题进行了深入研究。 有很多最优路径问题可以转化为最短路径问题,而且网 络最优化的其它许多问题也都可以转化为最短路径问题或 者用最短路径的算法作为其求解的子过程。最短路径不仅仅 指一般地理意义上的距离最短,还可以引申到其它的度量,如 时间、 费用、 线路容量等。相应地,最短路径问题就成为最快 路径问题、 最低费用问题等。比如司机用汽车运输货物从A 城到B城,他就会考虑走路程最短或者时间最少的道路。这 里所考虑的是路程最短问题或最快路径问题。又比如在两地 之间铺设煤气管道,则要根据地形、

9、 土壤、 是否经过江河、 泥 塘、 农田、 公路等各种情况,来选择铺设费用最小的铺设路线, 这是考虑费用的最短路径问题。经典的图论与不断发展完善 的计算机数据结构及算法的有效结合使得新的最短路径算 法不断涌现。对于最短路径的求解,狄克斯特拉提出的一个 算法是目前公认的最好的算法,现有的许多文献都对此作了 介绍。 3.2 传统的Dijkstra算法描述 Dijkstra算法是由著名的数学家EWDijkstra于1959年 首先提出来的。它是按路径长度递增的次序产生最短路径的 一种算法,该算法采用了在优化问题中常用的贪心技巧。贪 心算法在每一步都选择局部最优解以期望产生一个全局最 优解。采用Dij

10、kstra算法不仅求出从起点到终点的最短路径, 而且最后所得到的实际上是从起点到各顶点的最短路径。传 统的Dijkstra算法描述如下2: 假设用带权的邻接矩阵arcs来表示赋权有向图, arcsij表示弧上的权值,若不存在, 则置arcsij为 。S为已找到从始点v出发的最短路径 的终点的集合。Di表示从始点v到每个终点vi的最短路 径的长度。 3.2.1 初始化。置S为空集,Di的初值为: Di =arcsvviviV 3.2.2 选择vj,使得 Dj = minDi |viV-S vj就是当前求得的一条从v出发的最短路径的终点,令 S=Sj 3. 2.3 修改从v出发到集合V-S上任一顶

11、点vk可达的最短 路径长度。如果 Dj +arcsjk Dk 则修改Dk为: Dk =Dj +arcsjk 3. 2.4 重复操作(2)、(3)共n- 1次,由此求得从v到图上其 它各顶点的最短路径是依路径长度递增的序列。 3.3 传统的Dijkstra算法不适合公交线路查询的原因 Dijkstra最短路径算法由于其稳定性、 能适应网络拓扑的 变化,因而在计算机网络拓扑路径选择以及GIS中得到广泛 的应用。但是对公交网络来说,Dijkstra不适合公交线路的查 询算法3,其主要原因如下: 3.3.1 数据结构复杂。网络在数学和计算机领域中被抽象 为图,所以图的存储表示是其基础。一般而言,无向图

12、可以用 邻接矩阵和邻接多重表来表示,而有向图则可以用邻接表和 十字链表表示。由于公交网络在节点与连通性上有一定的特 殊性,如果采用现有的最短路径算法分析,所建立的公交线路 网络图的数据结构模型将是非常复杂的。 3.3.2 算法时间长。在实现Dijkstra算法的过程中,核心步 骤就是从未标记的点中选择一个权值最小的弧段,这是一个 循环比较的过程,如果不采用任何技巧,未标记点将以无序的 形式存放在一个链表或数组中。那么要选择一个权值最小的 弧段就必须把所有的点都扫描一遍,在大数据量的情况下,这 无疑是一个制约计算速度的瓶颈,而且传统的Dijkstra算法求 解最短路径问题运用了关联矩阵、 邻接矩

13、阵和距离矩阵,在存 储图形数据和进行运算时,需定义NN的数组,其中N为网 络的结点数,当网络的结点数较大时,将占用大量的计算机内 存,同时大数组运算起来是很浪费时间的4。 3.3.3 公交转车中的特殊性不一定要求用Dijkstra算法算出 一条最短路径。假设要计算乘客从站点A到站点B的最短 距离,将每个公交站点看成网络上的结点,每相邻站点间的路 段看作一条边。如果采用Dijkstra算法,只要网络图中两个结 点之间有边存在,它就会进行搜索,由于忽视了乘客在不同线 路上换车所付出了时间和费用代价,所计算出来的结果可能 是从站点A到站点B的距离是最短的,但需要转乘好几次车 才能到达,这样的结果对于

14、司机来说有着重要意义,但对乘客 却不是最佳选择。因为从前面的公交乘客出行心理研究报告 中可以看到,换乘次数少才是乘客出行时考虑的首要因素。 4 基于换乘次数最少的最优路径算法 在参考文献3中,作者提出了一种基于换乘次数最少的 最短路径算法,该算法比较符合人们出行时的心理情况。算 法的思想描述如下: 根据人们的出行习惯,在选择从A站到B站的行车线路 时,首先会先看经过A站的车是否有直接到B站的,如果有, 马上会选择直达车 ,( 如图2(a)如果存在不止一条的直达线 路,再考虑所走路线的远近,选择距离最近的乘车方案;如果 没有直达车,就会考虑换一次车的方案:即经过A站的车与 经过B站的车有公共站点

15、C吗?如果有,则可以在公共站点 C处转车(如图2(b) ;如果没有换一次车的方案,则又要考虑 476经 济 地 理 25卷 乘坐经过A点的车到某一站C下车,经过C站点的车与经过 B站点的车是否有公共站点D吗?如果有就再到D转车,两 次转车可到达 B( 如图2(c) ;如果没有,则需要转乘三次或三 次以上才可到达目的地(如图2(d)。在上述情况中如果存 在不止一种的选择方案,则再考虑乘车距离,选择路程最短的 乘车方案。 图2 公交线路换乘方案示意图 Fig.2 The transfer scheme of public transportation 5 基于换乘次数最少的最优路径改进算法 分析上

16、面的算法可以发现只有当不同线路之间具有公 共站点时才能够进行转车,这样计算出来的结果有时并不符 合实际情况,比如在实际出行时只需换乘二次便可到达目的 地,但计算出来的结果却需要换乘三次或四次。出现这种情 况的原因是忽视了现实生活中人们步行小段距离再转车的 现象。具体地说,人们在转车时,并不是下车后直接在下车的 站点处转车,往往需要步行一小段距离到附近的站点去转车。 人们选择这种方式通常可以减少换乘次数,而且这种换车方 式也是由站点的分布情况所决定的。参考文献5已详细分 析了紧邻站点的分布情况。紧邻是一个半定量的距离概念, 用以描述公交站点空间位置上的距离关系,通常是根据人们 的行为习惯和平均公

17、交路段长度来决定的。紧邻站点的存在 使得人们在选择换乘路线时多了一个考虑,就是如果在某一 站点下车后没有直接换乘的车次,还可以考虑附近的站点是 否有换乘车次。根据这种思想,本文对上面的算法进行了改 进,即在换乘时,加入对紧邻站点的判断和分析。这种算法更 加符合站点的分布情况以及人们出行时的实际选择情况。 从前面的公交乘客出行心理调查统计表可以看出,换乘 次数最少是公交乘客出行时考虑的第一重要因素,所以就以 换乘次数最少作为最优路径算法的第一约束目标,而出行耗 时最少虽是公交乘客考虑的第二重要因素,但因为其难以准 确测算,所以选择易于量化的出行距离最短作为第二约束目 标。 该算法的基本思想为分别

18、从起点A、 终点B出发,通过 比较公交网络上各车站的可换乘车站,追索A到B的可能路 径,然后比较各可能路径的距离,来确定最小成本路径。 设S(I) (I= 1 ,2 ,m) (m为正整数)为经过A或其附 近的线路集。 T(J) (J= 1 ,2 ,n) (n为正整数)为经过B或其附近 的线路集。 E(I,U) (U= 1 ,2 ,p,p为正整数)为线路S(I)上的 站点。 F(J,V) (V= 1 ,2 ,q,q为正整数)为线路T(J)上的 站点。 R(K) (K= 1 ,2 ,g) (g为正整数)为经过E(I,U)的 线路。 Y(O) (O= 1 ,2 ,z) (z为正整数)为经过F(J,V

19、)的 线路。 G(K,W) (W= 1 ,2 ,i) (i为正整数)为线路R(K) 上的站点。 L(O,X) (X= 1 ,2 ,j) (j为正整数)为线路Y(O)上 的站点。 d(m,n)表示站点m与站点n之间沿道路的距离。 w表示乘客在换车时步行距离的最大心理承受值,它是 一个人为干预的经验值,与公交站点间的平均长度呈线性相 关。对于站点m与站点n之间的紧邻关系,可以用一个不等 式来表示:d(m,n) =w。 根据经验表明,即使在上海这样的大都市的公交网络上, 换4次车即乘坐5条线路的公交车,方可到达目的地的情况 都是很少发生的6。所以根据杭州市公交线路的实际情况, 本文认为三次以内的转车

20、是比较合理的,超过三次的转车的 情况在这里不予考虑。算法的步骤如下: (1)输入乘车的起始站点A及目的站点B; (2)求经过站点A的所有线路集S(I)和经过站点B的所 有线路集T(J ) ; (3)判断S(I ) = T(J)吗? 如果有,则找到了从站点A到站点B的直达线路S(I)即 T(J ) , 输出结果,结束运算,如果没有则进行下一步。 (4)求线路S(I)上的站点E(I,U)以及线路T(J)上的 站点F(J,V ) ; 图3 改进算法流程图 Fig.3 The flow chart of amelioration algorithm (5)判断是否存在相同站点,即E(I,U ) = F

21、(J,V ) , 或 者存在紧邻站点,即满足d(E,F) =w; 如果满足E(I,U ) = F(J,V ) , 则线路S(I ) , T(J)即为 5765期 王建林:基于换乘次数最少的城市公交网络最优路径算法 一次转车的线路,E(I,U)即为转车站点且换车时不用更换 站点;如果满足E(I,U)F(J,V)但满足d(E,F) =w, 则线路S(I ) , T(J)即为一次转车的线路,E(I,U)即为转车 站点但换车时要步行到紧邻站点F(J,V)。如果没有,再执 行下面。 (6)求经过E(I,U)的线路集R(K ) , 经过F(J,V)的线 路集Y(O ) ; (7)判断R(K ) = Y(O

22、)吗? 如果有,则线路S(I ) , R(K ) , T(J)为两次换车的线路, 换车站点为E(I,U)和F(J,V ) , 输出结果,结束运算;如果 没有,则执行下面。 (8)求线路R(K)上的站点G(K,W)和线路Y(O)上的 站点L(O,X ) ; (9)判断是否存在相同站点,即G(K,W ) = L(O,X ) , 或 者存在紧邻站点,即满足d(G,L) =w; 如果满足G(K,W)=L(O,X ) , 则线路S(I ) , R(K ) , Y(O ) , T(J)即为三次转车的线路,E(I,U ) , G(K,W ) , F(J, V)即为转车站点,且换车时不用更换站点;如果满足G(

23、K, W)L(O,X)但满足d(G,L) =w,则在站点G(K,W) 转车时要步行到紧邻站点L(O,X)。 在上述情况中,满足条件的线路可能不止一种,这时再计 算每种方案的乘车距离,取距离最短的乘车方案,输出结果。 用图3表示算法流程图。 参考文献: 1 杨新苗,王 炜,马文腾.基于GIS的公交乘客出行路径选择模型 J .东南大学学报(自然科学版) ,2000 ,(6) :87 - 91. 2 严蔚敏,吴伟民.数据结构M.北京:清华大学出版社,1997. 158 - 159. 3 陈箫枫,蔡秀云,唐德强.最短路径算法分析及其在公交查询的 应用J .工程图学学报,2001 ,(3) :20 -

24、24. 4 王家耀.空间信息系统原理M.北京:科学出版社,2001. 275 - 276. 5 赵 玲.基于MAPINFO的城市公交信息查询系统的设计与实现 D.中南大学硕士论文,2003.10 - 17. 6 陈家治.ARCINFO路径寻找功能的拓展:双向比较追索法J . 上海师范大学学报(自然科学版) ,1996 ,(3) :78 - 83. THE PUBLIC TRANSPORTATION OPTIMUM ROUTE ALGORITHM BASED ON THE LEAST TRANSFER WANGJian - lin (Zhejiang Communication Vocation

25、al and Technical College ,Hangzhou 311112 ,Zhejiang ,China ) Abstract:This paper according as statistical result about psychology inquisition of passengers trip , pointed out that the least transfer is the most important when passengers go out. The paper described the traditional Dijkstra algorithm

26、, then analyzed the reason Dijkstra algorithm is not fit to optimum route selection of public transportation network. Finally , according as the fact that passengers walking to turntable usually , bring forward a public transportation optimum route amelioration algorithm based on the least transfer.

27、 Key words:public transportation network; transfer time ; optimum route algorithm 作者简介:王建林(1966 - ) ,男,浙江交通职业技术学院,讲师。主要从事道路工程方面的教学与研究。 (上接666页) THE APPLICATION OF THE“POINTAXIS SYSTEM”THEORY IN THE PLANNINGOF THE TRAFFIC ECONOMIC STRIP T AKING THE INDUSTRY PLANNINGOF THE NORTH ROAD INLVSHUN AS AN EX

28、AMPLE HAN Zeng - lin 1 ,LIU Wei 1 ,WANGLi 2 (1.Liaoning Normal University ,Center for Marine Economic and Sustainable Development ,Dalian 116029 ,Liaoning ,China ; 2.Liaoning Normal University ,Urban and Environment Department ,Dalian 116029 ,Liaoning ,China ) Abstract:This text takes the industry p

29、lanning of the north road in Lvshun as an example , specifically studies the application of the“point axis system”theory in the traffic economic strip. Firstly , analyses the planning background and the problems of the north road economic strip , importantly research the present condition of the ind

30、ustry planning along the north road inLvshun , thenforecasts and evaluates to the future in2 dustry planning of the economic strip , at last discusses the function of the“pointaxis system”theory to the planning of the traffic economic strip. Key words:the“pointaxis system”theory; the traffic economic strip ; the north road in Lvshun; the industry planning 作者简介:韩增林(1956 - ) ,男,山东商河人,博士生导师。主要从事交通运输与物流研究。刘 伟(1980 - ) ,女,辽宁北票人,在 读硕士研究生。主要从事区域开发与规划研究。 676经 济 地 理 25卷