馬千里

摘要：城市公交查詢系統(tǒng)是一個城市非常重要的基礎(chǔ)設(shè)施，也是城市文明的一個重要標志。該文探討城市公交查詢系統(tǒng)中最優(yōu)換乘次數(shù)的查詢算法。算法以圖論中鄰接矩陣為基礎(chǔ)，結(jié)合矩陣算術(shù)運算的特點和公交查詢系統(tǒng)的要求建立算法。該算法可有效地查找出最優(yōu)換乘次數(shù)的乘車路線，還可推廣到火車，民航等相關(guān)問題的查詢。

關(guān)鍵詞：鄰接矩陣；公交查詢系統(tǒng)；數(shù)學(xué)模型

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2012)09-2084-03

An Urban Public Transport Inquiry Algorithm Based on Optimal Number of Transfers

MA Qian-li

(Ordos City Dongsheng Informatization Committee, Ordos 017000, China)

Abstract: The urban public transport inquiry system is a very important infrastructure，which is also a symbol of urban civilization . This paper is focused on the Algorithm with optimal number of transfers in the urban public transport inquiry system. The algorithm is based on the theory of adjacency matrix and combined the feature of the matrix arithmetic operations and the requirement of public transport inquiry system, which can effectively find out the optimal number of transfers routes and can also be extended to the railway and civil aviation inquiries.

Key words: adjacency matrix; public transport inquiry system; mathematical model

城市公共交通是一個城市的重要基礎(chǔ)設(shè)施，是關(guān)系民生的社會公益事業(yè)。與其他出行方式相比，公交具有價格便宜、乘用方便安全、線路分布較廣、道路占用率低、耗能低廉等優(yōu)勢，是解決城市交通擁堵的有效途徑。發(fā)展城市公共交通是改善城市人居環(huán)境、構(gòu)建和諧社會、促進城市可持續(xù)發(fā)展的必然要求，是科學(xué)發(fā)展觀在城市建設(shè)和管理工作中的具體體現(xiàn)。

隨著城市規(guī)模不斷擴大，公交線路互連交匯，錯綜復(fù)雜，選擇一條高效便捷的出行方案，使當?shù)鼐用瘛⑼獾赜慰瞳@取足夠的公交出行信息很有必要。對于每個城市公交查詢系統(tǒng)，乘客均會面臨多條線路的選擇問題。通常，乘客需要在最少站數(shù)的路徑和換乘次數(shù)最少的路徑中做出選擇。由于乘客換乘公交需要等待下一趟公交，大多乘客在路徑差距不是很大的情況下更愿意選擇換乘次數(shù)最少的乘車路線。該文正是基于這個特點，討論公共交通網(wǎng)絡(luò)中如何尋找兩個結(jié)點間的一條路徑使之換車次數(shù)最優(yōu)。

1算法描述

1.1建立鄰接矩陣

設(shè)公交系統(tǒng)中的站點數(shù)為N，建立第i路車連接站點的鄰接矩陣:

m站到n站（m≠n）可以由第i路公交車連接0從m站到n站（m≠n）不可以由第i路公交車連接設(shè)公交系統(tǒng)中有M路的公交車，對所有線路公交車的鄰接矩陣求和可得:

1.2查找路徑

1）查找直達路徑

如果bm,n≥1，說明有直達的公車路線，這時只需查找Bi(i=1,2???M)中的bi m,n。當bi

m,n=0，說明第i路車不為所要找車次，依次查詢，找到所有乘車路線，并找出其時間最短的即可。

2）查找轉(zhuǎn)乘一次的線路

如果bm,n=0，則沒有直達路線，所以必須選擇換乘。先尋找轉(zhuǎn)乘一次的情況，這里根據(jù)鄰接矩陣的性質(zhì)知道，B×B=B2就為轉(zhuǎn)

=0，則說明從m站到n轉(zhuǎn)乘2次也不能完成此次行程，所以考慮轉(zhuǎn)乘三次公交才能到達目的地的情況。這種情況一般在一個城市的公交系統(tǒng)里出現(xiàn)的可能性較小，可以利用前面的方法類似推倒即可。

5）查找轉(zhuǎn)乘三次以上的路線

在公交查詢系統(tǒng)中，要換乘三次以上的公交才能達到兩個站點通常是距離很遠，這在城市公交系統(tǒng)中出現(xiàn)的可能性也是微乎其微。此外，由于在換乘公交過程中，乘客一般需要等待公交車，等待三次以上會浪費乘客的大量時間，乘客一般會選擇其他出行方式。該文認為考慮換乘三次以上的線路沒有必要，也不具有實際意義。

1.3算法流程

在城市公交查詢系統(tǒng)中，可以一次加入單個或者多個公交路線。為了提高查詢算法的效率，在每次加入新的公交線路時，建立相應(yīng)的鄰接矩陣，對矩陣B、B2和B3進行重新計算，并作為全局變量保存起來。

該文整個算法的過程描述如下：輸入：任意的兩個站點p和q。輸出：換乘的車次、換乘站點。（1）在矩陣B中查詢bp,q。若bp,q≥1，記錄p到q可以不用換乘公交，依次查找Bi(i=1,2???M)中的bi p,q，若bi p,q=1，記錄乘坐車次i，待循環(huán)結(jié)束后轉(zhuǎn)步驟（5）；若bp,q=0，轉(zhuǎn)步驟（2）。（2）在矩陣B2中查詢b(1)

p,q=0，記錄p到q需要換乘三次以上公交，建議乘客改變乘車方式，轉(zhuǎn)步驟（5）。（5）輸出乘坐車次和換乘站點或給出乘客乘坐建議。

011000 001101 100110 110011 211000 010100

通過查看B中對應(yīng)元素就可以得知是否可以直達。例如：我們要查找A站是否可以直達B站，則可以通過查看b1,2的值。由于b1,2≥1，則可以得知A站到B站可以直達；然后在Bi查找bi1,2(i=1,2,3)可知b11,2=1，由此，一路車可以從A站直達B站。

若要查找任意兩站的轉(zhuǎn)乘一次線路，則需要計算B2：

101112 122112 322011 233201 123112 111112

若要查找B站到E站得乘車路線，首先查找B，由于b2,5=0，故不存在直達的公交；然后查找B2，由于b(1) 2,5=1，故存在換乘一次的路線；最后，查找換乘的車次。依次判定B1B2、B1B3、B2B1、B2B3、B3B1、B3B2中第二行第五列元素的值可知，B1B2中對應(yīng)元素為1，故可以通過先乘坐1路車，再換乘2路車到終點站。至于換乘站點，可以查看B1第二行的元素和B2中第5列的元素可知，換乘站點為C站。

3結(jié)論

該文所述算法是利用矩陣運算特點所建立的，可以有效地搜索出的乘車路線，但由于利用矩陣運算，特別是轉(zhuǎn)乘次數(shù)增多的情況，會使得運算量增大，影響計算速度。

參考文獻：

[1]同濟大學(xué)應(yīng)用數(shù)學(xué)系.線性代數(shù)[M].北京:高等教育出版社,2003.

[2]趙靜,但琦.數(shù)學(xué)建模與數(shù)學(xué)實驗[M].北京:高等教育出版社,2002.

[3]蘇金明,阮沈勇.MATLAB實用教程[M].北京:電子工業(yè)出版社,2005.

[4]嚴蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社,1997.

[5]尹志華,羅小龍.荊州電子地圖公交查詢算法與實現(xiàn)[J].測繪與空間地理信息,2008,31(1):141-143.

[6]張永梅,韓焱,陳立潮.城市公交查詢系統(tǒng)的研究與設(shè)計[J].計算機應(yīng)用,2005,25(2):422-425.

[7]于小東,楊國東,王鳳艷,許惠平.城市公交查詢系統(tǒng)的設(shè)計與實現(xiàn)[J].吉林大學(xué)學(xué)報,2005,23(6):675-678.