基于 GIS的公交数据模型研究及换乘算法实现

付仲良,张文元,孟庆祥

(武汉大学遥感信息工程学院,湖北武汉 430079)

基于 GIS的公交数据模型研究及换乘算法实现

付仲良,张文元,孟庆祥

(武汉大学遥感信息工程学院,湖北武汉 430079)

针对公交出行中的一些实际问题,设计一种用 GIS矢量数据结构表达公交网络数据位置和关系的公交数据模型,在此基础上实现了以最少换乘次数为第一目标、最少途经站数为第二目标的公交换乘算法。该算法不仅解决了步行换乘、环路换乘等问题,而且优化了换乘点的选择。此外,利用数据库和空间数据引擎的索引和快速检索性能,并结合基于内存的查询、集合运算等高效处理机制,有效地解决了算法的效率问题,并应用于实践。

GIS;数据模型;公交换乘;换乘次数;途经站数

一、引 言

公共交通是各大城市市民出行的首选交通工具,面对错综复杂的交通网络,如何选择最优的乘车线路是广大市民面临的一个难题。因此,开发智能公交查询系统或者推行基于网络电子地图的公交查询服务显得越来越重要。

公交换乘查询就是要快速、准确地搜索网络上两点之间的最优乘车路径。现有的很多公交换乘算法都是将公交站点、公交线路的地理位置作为属性字段存储到关系数据库或文件中,然后采用最短路径算法、矩阵运算或者链表查询等方式求解换乘路径,如廖楚江等使用“图论”和空间网络数据库相结合的方法实现了一种基于最少换乘次数的算法[1];翁敏等使用关联矩阵实现最优换乘路径求解[2];杨新苗等设计了一种基于链表的公交乘客出行路径选择模型[3]。这些算法有些计算复杂,效率低下;有些没有考虑步行换乘、上下行线路、环形线路、最优换乘点选择等实际问题。

公交出行与很多因素相关,大量调查研究表明,换乘次数、出行距离、出行时间和出行费用是当今乘客选择公交出行的主要影响因素[4]。结合公交乘客出行心理的考虑,一般都是以换乘次数为优先考虑目标[3];在换乘次数最少的情况下,相对出行时间和费用等具有随机性的因素,乘客往往选择直观、易量算的出行距离作为第二考虑目标[5]。本文充分利用 GIS在空间数据表达、存储和查询等方面所具有的强大优势,设计了一种基于 GIS矢量数据结构的公交网络数据模型,并在此基础上实现了一种以最少换乘次数和最少途经站数为目标的高效公交换乘算法,用于解决步行换乘等实际难题。

二、公交数据模型的 GIS表达

公交换乘查询是建立在公交实体的详细表述基础之上的。公交数据结构的设计直接影响到算法的执行效果,合理的公交数据结构可以减少搜索次数,提高搜索效率[6]。大中城市的公交数据量大、线路复杂,考虑到公交站点和线路数据的维护、更新及换乘算法的效率,本文设计了一种空间数据和属性数据相结合的公交数据模型。其中,公交站点、公交路段等空间数据以 Geodatabase矢量数据模型存储;公交线路属性信息、线路与站点之间的关系则以关系数据库表的形式存储。空间数据和属性表之间通过关键字段关联,共同表达复杂的公交网络结构。

公交站点 (BusStop)对应一个矢量点状要素图层,主要存储每个公交站点的编号、名称和坐标等信息,该图层的主要字段如表 1所示。其中,Stop-Name ID字段主要用于标识同名站点,以便于算法解决步行换乘问题。所谓同名站点是指那些空间位置邻近且名称相同(或稍有不同)的站点,例如火车站前站、火车站后站等。在数据预处理过程中,设两站点间的距离为 d,同名站点之间的距离阈值为w,根据乘客的实际行为和相邻站点间的平均距离,取w=150 m,以此作为缓冲半径,利用 GIS的缓冲区分析功能将 d≤w的站点归纳为同名站点,赋予相同的 StopName ID值。

表1 BusStop字段说明

公交路段(BusLine)为矢量线状要素图层,用于存储两个相邻且有公交车直达的站点之间的路段位置信息,其主要字段如表 2所示。对于两个相邻站点之间的路段,如果从起点到终点和从终点到起点的行车路线相同,则只存储为一个要素;否则按照起止点的顺序不同,作为两个要素分别存储。多条通过该路段的公交线路均可共享该路段数据,这样可以减少数据冗余。

表 2 Bus L ine字段说明

公交线路属性表(BusRoute)用于存储各条公交线路的编号、名称、开班—收班时间等信息,其字段信息见表 3。每条公交线路都有上行和下行之分,但在BusRoute表只存储为一条记录,其上下行信息在下面的线路站点关系表中予以区分。

表3 BusRoute表结构

线路站点关系表 (RouteStop)存储各公交线路所经过的站点以及每个站点在上行和下行线路中的序号等信息,为公交换乘查询的核心表,其结构及示例数据如表4所示。

表 4中 SegUp、SegDn分别表示站点在线路上行、下行中的序号,-1表示不经过该站点;Line-IDUp、Line IDDn则记录站点和上行(下行)线路中相邻下一站点间的路段编号,无相邻下一站点,则该值为空。以表中 Route ID=1的线路 (图 1)为例,其上行线路经过的站点依次为:1—2—3—4—6,对应的公交路段编号依次为:01—03—04—05;下行线路经过的站点依次是:6—5—3—2—1,路段编号依次是:10—08—03—02。根据站点编号和路段编号可以分别解析出站点名称和上下行线路的位置信息,可在地图上对上下行线路加以区分。

表 4 RouteStop示例数据

图1 公交线路示意图

三、公交换乘算法实现

1.算法概述

为了便于公交换乘算法的描述,现将公交数据模型作如下数学定义:

定义 1:设V表示公交站点的集合,vi为第 i个公交站点,集合V表示为

定义 2:设 R表示经过某个公交站点 v的公交线路集合,ri为第 i条公交线路,集合 Rv表示为

定义 3:若 r表示某条公交线路,vri是该线路经过的站点,则 r可表示为

定义 4:设L表示某条公交线路的所有路段集合,lj为第 j条公交路段,集合L表示为

定义 5:从给定起始站点 vo通过 N次换乘能够到达目标站点 vd的可行公交换乘路径集合为 TR, TR表示为

其中,TRi为第 i条换乘方案,表示在起点 vo选择线路 ri1到达站点 vi1,换乘线路 ri2到达 vi2,…,最终到达 vd,该路径换乘次数 N。在本算法中,设定 0≤N≤2,即最多进行两次换乘,超过两次的换乘则认为两站点间没有可行的换乘方案,建议改用其他交通工具;为了提高算法效率,控制换乘方案数量 n≤10,即最多给出 10条可行的最优换乘方案供用户选择。

2.算法流程和步骤

基于以上定义和描述,设计的换乘算法流程如图2所示。

图2 公交换乘算法流程图

结合以上流程图,算法实现步骤如下:

1)在表 RouteStop中搜索经过起始站点 vo的线路集合 Ro和经过目标站点 vd的线路集合 Rd;

2)∀r(i)∈Ro,搜索线路 r(i)上行 (下行)中站点 vo之后的所有站点集 Vo(i),记 Vo(i)={vi1, vi2,…,vik}。则从 vo能够直达的所有站点集合Vo= {Vo(i)|i=1,2,…,m}。

3)直达搜索。∀Vo(i)∈Vo,如果 vd∈Vo(i),则 Vo(i)对应的线路 ri为直达线路,直达路径记为TRi=〈vo,ri,vd〉。所有元素比较完后,形成直达路径集合 TR0={TRi|i=1,2,…,n}。若 TR0≠ φ,则转入 6),否则转入 4)。

4)一次换乘搜索。思路如下:

a.∀r(j)∈Rd,搜索线路 r(j)从上行 (下行)起点到 Vd的所有站点集 Vd(j),记 Vd(j)={vj1,vj2,…,vjm}。能够直达 vd的所有站点集合为 Vd= {Vd(j)|j=1,2,…,t}。

b.∀Vo(i)∈Vo,∀Vd(j)∈Vd,设 Vc=Vo(i)∩Vd(j),如果 Vc≠φ,则存在一次换乘路径,Vc为换乘点集;∀vk∈Vc,分别获取换乘前后的公交线路 r1和 r2,形成一条换乘路径 TRk=〈vo,r1,vk,r2,vd〉。所有元素比较完后,形成一次换乘路径集合 TR1= {TRi|i=1,2,…,n}。若 TR1≠φ,则转入 6),否则转入5)。

5)二次换乘搜索。思路如下:

a.在 RouteStop表中分别搜索通过集合 Vo、Vd中任一站点的所有不同线路,形成线路集合 R1和R2;设 Rm=R1∩R2,如果 Rm≠φ,则存在中间换乘线路,否则转入 7)。

b.搜索集合 Rm中每条线路所经过的站点,形成中间换乘线路的站点集合Vm。

c.∀Vo(i)∈Vo,∀Vm(j)∈Vm,设Vc1=Vo(i)∩Vm(j),若 Vc1≠φ,则 Vc1为第一次换乘站点集合;然后继续将 Vm(j)同 Vd中的每个元素 Vd(k)比较,设 Vc2=Vm(j)∩Vd(k),若 Vc2≠ φ,则 Vc2可作为第二次换乘站点集合,此时存在二次换乘路径,记为 TRi=〈vo,ri1,vc1,ri2,vc2,ri3,vd〉。所有元素比较完后,形成二次换乘线路集合 TR2={TRi|i =1,2,…,n}。若 TR2≠φ,则转入 6),否则转入7)。

6)结果解析。对集合 TR中的每个元素 TRi,求出途经的总站点数 Si,然后按照 Si从少到多的顺序对 TRi进行排序;再根据排序后 TRi中记录的站点编号、线路编号依次解析出站点、线路的名称,形成每条换乘方案的文字描述信息;与此同时,根据每条直达线路 ri对应的路段集合 L,利用 L中每条路段 lj的编号 Line ID,通过 GIS中的空间查询函数快速获取该换乘路径的坐标信息,用于在地图上标识对应的换乘线路。至此,算法结束。

7)如果二次换乘无搜索结果,则算法结束,返回所查询的两个站点之间无公交换乘方案。

3.算法特点

1)效率高。在进行公交换乘搜索前,首先将表RouteStop中查询出的通过起始点或者目标点的所有记录读入内存,形成缓存数据表,后续的部分数据查询、结果解析都是在该缓存表中进行搜索,相比每次都从包含所有记录的物理表 RouteStop中查询,这种技巧不仅可以提高算法效率,而且还可以减少对数据库中原始表的频繁操作,避免游标溢出问题。

2)支持步行换乘。现有的很多换乘算法要么没有考虑步行换乘,要么就是将距离临近的多个公交站点提取为一个站点来实现步行换乘。即使是后一种情况,也无法获得步行换乘时下车站点和上车站点的具体名称和步行距离。本算法在公交数据中增加了标识同名站点的 StopName ID字段。换乘搜索时,利用 StopName ID(而非 Stop ID)来判断两条线路是否有站点交集。若交集非空,再获取 StopName ID在不同线路中对应的 Stop ID。若 Stop ID不同,则两个 Stop ID对应的站点为步行换乘站点,可以获取具体的下车、上车站点名称,还可以利用 GIS函数计算这两个站点间的距离,即用户需要步行换乘的距离。

3)区分了线路上、下行和环路问题。本算法在搜索每条线路 r经过的站点集合时,都是按照上、下行次序分别组织成上行站点集合V r1和下行站点集合Vr2,将其作为线路集合 R对应的站点集合 V中的两个独立元素,并在每个元素中增加线路 ID和上、下行标记符。当判断出元素 V r(i)和另一站点集合中的元素 Vk(j)有交集时,通过解析元素的标记符不仅可以快速获取换乘前后线路编号,而且可以区分线路的上、下行。对于可以同时从两边发车的环线(起点和终点相同,如图 3所示),可以将一个方向(A—B—C)看作上行线路,另一个方向(A—F—E—D—C)看作下行线路。当搜索到该线路时,只需比较上行或下行哪个途经的站点少,即可舍弃其中的以一种,获得最优的环路换乘方案。

图3 公交环线示意图

4)最优换乘点选择。进行一次换乘和二次换乘搜索时,当两条具有相交关系的线路存在多个相交站点时,如何选择换乘站点以保证出行距离最短也是一个需要考虑的现实问题。以图 4为例,线路 1 (A—B—C—D—E)和线路 2(F—D—C—B—G)存在 3个相交站点(B,C,D),查询A站到 G站的换乘线路时,B、C、D都可以作为换乘点,但经B站换乘途经总站数为 2(A—B—D),而经D站换乘则需要坐 6站 (A—B—C—D—C—B—G),显然 B站是最合理的换乘站点。本算法在换取两条线路的换乘点集后,可以快速统计出从起点站到每个换乘点再到目标站途经的总站数,然后取总站数最少的那个换乘站点作为最优换乘点。对于其他的线路相交情况,也可以用该方法统一处理。

图4 两条线路相交示意图

三、公交换乘算法应用实例

本算法目前已应用到了山东省网通公司的 114电话导航WebGIS平台。公交数据统一存储到Oracle数据库中,其中,空间数据通过空间数据引擎ArcSDE进行高效访问,属性数据通过ADO.NET来访问。系统根据客户端传入的起止站点,在换乘次数最少的情况下,优先给出途经总站点数较少的多条换乘方案供用户选择。点击每条换乘方案,还可以在地图上清晰标识出该换乘线路、起始点、换乘点和目标点的位置信息,直观地展现给用户,结果如图5所示。

图5 公交换乘查询结果

在对公交换乘算法的效率测试中,选用济南市目前拥有的 158条公交线路、1 373个公交站点作为测试数据,搜索直达方案平均耗时在 0.5 s以内,一次换乘搜索时间一般不超过 1.3 s,二次换乘搜索耗时在 2 s左右。总体来说,算法效率较高,能够满足114客户快速查询响应的要求。

四、结 论

公交网络模型通过 GIS空间数据来表达更加符合现实公交路网情况,在此基础上设计的公交换乘最优路径算法,充分利用了Oracle数据库和ArcSDE在索引、SQL查询和空间坐标获取方面的优异性能,并结合基于内存的数据表查询、字符串快速拆分和查找机制,不仅为求解大中城市乘客的公交出行难题提供了一种高效、快捷的解决方案,而且在步行换乘、上下行和环形线路区分、最优换乘点选取等实际问题上进行了优化处理,能够弥补现有许多算法在查询效率和准确性方面的不足。由于公交出行的实际情况非常复杂,许多因素还有待考虑,如换乘的难易、时间和费用因素等,这些方面仍需进一步的研究和探索。

[1] 廖楚江,蔡忠亮,杜清运,等.基于最少换乘的公交最优路径算法的设计与实现[J].武汉大学学报:信息科学版,2006,31(10):904-907.

[2] 翁敏,毋河海,杜清运,等.基于公交网络模型的最优出行路径选择的研究[J].武汉大学学报:信息科学版,2004,29(6):500-503.

[3] 杨新苗,王炜,马文腾.基于 GIS的公交乘客出行路径选择模型[J].东南大学学报:自然科学版,2000,30 (6):87-91.

[4] 王庆平,张兴芳,宋颖,等.城市公交换乘的数学模型及其算法实现[J].计算机工程与应用,2008,44(7): 246-248.

[5] 向万里,刘洪升.城市公交网络出行路径选择的计算机算法研究 [J].兰州交通大学学报:自然科学版, 2006,25(1):121-124.

[6] 黄正东.公交实体的详细表达及其在出行系统中的应用[J].武汉大学学报:工学版,2003,36(3):69-75.

A Study of BusData M odel and Transfer Algorithm Based on GIS

FU Zhongliang,ZHANGWenyuan,MENGQingxiang

0494-0911(2010)07-0015-04

P208

B

2009-12-22

付仲良(1965—),男,湖北麻城人,教授,博士生导师,主要研究方向为 GIS、图像处理与分析。