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

李 俊 陳建勛 熊文龍 杜 江

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

0 引 言

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

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

1 系統(tǒng)介紹

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

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

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

表1 公交車站表

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

表2 公交線路表

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

表3 公交車站路線表

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

2.1 模型抽象與問題分析

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

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

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

2.2 換乘矩陣

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

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

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

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

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

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

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

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

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

3次換乘矩陣為

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

2.3 站點(diǎn)最少算法

對(duì) H 3而言,

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

2.3.1 直達(dá)車算法

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

2.3.2 一次換乘算法

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

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

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

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

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

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

2.4 算法分析

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

換乘矩陣運(yùn)算一次后,以后查詢路徑不需要重新計(jì)算,以一次的計(jì)算代價(jià)來換取以后查詢的高速度.

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

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

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

3.1 公交線路信息查詢

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

圖2 公交線路信息查詢

3.2 出行方案查詢

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

4 結(jié)束語

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

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

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

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

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

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

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

[4]李 響,張睿智.公交查詢系統(tǒng)的數(shù)學(xué)模型[J].黑龍江大學(xué)學(xué)報(bào):自然科學(xué)版,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.