付仲良,張文元,孟慶祥

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

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

付仲良,張文元,孟慶祥

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

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

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

一、引 言

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

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

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

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

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

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

表1 BusStop字段說明

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

表 2 Bus L ine字段說明

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

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

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

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

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

圖1 公交線路示意圖

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

1.算法概述

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

定義 1:設V表示公交站點的集合,vi為第 i個公交站點,集合V表示為

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

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

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

定義 5:從給定起始站點 vo通過 N次換乘能夠到達目標站點 vd的可行公交換乘路徑集合為 TR, TR表示為

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

2.算法流程和步驟

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

圖2 公交換乘算法流程圖

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

1)在表 RouteStop中搜索經(jīng)過起始站點 vo的線路集合 Ro和經(jīng)過目標站點 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≠ φ,則轉(zhuǎn)入 6),否則轉(zhuǎn)入 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≠φ,則轉(zhuǎn)入 6),否則轉(zhuǎn)入5)。

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

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

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

c.?Vo(i)∈Vo,?Vm(j)∈Vm,設Vc1=Vo(i)∩Vm(j),若 Vc1≠φ,則 Vc1為第一次換乘站點集合;然后繼續(xù)將 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≠φ,則轉(zhuǎn)入 6),否則轉(zhuǎn)入7)。

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

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

3.算法特點

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

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

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

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

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

圖4 兩條線路相交示意圖

三、公交換乘算法應用實例

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

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

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

四、結(jié) 論

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

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

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

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

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

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

[6] 黃正東.公交實體的詳細表達及其在出行系統(tǒng)中的應用[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、圖像處理與分析。