付仲良,張文元,孟慶祥

(武漢大學(xué)遙感信息工程學(xué)院,湖北武漢 430079)

基于 GIS的公交數(shù)據(jù)模型研究及換乘算法實(shí)現(xiàn)

付仲良,張文元,孟慶祥

(武漢大學(xué)遙感信息工程學(xué)院,湖北武漢 430079)

針對(duì)公交出行中的一些實(shí)際問題,設(shè)計(jì)一種用 GIS矢量數(shù)據(jù)結(jié)構(gòu)表達(dá)公交網(wǎng)絡(luò)數(shù)據(jù)位置和關(guān)系的公交數(shù)據(jù)模型,在此基礎(chǔ)上實(shí)現(xiàn)了以最少換乘次數(shù)為第一目標(biāo)、最少途經(jīng)站數(shù)為第二目標(biāo)的公交換乘算法。該算法不僅解決了步行換乘、環(huán)路換乘等問題,而且優(yōu)化了換乘點(diǎn)的選擇。此外,利用數(shù)據(jù)庫(kù)和空間數(shù)據(jù)引擎的索引和快速檢索性能,并結(jié)合基于內(nèi)存的查詢、集合運(yùn)算等高效處理機(jī)制,有效地解決了算法的效率問題,并應(yīng)用于實(shí)踐。

GIS;數(shù)據(jù)模型;公交換乘;換乘次數(shù);途經(jīng)站數(shù)

一、引 言

公共交通是各大城市市民出行的首選交通工具,面對(duì)錯(cuò)綜復(fù)雜的交通網(wǎng)絡(luò),如何選擇最優(yōu)的乘車線路是廣大市民面臨的一個(gè)難題。因此,開發(fā)智能公交查詢系統(tǒng)或者推行基于網(wǎng)絡(luò)電子地圖的公交查詢服務(wù)顯得越來(lái)越重要。

公交換乘查詢就是要快速、準(zhǔn)確地搜索網(wǎng)絡(luò)上兩點(diǎn)之間的最優(yōu)乘車路徑?，F(xiàn)有的很多公交換乘算法都是將公交站點(diǎn)、公交線路的地理位置作為屬性字段存儲(chǔ)到關(guān)系數(shù)據(jù)庫(kù)或文件中,然后采用最短路徑算法、矩陣運(yùn)算或者鏈表查詢等方式求解換乘路徑,如廖楚江等使用“圖論”和空間網(wǎng)絡(luò)數(shù)據(jù)庫(kù)相結(jié)合的方法實(shí)現(xiàn)了一種基于最少換乘次數(shù)的算法[1];翁敏等使用關(guān)聯(lián)矩陣實(shí)現(xiàn)最優(yōu)換乘路徑求解[2];楊新苗等設(shè)計(jì)了一種基于鏈表的公交乘客出行路徑選擇模型[3]。這些算法有些計(jì)算復(fù)雜,效率低下;有些沒有考慮步行換乘、上下行線路、環(huán)形線路、最優(yōu)換乘點(diǎn)選擇等實(shí)際問題。

公交出行與很多因素相關(guān),大量調(diào)查研究表明,換乘次數(shù)、出行距離、出行時(shí)間和出行費(fèi)用是當(dāng)今乘客選擇公交出行的主要影響因素[4]。結(jié)合公交乘客出行心理的考慮,一般都是以換乘次數(shù)為優(yōu)先考慮目標(biāo)[3];在換乘次數(shù)最少的情況下,相對(duì)出行時(shí)間和費(fèi)用等具有隨機(jī)性的因素,乘客往往選擇直觀、易量算的出行距離作為第二考慮目標(biāo)[5]。本文充分利用 GIS在空間數(shù)據(jù)表達(dá)、存儲(chǔ)和查詢等方面所具有的強(qiáng)大優(yōu)勢(shì),設(shè)計(jì)了一種基于 GIS矢量數(shù)據(jù)結(jié)構(gòu)的公交網(wǎng)絡(luò)數(shù)據(jù)模型,并在此基礎(chǔ)上實(shí)現(xiàn)了一種以最少換乘次數(shù)和最少途經(jīng)站數(shù)為目標(biāo)的高效公交換乘算法,用于解決步行換乘等實(shí)際難題。

二、公交數(shù)據(jù)模型的 GIS表達(dá)

公交換乘查詢是建立在公交實(shí)體的詳細(xì)表述基礎(chǔ)之上的。公交數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)直接影響到算法的執(zhí)行效果,合理的公交數(shù)據(jù)結(jié)構(gòu)可以減少搜索次數(shù),提高搜索效率[6]。大中城市的公交數(shù)據(jù)量大、線路復(fù)雜,考慮到公交站點(diǎn)和線路數(shù)據(jù)的維護(hù)、更新及換乘算法的效率,本文設(shè)計(jì)了一種空間數(shù)據(jù)和屬性數(shù)據(jù)相結(jié)合的公交數(shù)據(jù)模型。其中,公交站點(diǎn)、公交路段等空間數(shù)據(jù)以 Geodatabase矢量數(shù)據(jù)模型存儲(chǔ);公交線路屬性信息、線路與站點(diǎn)之間的關(guān)系則以關(guān)系數(shù)據(jù)庫(kù)表的形式存儲(chǔ)。空間數(shù)據(jù)和屬性表之間通過關(guān)鍵字段關(guān)聯(lián),共同表達(dá)復(fù)雜的公交網(wǎng)絡(luò)結(jié)構(gòu)。

公交站點(diǎn) (BusStop)對(duì)應(yīng)一個(gè)矢量點(diǎn)狀要素圖層,主要存儲(chǔ)每個(gè)公交站點(diǎn)的編號(hào)、名稱和坐標(biāo)等信息,該圖層的主要字段如表 1所示。其中,Stop-Name ID字段主要用于標(biāo)識(shí)同名站點(diǎn),以便于算法解決步行換乘問題。所謂同名站點(diǎn)是指那些空間位置鄰近且名稱相同(或稍有不同)的站點(diǎn),例如火車站前站、火車站后站等。在數(shù)據(jù)預(yù)處理過程中,設(shè)兩站點(diǎn)間的距離為 d,同名站點(diǎn)之間的距離閾值為w,根據(jù)乘客的實(shí)際行為和相鄰站點(diǎn)間的平均距離,取w=150 m,以此作為緩沖半徑,利用 GIS的緩沖區(qū)分析功能將 d≤w的站點(diǎn)歸納為同名站點(diǎn),賦予相同的 StopName ID值。

表1 BusStop字段說明

公交路段(BusLine)為矢量線狀要素圖層,用于存儲(chǔ)兩個(gè)相鄰且有公交車直達(dá)的站點(diǎn)之間的路段位置信息,其主要字段如表 2所示。對(duì)于兩個(gè)相鄰站點(diǎn)之間的路段,如果從起點(diǎn)到終點(diǎn)和從終點(diǎn)到起點(diǎn)的行車路線相同,則只存儲(chǔ)為一個(gè)要素;否則按照起止點(diǎn)的順序不同,作為兩個(gè)要素分別存儲(chǔ)。多條通過該路段的公交線路均可共享該路段數(shù)據(jù),這樣可以減少數(shù)據(jù)冗余。

表 2 Bus L ine字段說明

公交線路屬性表(BusRoute)用于存儲(chǔ)各條公交線路的編號(hào)、名稱、開班—收班時(shí)間等信息,其字段信息見表 3。每條公交線路都有上行和下行之分,但在BusRoute表只存儲(chǔ)為一條記錄,其上下行信息在下面的線路站點(diǎn)關(guān)系表中予以區(qū)分。

表3 BusRoute表結(jié)構(gòu)

線路站點(diǎn)關(guān)系表 (RouteStop)存儲(chǔ)各公交線路所經(jīng)過的站點(diǎn)以及每個(gè)站點(diǎn)在上行和下行線路中的序號(hào)等信息,為公交換乘查詢的核心表,其結(jié)構(gòu)及示例數(shù)據(jù)如表4所示。

表 4中 SegUp、SegDn分別表示站點(diǎn)在線路上行、下行中的序號(hào),-1表示不經(jīng)過該站點(diǎn);Line-IDUp、Line IDDn則記錄站點(diǎn)和上行(下行)線路中相鄰下一站點(diǎn)間的路段編號(hào),無(wú)相鄰下一站點(diǎn),則該值為空。以表中 Route ID=1的線路 (圖 1)為例,其上行線路經(jīng)過的站點(diǎn)依次為:1—2—3—4—6,對(duì)應(yīng)的公交路段編號(hào)依次為:01—03—04—05;下行線路經(jīng)過的站點(diǎn)依次是:6—5—3—2—1,路段編號(hào)依次是:10—08—03—02。根據(jù)站點(diǎn)編號(hào)和路段編號(hào)可以分別解析出站點(diǎn)名稱和上下行線路的位置信息,可在地圖上對(duì)上下行線路加以區(qū)分。

表 4 RouteStop示例數(shù)據(jù)

圖1 公交線路示意圖

三、公交換乘算法實(shí)現(xiàn)

1.算法概述

為了便于公交換乘算法的描述,現(xiàn)將公交數(shù)據(jù)模型作如下數(shù)學(xué)定義:

定義 1:設(shè)V表示公交站點(diǎn)的集合,vi為第 i個(gè)公交站點(diǎn),集合V表示為

定義 2:設(shè) R表示經(jīng)過某個(gè)公交站點(diǎn) v的公交線路集合,ri為第 i條公交線路,集合 Rv表示為

定義 3:若 r表示某條公交線路,vri是該線路經(jīng)過的站點(diǎn),則 r可表示為

定義 4:設(shè)L表示某條公交線路的所有路段集合,lj為第 j條公交路段,集合L表示為

定義 5:從給定起始站點(diǎn) vo通過 N次換乘能夠到達(dá)目標(biāo)站點(diǎn) vd的可行公交換乘路徑集合為 TR, TR表示為

其中,TRi為第 i條換乘方案,表示在起點(diǎn) vo選擇線路 ri1到達(dá)站點(diǎn) vi1,換乘線路 ri2到達(dá) vi2,…,最終到達(dá) vd,該路徑換乘次數(shù) N。在本算法中,設(shè)定 0≤N≤2,即最多進(jìn)行兩次換乘,超過兩次的換乘則認(rèn)為兩站點(diǎn)間沒有可行的換乘方案,建議改用其他交通工具;為了提高算法效率,控制換乘方案數(shù)量 n≤10,即最多給出 10條可行的最優(yōu)換乘方案供用戶選擇。

2.算法流程和步驟

基于以上定義和描述,設(shè)計(jì)的換乘算法流程如圖2所示。

圖2 公交換乘算法流程圖

結(jié)合以上流程圖,算法實(shí)現(xiàn)步驟如下:

1)在表 RouteStop中搜索經(jīng)過起始站點(diǎn) vo的線路集合 Ro和經(jīng)過目標(biāo)站點(diǎn) vd的線路集合 Rd;

2)?r(i)∈Ro,搜索線路 r(i)上行 (下行)中站點(diǎn) vo之后的所有站點(diǎn)集 Vo(i),記 Vo(i)={vi1, vi2,…,vik}。則從 vo能夠直達(dá)的所有站點(diǎn)集合Vo= {Vo(i)|i=1,2,…,m}。

3)直達(dá)搜索。?Vo(i)∈Vo,如果 vd∈Vo(i),則 Vo(i)對(duì)應(yīng)的線路 ri為直達(dá)線路,直達(dá)路徑記為TRi=〈vo,ri,vd〉。所有元素比較完后,形成直達(dá)路徑集合 TR0={TRi|i=1,2,…,n}。若 TR0≠ φ,則轉(zhuǎn)入 6),否則轉(zhuǎn)入 4)。

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

a.?r(j)∈Rd,搜索線路 r(j)從上行 (下行)起點(diǎn)到 Vd的所有站點(diǎn)集 Vd(j),記 Vd(j)={vj1,vj2,…,vjm}。能夠直達(dá) vd的所有站點(diǎn)集合為 Vd= {Vd(j)|j=1,2,…,t}。

b.?Vo(i)∈Vo,?Vd(j)∈Vd,設(shè) Vc=Vo(i)∩Vd(j),如果 Vc≠φ,則存在一次換乘路徑,Vc為換乘點(diǎn)集;?vk∈Vc,分別獲取換乘前后的公交線路 r1和 r2,形成一條換乘路徑 TRk=〈vo,r1,vk,r2,vd〉。所有元素比較完后,形成一次換乘路徑集合 TR1= {TRi|i=1,2,…,n}。若 TR1≠φ,則轉(zhuǎn)入 6),否則轉(zhuǎn)入5)。

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

a.在 RouteStop表中分別搜索通過集合 Vo、Vd中任一站點(diǎn)的所有不同線路,形成線路集合 R1和R2;設(shè) Rm=R1∩R2,如果 Rm≠φ,則存在中間換乘線路,否則轉(zhuǎn)入 7)。

b.搜索集合 Rm中每條線路所經(jīng)過的站點(diǎn),形成中間換乘線路的站點(diǎn)集合Vm。

c.?Vo(i)∈Vo,?Vm(j)∈Vm,設(shè)Vc1=Vo(i)∩Vm(j),若 Vc1≠φ,則 Vc1為第一次換乘站點(diǎn)集合;然后繼續(xù)將 Vm(j)同 Vd中的每個(gè)元素 Vd(k)比較,設(shè) Vc2=Vm(j)∩Vd(k),若 Vc2≠ φ,則 Vc2可作為第二次換乘站點(diǎn)集合,此時(shí)存在二次換乘路徑,記為 TRi=〈vo,ri1,vc1,ri2,vc2,ri3,vd〉。所有元素比較完后,形成二次換乘線路集合 TR2={TRi|i =1,2,…,n}。若 TR2≠φ,則轉(zhuǎn)入 6),否則轉(zhuǎn)入7)。

6)結(jié)果解析。對(duì)集合 TR中的每個(gè)元素 TRi,求出途經(jīng)的總站點(diǎn)數(shù) Si,然后按照 Si從少到多的順序?qū)?TRi進(jìn)行排序;再根據(jù)排序后 TRi中記錄的站點(diǎn)編號(hào)、線路編號(hào)依次解析出站點(diǎn)、線路的名稱,形成每條換乘方案的文字描述信息;與此同時(shí),根據(jù)每條直達(dá)線路 ri對(duì)應(yīng)的路段集合 L,利用 L中每條路段 lj的編號(hào) Line ID,通過 GIS中的空間查詢函數(shù)快速獲取該換乘路徑的坐標(biāo)信息,用于在地圖上標(biāo)識(shí)對(duì)應(yīng)的換乘線路。至此,算法結(jié)束。

7)如果二次換乘無(wú)搜索結(jié)果,則算法結(jié)束,返回所查詢的兩個(gè)站點(diǎn)之間無(wú)公交換乘方案。

3.算法特點(diǎn)

1)效率高。在進(jìn)行公交換乘搜索前,首先將表RouteStop中查詢出的通過起始點(diǎn)或者目標(biāo)點(diǎn)的所有記錄讀入內(nèi)存,形成緩存數(shù)據(jù)表,后續(xù)的部分?jǐn)?shù)據(jù)查詢、結(jié)果解析都是在該緩存表中進(jìn)行搜索,相比每次都從包含所有記錄的物理表 RouteStop中查詢,這種技巧不僅可以提高算法效率,而且還可以減少對(duì)數(shù)據(jù)庫(kù)中原始表的頻繁操作,避免游標(biāo)溢出問題。

2)支持步行換乘。現(xiàn)有的很多換乘算法要么沒有考慮步行換乘,要么就是將距離臨近的多個(gè)公交站點(diǎn)提取為一個(gè)站點(diǎn)來(lái)實(shí)現(xiàn)步行換乘。即使是后一種情況,也無(wú)法獲得步行換乘時(shí)下車站點(diǎn)和上車站點(diǎn)的具體名稱和步行距離。本算法在公交數(shù)據(jù)中增加了標(biāo)識(shí)同名站點(diǎn)的 StopName ID字段。換乘搜索時(shí),利用 StopName ID(而非 Stop ID)來(lái)判斷兩條線路是否有站點(diǎn)交集。若交集非空,再獲取 StopName ID在不同線路中對(duì)應(yīng)的 Stop ID。若 Stop ID不同,則兩個(gè) Stop ID對(duì)應(yīng)的站點(diǎn)為步行換乘站點(diǎn),可以獲取具體的下車、上車站點(diǎn)名稱,還可以利用 GIS函數(shù)計(jì)算這兩個(gè)站點(diǎn)間的距離,即用戶需要步行換乘的距離。

3)區(qū)分了線路上、下行和環(huán)路問題。本算法在搜索每條線路 r經(jīng)過的站點(diǎn)集合時(shí),都是按照上、下行次序分別組織成上行站點(diǎn)集合V r1和下行站點(diǎn)集合Vr2,將其作為線路集合 R對(duì)應(yīng)的站點(diǎn)集合 V中的兩個(gè)獨(dú)立元素,并在每個(gè)元素中增加線路 ID和上、下行標(biāo)記符。當(dāng)判斷出元素 V r(i)和另一站點(diǎn)集合中的元素 Vk(j)有交集時(shí),通過解析元素的標(biāo)記符不僅可以快速獲取換乘前后線路編號(hào),而且可以區(qū)分線路的上、下行。對(duì)于可以同時(shí)從兩邊發(fā)車的環(huán)線(起點(diǎn)和終點(diǎn)相同,如圖 3所示),可以將一個(gè)方向(A—B—C)看作上行線路,另一個(gè)方向(A—F—E—D—C)看作下行線路。當(dāng)搜索到該線路時(shí),只需比較上行或下行哪個(gè)途經(jīng)的站點(diǎn)少,即可舍棄其中的以一種,獲得最優(yōu)的環(huán)路換乘方案。

圖3 公交環(huán)線示意圖

4)最優(yōu)換乘點(diǎn)選擇。進(jìn)行一次換乘和二次換乘搜索時(shí),當(dāng)兩條具有相交關(guān)系的線路存在多個(gè)相交站點(diǎn)時(shí),如何選擇換乘站點(diǎn)以保證出行距離最短也是一個(gè)需要考慮的現(xiàn)實(shí)問題。以圖 4為例,線路 1 (A—B—C—D—E)和線路 2(F—D—C—B—G)存在 3個(gè)相交站點(diǎn)(B,C,D),查詢A站到 G站的換乘線路時(shí),B、C、D都可以作為換乘點(diǎn),但經(jīng)B站換乘途經(jīng)總站數(shù)為 2(A—B—D),而經(jīng)D站換乘則需要坐 6站 (A—B—C—D—C—B—G),顯然 B站是最合理的換乘站點(diǎn)。本算法在換取兩條線路的換乘點(diǎn)集后,可以快速統(tǒng)計(jì)出從起點(diǎn)站到每個(gè)換乘點(diǎn)再到目標(biāo)站途經(jīng)的總站數(shù),然后取總站數(shù)最少的那個(gè)換乘站點(diǎn)作為最優(yōu)換乘點(diǎn)。對(duì)于其他的線路相交情況,也可以用該方法統(tǒng)一處理。

圖4 兩條線路相交示意圖

三、公交換乘算法應(yīng)用實(shí)例

本算法目前已應(yīng)用到了山東省網(wǎng)通公司的 114電話導(dǎo)航WebGIS平臺(tái)。公交數(shù)據(jù)統(tǒng)一存儲(chǔ)到Oracle數(shù)據(jù)庫(kù)中,其中,空間數(shù)據(jù)通過空間數(shù)據(jù)引擎ArcSDE進(jìn)行高效訪問,屬性數(shù)據(jù)通過ADO.NET來(lái)訪問。系統(tǒng)根據(jù)客戶端傳入的起止站點(diǎn),在換乘次數(shù)最少的情況下,優(yōu)先給出途經(jīng)總站點(diǎn)數(shù)較少的多條換乘方案供用戶選擇。點(diǎn)擊每條換乘方案,還可以在地圖上清晰標(biāo)識(shí)出該換乘線路、起始點(diǎn)、換乘點(diǎn)和目標(biāo)點(diǎn)的位置信息,直觀地展現(xiàn)給用戶,結(jié)果如圖5所示。

圖5 公交換乘查詢結(jié)果

在對(duì)公交換乘算法的效率測(cè)試中,選用濟(jì)南市目前擁有的 158條公交線路、1 373個(gè)公交站點(diǎn)作為測(cè)試數(shù)據(jù),搜索直達(dá)方案平均耗時(shí)在 0.5 s以內(nèi),一次換乘搜索時(shí)間一般不超過 1.3 s,二次換乘搜索耗時(shí)在 2 s左右。總體來(lái)說,算法效率較高,能夠滿足114客戶快速查詢響應(yīng)的要求。

四、結(jié) 論

公交網(wǎng)絡(luò)模型通過 GIS空間數(shù)據(jù)來(lái)表達(dá)更加符合現(xiàn)實(shí)公交路網(wǎng)情況,在此基礎(chǔ)上設(shè)計(jì)的公交換乘最優(yōu)路徑算法,充分利用了Oracle數(shù)據(jù)庫(kù)和ArcSDE在索引、SQL查詢和空間坐標(biāo)獲取方面的優(yōu)異性能,并結(jié)合基于內(nèi)存的數(shù)據(jù)表查詢、字符串快速拆分和查找機(jī)制,不僅為求解大中城市乘客的公交出行難題提供了一種高效、快捷的解決方案,而且在步行換乘、上下行和環(huán)形線路區(qū)分、最優(yōu)換乘點(diǎn)選取等實(shí)際問題上進(jìn)行了優(yōu)化處理,能夠彌補(bǔ)現(xiàn)有許多算法在查詢效率和準(zhǔn)確性方面的不足。由于公交出行的實(shí)際情況非常復(fù)雜,許多因素還有待考慮,如換乘的難易、時(shí)間和費(fèi)用因素等,這些方面仍需進(jìn)一步的研究和探索。

[1] 廖楚江,蔡忠亮,杜清運(yùn),等.基于最少換乘的公交最優(yōu)路徑算法的設(shè)計(jì)與實(shí)現(xiàn)[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版,2006,31(10):904-907.

[2] 翁敏,毋河海,杜清運(yùn),等.基于公交網(wǎng)絡(luò)模型的最優(yōu)出行路徑選擇的研究[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版,2004,29(6):500-503.

[3] 楊新苗,王煒,馬文騰.基于 GIS的公交乘客出行路徑選擇模型[J].東南大學(xué)學(xué)報(bào):自然科學(xué)版,2000,30 (6):87-91.

[4] 王慶平,張興芳,宋穎,等.城市公交換乘的數(shù)學(xué)模型及其算法實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(7): 246-248.

[5] 向萬(wàn)里,劉洪升.城市公交網(wǎng)絡(luò)出行路徑選擇的計(jì)算機(jī)算法研究 [J].蘭州交通大學(xué)學(xué)報(bào):自然科學(xué)版, 2006,25(1):121-124.

[6] 黃正東.公交實(shí)體的詳細(xì)表達(dá)及其在出行系統(tǒng)中的應(yīng)用[J].武漢大學(xué)學(xué)報(bào):工學(xué)版,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—),男,湖北麻城人,教授,博士生導(dǎo)師,主要研究方向?yàn)?GIS、圖像處理與分析。