基于最小換乘模型的公交查詢系統(tǒng)的設計與實現(xiàn)*

李 俊 陳建勛 熊文龍 杜 江

(武漢科技大學計算機科學與技術(shù)學院1) 武漢 430065)(武漢理工大學計算機科學與技術(shù)學院2) 武漢 430063)(石家莊鋼鐵有限責任公司自動化部信息中心3) 石家莊 050031)

0 引 言

公共交通在現(xiàn)代都市中起著越來越重要的作用,是人們出行的首要選擇.因此有必要建立一個公交查詢系統(tǒng)為人們提供快速、方便的出行方案.

公交查詢系統(tǒng)在電子地圖上直觀的顯示出站點和線路的信息,并提供了起始站點間的最優(yōu)出行方案,極大地方便了人們的出行.

1 系統(tǒng)介紹

公交查詢系統(tǒng)在MyEclipse平臺上選用MapXtreme和Java作為開發(fā)工具,My Sql作為后臺數(shù)據(jù)庫.除了實現(xiàn)了地圖的放大、縮小、漫游等GIS軟件的基本功能外,還能對公交信息進行三種方式的查詢:公交車站查詢、公交線路查詢以及出行方案查詢.(1)公交車站查詢時系統(tǒng)會列出所有在該站點停靠的公交線路,并在地圖上定位顯示;(2)公交線路查詢時系統(tǒng)會列出該公交線路的詳細信息,并在地圖上定位顯示;(3)出行方案查詢時輸入起點和終點,系統(tǒng)即可查詢出以最少換乘為前提,站數(shù)最少的公交出行方案,并在地圖上定位顯示.

為了能在地圖中查詢公交信息,需要在數(shù)據(jù)庫中建立三個屬性數(shù)據(jù)表:公交車站表、公交線路表、公交車站路線表,通過必不可少的主關(guān)鍵字與圖形數(shù)據(jù)一一對應關(guān)聯(lián).3個表的結(jié)構(gòu)如下[1].

1)公交車站表,如表1,列出城市所有的公交車站,其中站名為主關(guān)鍵字.

表1 公交車站表

2)公交線路表,如表2,列出城市所有的公交線路,線路名稱為主關(guān)鍵字.

表2 公交線路表

3)公交車站路線表,如表3,用于公交出行查詢,包括公交車站信息、線路信息以及出行方案查詢等.

表3 公交車站路線表

2 算法分析與實現(xiàn)

2.1 模型抽象與問題分析

公交網(wǎng)絡本身所具有連通性、節(jié)點性、有向性,可將其視為一連通的有向圖;考慮到人們乘車的一般心理,大多數(shù)以換乘次數(shù)最少為第一目標、站數(shù)最少為第二目標[2].因其算法如下.

1)從站點入手,構(gòu)造連通有向圖,即把公交線路視為“邊”,若兩公交站點中有共同線路就相連.從中選取與換乘次數(shù)、站點個數(shù)相關(guān)的最優(yōu)乘車出行方案.

2)在保證換乘次數(shù)相同的前提下經(jīng)過的站點最少.

2.2 換乘矩陣

把站點視為"節(jié)點",把線路視為“邊”,若兩站點中有共同線路就相連,構(gòu)造連通有向圖,記為G(V,E).式中:V,E分別為G的節(jié)點集合和邊集合.然后利用圖論理論對網(wǎng)絡換乘進行分析,建立換乘矩陣 H=(hmn),式中:m,n屬于V;hmn為從節(jié)點m到節(jié)點n的最少換乘次數(shù).

圖1 一個簡單的公交網(wǎng)絡圖

對圖1建立初始換乘矩陣.如果任意兩個站點m,n之間可以直達,則hmn=1,否則hmn=0.這樣就可獲得初始換乘矩陣H0(6×6).

假設公交網(wǎng)絡有q個站點.仿照參考文獻[3]提出的無向圖換乘矩陣算法,結(jié)合公交網(wǎng)絡有向圖的實際,可得換乘矩陣(q×q)的算法如下.

1)初始換乘矩陣H0首先輸入所有站點,如果任意兩個站點m、n之間可以直達,則hmn=1,否則 hmn=0(m、n=1,2,…,q).這樣就可獲得初始換乘矩陣H 0.

2)一次換乘矩陣H1初始換乘矩陣H0中若hmn=1則保持不變.對于H0中的任一hmn=0,如果存在一個k(k=1,2,…,q),使得hmk=1且 hkn=1,則 hmn=2;否則保持不變.對 H0中的所有hmn進行上述運算,就可得到一次換乘矩陣H1.如果H 1中所有 hmn≠0,則停止,否則繼續(xù)下一步.

3)二次換乘矩陣H2一次換乘矩陣H1中的 hmn若1≤hmn≤2則保持不變.對于 H1中的任一hmn=0,如果存在一個k,使得hmk=2且hkn=1,則hmn=3;否則保持不變.對H1中的所有的hmn進行上述運算,就可得到二次換乘矩陣H 2.如果 H2中所有hmn≠0或者H 2=H 1,則停止,否則繼續(xù)下一步.

4)n次換乘矩陣H n 假設已得到n-1次換乘矩陣 H n-1,H n-1中的hmn若 1≤hmn≤n-1則保持不變.如果H n-1中的任一hmn=0,如果存在一個 k,使得hmn=n且hkn=1,則hmn=n+1;否則hmn=0保持不變.對H n中的所有的hmn進行上述運算,就可得到n次換乘矩陣H n.H n中所有hmn≠0或者Hn=Hn-1,則停止,否則繼續(xù)下一步.

為了便于對換乘次數(shù)理解,需要特別說明的是:0表示所對應的2站點不能連通,非0元素減1表示2站點間實際的換乘次數(shù).

3次換乘矩陣為

即為根據(jù)算法得到的最終換乘矩陣.也就是說圖1代表的公交網(wǎng)絡經(jīng)過3次矩陣運算就可以得到最終的換乘矩陣.在解決了換乘次數(shù)問題之后,下面的算法就是解決在換乘次數(shù)相等的條件下站點數(shù)目的問題.

2.3 站點最少算法

對 H 3而言,

對任意2個站點m與n,分別選出所有經(jīng)過站點m及站點n的線路,其中經(jīng)過站點m的所有線路集合記為Lm,經(jīng)過站點n的所有線路集合記為L n.

2.3.1 直達車算法

若hmn=1,此時表示從m到n有直達車.對任意Li∈Lm∩Ln,若此時m,n在這條線路中的位置分別為im,in,則經(jīng)過的站點為Cnm=|inim|.這樣的Li有r條,則統(tǒng)計 r個Cnm.

2.3.2 一次換乘算法

若hmn=2,此時必須轉(zhuǎn)一次車才可以到達終點.對任意的 k∈﹛1,2,…,q﹜∧(k≠m)∧(k≠n),若存在這樣的k,使得 hmk=1且hkn=1,那么找出同時經(jīng)過站點m,k的線路集合L mk(r 1條),同時經(jīng)過站點k,n的線路集合Lkn(r2條).按照直達車算法分別算出r 1條站點m,k間的站數(shù)Ckm,r2條站點k,n間的站數(shù)Cnk.

m,n間總站數(shù)Cnm=Cnk+Ckm,統(tǒng)計 Cnm的值(最多個數(shù)為r1×r2).

2.3.3 n(n≥2)次換乘算法

若hmn=n+1,此時必須轉(zhuǎn)n次車才可以到達終點.對任意的 k∈﹛1,2,…,q﹜∧(k≠m)∧(k≠n),若存在這樣的k,使得 hmk=n且hkn=1(hmk=1且hkn=n類似),那么找出同時經(jīng)過站點m,k的線路集合Lmk(r1條),同時經(jīng)過站點k,n的線路集合L kn(r 2條).按照n-1次換乘算法算出r1條站點m、k間的站數(shù)Ckm,按照直達車算法算出r2條站點k、n間的站數(shù)Cnk.

m,n間總站數(shù)Cnm=Cnk+Ckm,統(tǒng)計 Cnm的值(最多個數(shù)為r1×r2).同法可以算出hmk=1且hkn=n時m,n間總站數(shù)Cnm,統(tǒng)計若干個Cnm的值.

在換乘次數(shù)相同的前提下,求出集合Cnm中最小的N個,則這N個結(jié)果對應的N種線路組合便是站數(shù)較短的線路.

2.4 算法分析

把所有公交站點當成節(jié)點,然后構(gòu)造換乘矩陣,矩陣規(guī)模比較龐大.當然,復雜的公交網(wǎng)絡可能要經(jīng)過更多次矩陣運算才能終止.但是在實際中,兩站點經(jīng)過太多次換乘到達也沒有實際意義,所以可以人為定義最高換乘次數(shù)(比如2或者3).這樣就極大減少了運算時間.

換乘矩陣運算一次后,以后查詢路徑不需要重新計算,以一次的計算代價來換取以后查詢的高速度.

得到換乘矩陣之后,可以比較方便的進行站點個數(shù)計算.以一次換乘算法為例,hmn=2即可確定一次換乘.從換乘矩陣的指定元素得到線路,從線路上得到站點間個數(shù).而文獻[4]則需要從起始站點得到經(jīng)過該站點所有線路集合,再從線路集合中每個站點出發(fā),找到包含任一站點的線路集合,再與經(jīng)過終點站的線路集合比較,兩個集合有交集才能確定一次換乘.

3 系統(tǒng)實現(xiàn)

以公交線路信息查詢和出行方案查詢?yōu)槔齺碚故鞠到y(tǒng)實現(xiàn)的功能.

3.1 公交線路信息查詢

如圖2在“線路查詢”中,輸入要查詢的線路名稱,點擊“查詢”,左邊列表框會出現(xiàn)該線路的所有站點,及收發(fā)班時間、票價等基本信息,右邊地圖上會定位并顯示該線路.

圖2 公交線路信息查詢

3.2 出行方案查詢

輸入“起點”和“終點”站的名稱,然后點擊“查詢”,左邊列表框會出現(xiàn)推薦的出行方案信息,右邊地圖上會定位并顯示該出行方案.方案一如圖3,方案二如圖4,在2個方案都有一次換乘的前提下,方案一只有5站路,比方案二8站路要好.

4 結(jié)束語

論文設計了以最小換乘為前提,以站數(shù)最少為次要條件的最優(yōu)路線出行方案.該方案首先得到站站之間換乘次數(shù)矩陣,然后利用該矩陣非常方便計算出站點間經(jīng)過的站點個數(shù).

圖3 出行方案查詢(方案一)

圖4 出行方案查詢(方案二)

當然,系統(tǒng)可以進一步完善,主要體現(xiàn)在:(1)初始換乘矩陣可以進一步精簡,算法可以進一步完善[5];(2)在換乘次數(shù)相等的條件下,還有時間、票價等因素影響人們的乘車習慣.要考慮到這些因素;(3)結(jié)合無線網(wǎng)絡技術(shù),為無線網(wǎng)絡終端用戶(如3G手機用戶)提供地圖搜索和導航服務.

[1]李玉芝.基于組件式GIS的城市公交查詢系統(tǒng)的設計與實現(xiàn)[D].昆明:昆明理工大學國土資源工程學院.2006.

[2]張存保,李 華,嚴新平.基于Web GIS的城市公交問路系統(tǒng)[J].武漢理工大學學報:交通科學與工程版,2004,28(1):99-102.

[3]張林峰,范炳全,呂智林.公交網(wǎng)絡換乘矩陣的分析與算法[J].系統(tǒng)工程,2003,21(6):92-96.

[4]李 響,張睿智.公交查詢系統(tǒng)的數(shù)學模型[J].黑龍江大學學報:自然科學版,2008,25(4):554-557.

[5] Bi Yong,Hu Hongping.Mathematical model of best-path planning algorithms for public transportation systems[C]//2010 International Conference on Computer Application and System Modeling(ICCASM 2010),2010,13:345-348.