1、第31卷第10期2006年10月武漢大學(xué)學(xué)報信息科學(xué)版GeomaticsandInformationScienceofWuhanUniversityVol.31No.10Oct.2006文章編號:167128860(2006)1020904204文獻標志碼:A基于最少換乘的公交最優(yōu)路徑算法的設(shè)計與實現(xiàn)廖楚江1蔡忠亮2杜清運2王長耀1(1中國科學(xué)院遙感應(yīng)用研究所遙感科學(xué)國家重點實驗室,北京市大屯路3號)(2武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院,129號摘要:,。由于算法本身的獨特性,筆者將“圖算法”,利用數(shù)據(jù)庫的快速查詢、索引支持和在集合運,確保算法在求取。關(guān)鍵詞:;最少換乘;最優(yōu)路徑中圖法分類號:P20

2、8城市公交系統(tǒng)是與城市居民日常生活聯(lián)系最為緊密的環(huán)節(jié)之一,甚至在一定程度上決定著城市居民的生活方式,因而,時下眾多城市的電子地圖產(chǎn)品都把實現(xiàn)公交網(wǎng)絡(luò)最優(yōu)路徑查詢作為其重中之重,以期使電子地圖能夠更好地滿足用戶的需求,但其離最優(yōu)還有很大的差距。筆者經(jīng)過調(diào)查研究發(fā)現(xiàn),存在這一差距的主要原因是電子地圖軟件的開發(fā)者與用戶雙方對公交最優(yōu)路徑的理解有著明顯的分歧。一方面,軟件開發(fā)者認為,公交網(wǎng)絡(luò)最優(yōu)路徑分析同其他網(wǎng)絡(luò)分析一樣,也應(yīng)該是以最短為基礎(chǔ)的1,2;另一方面,多數(shù)用戶認為,最少換乘才是關(guān)鍵問題。這兩者看似統(tǒng)一,但其實不然,因為絕大多數(shù)城市公交網(wǎng)絡(luò)中的站點是依據(jù)客流量的大小而設(shè)計的,還有一些是源于政治

3、和歷史的原因而形成的,因而即使把最短路徑求得再快再好,建立于其上的最優(yōu)乘車方案往往會為達到最短而增加換車次數(shù)。當然,不排除一些最短路徑雖然換乘次數(shù)較多,但由于中途等待的時間很短反而能更快地到達的情況,因而筆者在最后的系統(tǒng)中仍然保留了這一傳統(tǒng)模式的實現(xiàn),以便用戶可以在兩種模式之間進行選擇。本文主要就基于最少換乘的最優(yōu)路徑展開討論。1基于最少換乘的最優(yōu)路徑算法思想算法的基本思想如圖1所示,在查詢從站點1到站點2的最優(yōu)路徑的過程中,首先看二者之間是否可以直達,如果是,則直接進入最后一步,按照路線距離進行排序,給出其中最短的幾條線路供用戶選擇;如果不是,則查詢站點1所能直達的所有站點和能直達站點2的所

4、有站點,對這兩個集合求取交集,如果存在交集,則結(jié)束迭代,進入最后一步按路線總距離進行排序,否則,仍然繼續(xù)迭代,求取從站點1必須經(jīng)過1次換乘才能夠到達的站點集合(涉及集合差與并),與能夠直達2的所有站點集合求交,從而得到必須換乘兩次才能到達的乘車方案。交集非空,則結(jié)束迭代,進入最后一步;否則,繼續(xù)迭代,直到找到乘車方案為止。顯然,這一基于“圖論”的算法包含了眾多的集合運算。對該算法的實現(xiàn)有兩種途徑可供選擇,一是采用主存數(shù)據(jù)結(jié)構(gòu),實現(xiàn)集合的快速運算,其中包括快速查找、索引支持以及集合運算等一系列算法;二是直接利用現(xiàn)存商業(yè)數(shù)據(jù)庫已有的在集合運算方面的優(yōu)秀性能。對于前者,筆者收稿日期:20062072

5、20。項目來源:中國科學(xué)院知識創(chuàng)新工程重大資助項目(KZCX12SW201202);國家重點基礎(chǔ)研究發(fā)展規(guī)劃資助項目(G2000077902)。第31卷第10期廖楚江等:基于最少換乘的公交最優(yōu)路徑算法的設(shè)計與實現(xiàn)GeometryLineType,905曾經(jīng)采用基于STL(標準模板庫)的算法予以了實現(xiàn)。在為這個算法作進一步改進的過程中,筆者嘗試了第二種選擇,結(jié)果表明,其在武漢公交網(wǎng)絡(luò)查詢系統(tǒng)中的效率和穩(wěn)定性明顯更進了一步。MEMBERFUNCTIONLengthget_AppointedPar2tRouteLength(longlDepStopPointID,longlReaStop2Point

6、ID)RETURNNUMBER,PRAGMARESTRICT_REFERENCES(Length,WNDS);由此可以計算指定的兩個站點之間的距離。所有線路站點的對應(yīng)關(guān)系在RouteStop中進行了實體化,Rank字段為站點在路線中所處的位置。如可站:ECT(R2,StopS1,StopR1.RouteID=R2.RouteIDANDR1.StopID=S2.StopIDANDR2.StopID=S2.StopIDANDS1.Name=廣埠屯ANDR1.StopID<>R2.StopID圖1of2公交網(wǎng)絡(luò)圖的邏輯結(jié)構(gòu)如圖2所示,它主要由三個表組成,分別為Route表、Stop表和R

7、out2eStop表。在Route表中,除了傳統(tǒng)關(guān)系數(shù)據(jù)庫3算法設(shè)計上文提到,整個最少換乘算法的思想是一個迭代的過程,從搜索經(jīng)過起點站的線路開始,由線路查找該線路經(jīng)過的所有站點,再從這些站點查找經(jīng)過它們的所有線路,不斷迭代,直至找到終點站為止。在具體實現(xiàn)中,可把它演變成一個雙向的過程,即從起點站和終點站同時進行搜索,直到中常見的頭兩個字段外,還增加了Shape字段,其中,Linestring對象類型定義如下3:CREATETYPELinestringASOBJECT(Num_of_PointsINT,圖2公交網(wǎng)絡(luò)圖邏輯結(jié)構(gòu)Fig.2LogicStructureofPublicTrafficNe

8、twork906武漢大學(xué)學(xué)報信息科學(xué)版2006年10月找到兩者相交的站點為止,再從這些線路中尋求最短和最優(yōu)的線路。下面是算法的偽語言描述。PublicSeachPath()需兩次換乘才能到達的站點間的乘車方案,最多僅耗時6s。線路集LineSet1=ExecuteQuery(起點站所經(jīng)過的所有線路);從出發(fā)點能夠直達的站點集StopPointSet1=Union(LineSet1中的所有能達站點);4公交網(wǎng)絡(luò)查詢系統(tǒng)應(yīng)用實例本算法是隸屬于武漢交通網(wǎng)絡(luò)查詢系統(tǒng)的一個子任務(wù),目前該系統(tǒng)為第二版。在原來的版本中,由于開發(fā)周期非常短,筆者直接在網(wǎng)絡(luò)版系,在組件的實現(xiàn)中采用的是基于,一率。但在,Ac2O

9、racle,從而為空間數(shù)據(jù)的存儲和查詢創(chuàng)造了條件。因此,筆者在這個版本中改用基于數(shù)據(jù)庫結(jié)構(gòu)的算法設(shè)計,剔除了原來系統(tǒng)中的非Java部分。實踐證明,新的系統(tǒng)無論在穩(wěn)定性還是在效率上,都較前一版本有了很大的改觀。圖3為該網(wǎng)絡(luò)查詢系統(tǒng)窄帶版的界面,查詢從位于武昌高校中心的廣埠屯到位于漢口的宗關(guān)長途汽車站的乘車方案。從圖3可以看出,在兩站點之間可以乘坐806路車直達,就公交網(wǎng)絡(luò)的規(guī)劃設(shè)計而言,理論上,這兩個站點應(yīng)該是直達的,但如果采用基于最短路徑的查詢,如圖4所示,為了盡量走直線,提供的查詢方案顯示,必須換乘一次才能到達。對比兩圖的線路可以發(fā)現(xiàn),后者只是在武勝路附近走了一個直線,距離顯示僅少走了480

10、m。為測試算法效率,筆者選擇相距較遠的兩個站點進行查詢,查詢從位于武昌東部的“關(guān)山口”到位于漢口北部的“堤角邊”的最優(yōu)路徑(圖5),結(jié)果表明,該查詢耗時僅為5s(算法效率與帶寬無關(guān)),只用一次換乘即可實現(xiàn)。同時,方案的選擇也非常多樣,與實際情況中絕大多數(shù)人的乘車思路完全吻合,相對于同類公交查詢系統(tǒng),其無論是從效率上還是穩(wěn)定性上,都要優(yōu)秀得多。線路集合LineSet2=ExecuteQuery(經(jīng)過終點站的所有線路);能夠到達終點站的所有站點集StopPoint2=Union(LineSet2中的所有能達站點);Vector<StopPointSet>StopPointSetVect

11、or;StopPointSetVector.push_back(StopPointSet1);while(Intersection(StopPoint2,StopPointSet1)=NULL)LineSet3(StopPointSet1中該線路集所能到達的站點集StopPointSet3=Union(LineSet3中的所有能達站點);for(inti=0;i<StopPointSetVector.size();i+)從出發(fā)點必須經(jīng)i+1次換乘方能到達的站點集合StopPointSet4=difference(StopPointSet3,StopPoint2SetVector.at(i

12、);StopPointSet1=StopPointSet4;StopPointSetVector.push_back(StopPointSet4);最后一次換乘站點集合LastStopPointSet=Inter2section(StopPoint2,StopPointSet1);pathPointSet);Sort(所有結(jié)果)=最短路徑=GiveBirthOptionalPathPointer(LastStop2在代碼中,difference、union和intersection都是關(guān)系代數(shù)中的基本運算,可以用SQL查詢來實現(xiàn)。從整個步驟看來,算法蘊涵著相當龐大的運算量,其中對于一次換乘,其

13、時間復(fù)雜度就已經(jīng)是O(n2),如果采用常規(guī)的主存數(shù)據(jù)結(jié)構(gòu),實現(xiàn)起來將非常困難。筆者曾經(jīng)通過基于STL的數(shù)據(jù)結(jié)構(gòu)對該算法進行了實現(xiàn),但在實際運行過程中,仍然無法滿足需求。本文利用數(shù)據(jù)庫本身在空間查詢、索引支持和集合運算上的優(yōu)秀性能,使得這一算法最終得到有效實現(xiàn)的同時,更大程度地滿足了需求。以武漢市為例,它共有612個交通站點,462條公交線路(據(jù)2003年統(tǒng)計),從中查詢5結(jié)語本文提出的基于最少換乘的最優(yōu)路徑思想,是將“圖算法”部署到空間網(wǎng)絡(luò)數(shù)據(jù)庫中加以實現(xiàn),利用數(shù)據(jù)庫在空間查詢、索引和集合運算方面的優(yōu)秀性能來達到目的,從而減小了系統(tǒng)維護的難度,縮短了系統(tǒng)的開發(fā)周期,并為今后“圖算法”的實現(xiàn)開辟

14、了一個新的途徑。當然,就算法的設(shè)計而言,很多附加因素,如路面情況、車速、氣候條第31卷第10期廖楚江等:基于最少換乘的公交最優(yōu)路徑算法的設(shè)計與實現(xiàn)907件等由于數(shù)據(jù)的實時獲取比較困難,本文沒有納入到考慮范圍中來。另外,就算法的實現(xiàn)而言,可以通過層次策略來減少I/O代價和主存緩沖的需求量,從而滿足更大數(shù)據(jù)量的要求。圖3最優(yōu)換乘查詢1Fig.3QueryofBestTransfer1圖4最短路徑查詢圖52Fig.4QueryofOptimumPathFig.5Test2,S.空間數(shù)據(jù)庫M.謝昆青參考文獻1MohammadRK,CyrusSH.ContinuousrestNeighbourQueri

15、esinesC.STDBM,2樂陽.J.,1999,24(3):20922123MichaelZ.ModelingOurWorldM.Redlands:譯.:機械工業(yè)出版社,2004第一作者簡介:廖楚江,博士生。主要從事交通信息系統(tǒng)、組件GIS以及電子地圖的網(wǎng)絡(luò)服務(wù)方面的研究。E2mail:eren_sheepModernRealizationofPublicTrafficOptimalPathBasedonLeastTransfersLIAOChujiangCAIZhongliangDUQingyunWANGChangyao(1StateKeyLaboratoryofRemoteSensin

16、gScience,InstituteofRemoteSensingApplications,ChineseAcademyofSciences,3DatunRoad,Beijing100101,China)(2SchoolofResourceandEnvironmentScience,WuhanUniversity,129LuoyuRoad,Wuhan430079,China)1221Abstract:Thetheoryoftheoptimumqueryofpublictransportationbasedontheleasttrans2fersisputforward,andthealgorithmtorealizeitisdesigned.Thegraphalgorithmistriedtorealizebasedonthespatialnetworkdatabase,makinguseofthequickquery,indexsup2portandthecollectionoperationofdatabasetoacquireexcellentefficiency,andmakinguseofspatialquerysupportofsuchtypeofdatabasetoensurethatthealgorithm