基于最少換乘路徑選擇算法的改進(jìn)

摘要:最短路徑是圖論研究中一個(gè)最基本的算法問題，也是公交出行路線選擇系統(tǒng)中的關(guān)鍵技術(shù)之一。通過分析研究目前比較流行的最短路徑算法，根據(jù)人們選擇出行路線的心理，提出以最少換乘為第一目標(biāo)，最短路徑為第二目標(biāo)的思想，并以其作為基準(zhǔn)點(diǎn)，對(duì)傳統(tǒng)的廣度優(yōu)先搜索算法中存在的問題做出適當(dāng)?shù)母倪M(jìn)。

關(guān)鍵詞:最短路徑;廣度優(yōu)先搜索算法;最少換乘

中圖分類號(hào):TP301文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2010)01-168-03

Improvements for Optimal Path Selection Algorithm with Minimum Transfer Times

JING Li-rong， MA Shang-cai， SHEN Liang

(Information Management，Shanxi University of Finance Economics，Taiyuan 030006，China)

Abstract: The shortest path problem is a classic algorithm issue in Graph Theory study，and it is also one of the key technologies in Bus Travel Route Choice System.In this paper，by analyzing the shortest path algorithms which is an idea prevails currently and considering people's psychology when choosing travel routes，the minimum transfer times is regarded as the main principle and the shortest path followed is proposed.Based on the discussion above，appropriate improvements are made to the traditional Breadth First Search algorithm.

Key words: Shortest Path;Breadth First Search Algorithm;Minimum Transfer Times

城市道路交通網(wǎng)是城市的重要基礎(chǔ)設(shè)施，它的運(yùn)行直接影響著城市的規(guī)劃、建設(shè)和管理。面對(duì)未來的城市，道路有效地運(yùn)行，無疑是城市發(fā)展的一個(gè)重要方面。目前，解決交通擁擠的直接辦法是提高路網(wǎng)的通行能力，增加公共交通運(yùn)輸能力提倡人們選擇公共交通出行。但正因?yàn)槁肪€的眾多，給人們出行選擇路線帶來了一定的困擾。在綜合考慮了時(shí)間，費(fèi)用，距離的基礎(chǔ)上，人們傾向于選擇能花最少的時(shí)間，付最小的代價(jià)的路線作為出行路線。

目前，已經(jīng)有許多的研究者在公交最優(yōu)路徑選擇問題中做出了相關(guān)研究。王建林提出一種基于換乘次數(shù)最少的城市公交網(wǎng)絡(luò)最優(yōu)路徑算法，文中充分考慮了乘客乘車時(shí)的心理因素，并指出換乘次數(shù)最少是乘客出行時(shí)考慮的首要因素[1];胡霍真等人將最短路徑算法應(yīng)用到公交車網(wǎng)絡(luò)中，并通過實(shí)驗(yàn)驗(yàn)證該算法取了較好的查詢結(jié)果[2];李洪波等人提出了一種動(dòng)態(tài)優(yōu)化的Floyd最短路徑算法，提高了算法的運(yùn)行效率[3]。

本文第二節(jié)簡要介紹了幾種比較著名的最短路徑算法，并分析了其算法中所存在的問題。第三節(jié)中具體的描述了傳統(tǒng)的廣度優(yōu)先搜索算法以及對(duì)公交車路線網(wǎng)的抽象。第四節(jié)給出了一種新的公交車路線網(wǎng)抽象模型和改進(jìn)的廣度優(yōu)先搜索算法，經(jīng)實(shí)例驗(yàn)證了該新模型以及改進(jìn)算法的有效性。第五節(jié)總結(jié)全文。

1 最短路徑算法綜述

最短路徑算法的研究，得到了國內(nèi)外各個(gè)領(lǐng)域的高度重視。研究學(xué)者分別從不同的角度出發(fā)，提出了各種相關(guān)的知名算法，如Dijkstra算法、Floyd算法以及A*算法等，并且成功的應(yīng)用于各個(gè)領(lǐng)域。

Dijkstra算法是由E.W.Dijkstra在1995年提出的[4]。它是一種基于貪婪搜索技術(shù)[5]的搜索算法。首先，它求出從起點(diǎn)到最接近起點(diǎn)的頂點(diǎn)之間的最短路徑，然后求出到第二接近頂點(diǎn)間的最短路徑，以此類推。推而廣之，在第i次迭代開始以前，該算法已經(jīng)確定了i-1條離起點(diǎn)最近頂點(diǎn)之間的最短路徑。

Floyd算法是一種動(dòng)態(tài)規(guī)劃算法[3]。它從圖的帶權(quán)鄰接矩陣A=[a(i，j)]n×n開始，按照公式(1)迭代，構(gòu)造出矩陣D(1)，D(2)……D(n-1)，D(n)。其中D(0)=A=[a(i，j)]n×n，D(k)[i][j]是從vi到vj的中間頂點(diǎn)的序號(hào)不大于k的最短路徑長度。矩陣D(n)的第i行第j列元素為從i號(hào)頂點(diǎn)到j(luò)號(hào)頂點(diǎn)的最短路徑長度，D(n)為圖的距離矩陣。

A*算法是目前最流行的啟發(fā)式搜索算法(Heuristic Search)[6]，也是一種靜態(tài)路網(wǎng)中求解最短路最有效的方法。該算法的創(chuàng)新之處在于采用啟發(fā)信息，其目的是估計(jì)待選的節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)間的距離，以使搜索算法優(yōu)先考慮最有希望的節(jié)點(diǎn)，即使估價(jià)函數(shù)最小的節(jié)點(diǎn)[7]。定義節(jié)點(diǎn)n 的啟發(fā)式估價(jià)函數(shù)f'(n)見公式(2)。其中，g(n)是從原點(diǎn)到當(dāng)前節(jié)點(diǎn)n的實(shí)際代價(jià)，h'(n)是從當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最小代價(jià)的估計(jì)函數(shù)，A*算法是搜索具有最小f'(n)的節(jié)點(diǎn)。

然而，上述討論的最短路徑算法并不適用于公交路線選擇問題中。首先，根據(jù)統(tǒng)計(jì)數(shù)據(jù)表明[1]，在選擇出行路線時(shí)首先考慮換乘最少的乘客占有41.16%，而只有18.60%的乘客在選擇出行路線時(shí)會(huì)考慮路徑最短。其次，將最短路徑算法應(yīng)用在公交路線查詢系統(tǒng)中會(huì)給系統(tǒng)帶來不必要負(fù)擔(dān)。如在Dijkstra算法中，Dijkstra要求的是一組路徑，每條路徑都從起點(diǎn)出發(fā)通向圖中的一個(gè)不同頂點(diǎn)。由于公交路線中的站站分布較廣，抽象為圖式本身的數(shù)據(jù)結(jié)構(gòu)比較龐大，無疑在查詢的過程中會(huì)增加運(yùn)算時(shí)間。而在A*算法中，h(n)的信息越多，它的計(jì)算量就越大，耗費(fèi)的時(shí)間就越多。如果適當(dāng)?shù)臏p小h(n)的信息，即減小約束條件，算法的準(zhǔn)確性就差。

綜上所述，基于乘客的乘車的心理，最少換乘算法應(yīng)運(yùn)而生，本文稱之為傳統(tǒng)的廣度優(yōu)先搜索算法。

2 傳統(tǒng)的廣度優(yōu)先搜索算法

在公交車路線網(wǎng)中，由于所有的站點(diǎn)都是通過公交路線相連的，故可以將公交車路線網(wǎng)抽象為一個(gè)無向的連通圖[8]G(V，E)，圖中頂點(diǎn)V表示公交路線所經(jīng)過的站點(diǎn)，E表示來兩個(gè)站點(diǎn)之間有公交路線相連。如圖1所示。

該算法的基本思路是:假設(shè)欲查找從起始站S出發(fā)到達(dá)終點(diǎn)站E的公交路線。

1) 查找站點(diǎn)S處所有的公交車號(hào)集合BUS(S)是否與站點(diǎn)E處所有的公交車號(hào)集合BUS(E)有交集，若有，則說明從S站到E站有直達(dá)的公交車。否則轉(zhuǎn)步驟2)。

2) 查找經(jīng)過S站所有的公交車沿路能轉(zhuǎn)成的公交車號(hào)的集ALONG(BUS(S))是否與站點(diǎn)E處所有的公交車集合BUS(E)有交集。若有，則說明從S站能通過轉(zhuǎn)車到達(dá)E站，否則重復(fù)2)直到找到有交集或轉(zhuǎn)車次數(shù)達(dá)到2次為止。

3 基于廣度優(yōu)先搜索算法的改進(jìn)

3.1 算法的主要思路

由于公交車路線的數(shù)據(jù)量比較龐大，傳統(tǒng)的廣度優(yōu)先搜索算法將公交路線網(wǎng)抽象為無向連通圖較為復(fù)雜。本文用無向帶標(biāo)簽的圖[7]G1=(V，E，L)來抽象整個(gè)公交車路線網(wǎng)。將公交車號(hào)集合抽象成頂點(diǎn)集V={v1，v2，…vn}，vi表示某一條公交車路線。邊集E={e1，e2，…en}表示來兩個(gè)公交車之間的公共站點(diǎn)。標(biāo)簽集包括兩個(gè)子集L=Lv∪Le，分別為:Lv={lv1，lv2，…lvn}，Le={le1，le2，…Len}。改進(jìn)后的公交路線網(wǎng)抽象模型如圖2所示。

此外，傳統(tǒng)的廣度優(yōu)先搜索算法在運(yùn)行過程中產(chǎn)生大量的無效數(shù)據(jù)，使得算法對(duì)這些數(shù)據(jù)的重復(fù)操作，極大的影響了算法的效率。因此本文主要是針對(duì)以上問題做出相應(yīng)的改進(jìn)。

算法的步驟如下:

1)將乘客欲查找的起始站S作為樹TS的根節(jié)點(diǎn)，終點(diǎn)站E作為樹TE的根節(jié)點(diǎn)。

2)將經(jīng)過起始站S與終點(diǎn)站E的所有公交車號(hào)分別作為這兩棵樹的子節(jié)點(diǎn)。

3)對(duì)TS和TE的子節(jié)點(diǎn)進(jìn)行遍歷查找，查找這兩棵樹的子節(jié)點(diǎn)中是否存在相同的公交車號(hào)，若不存在，則轉(zhuǎn)步驟4)，否則轉(zhuǎn)步驟5)。

4)對(duì)TS和TE樹的子節(jié)點(diǎn)交替構(gòu)造新的子節(jié)點(diǎn)，即將當(dāng)前節(jié)點(diǎn)中表示的公交車號(hào)沿路能轉(zhuǎn)乘的車號(hào)作為其欲構(gòu)造的子節(jié)點(diǎn)。在添加節(jié)點(diǎn)的過程中，若添加的節(jié)點(diǎn)與其上一層節(jié)點(diǎn)相同，則取消添加。轉(zhuǎn)步驟(3)。

5)輸出相應(yīng)的公交車號(hào)即轉(zhuǎn)乘路線。(考慮到實(shí)用性，規(guī)定轉(zhuǎn)車上限為2次，因?yàn)槌^一定的轉(zhuǎn)車次數(shù)，人們會(huì)選擇其他的方式出行。)

3.2算法的實(shí)現(xiàn)

由上所述，其算法偽代碼實(shí)現(xiàn)如下:

算法1:改進(jìn)的廣度優(yōu)先算法

If(SE)

{

CreateTree(TS)

CreateTree(TE)

ExtendTree (TS);

ExtendTree (TE);

If(BFSearch(TS，1)∩BFSearch(TE，1)≠Φ)

Path=GetThePath(BFSearch(TS，1)∩BFSearch(TE，1)，0)

Else

ExtendTree(TS);

If(BFSearch(TS，2)∩BFSearch(TE，1)≠Φ))

Path=GetThePath(BFSearch(TS，2)∩BFSearch(TE，1)，1)

Else

ExtendTree(TE);

If(BFSearch(TS，2)∩BFSearch(TE，2)≠Φ)

Path=GetThePath(BFSearch(TS，2)∩BFSearch(TE，2)，2)

Else

Return 0

}

算法2 構(gòu)造子節(jié)點(diǎn)函數(shù)

ExtendTree(Tree T)

{

If(T)

{

While(T→chlid)

T=T→Child;

While(Bi?Buses(T→data))

{

If(Bi?Histroy)//History集合即父輩已插入的站點(diǎn)

Insert(Bi，T);

}

}

}

其中，CreateTree( )函樹用來創(chuàng)建一個(gè)樹，建立樹的根節(jié)點(diǎn)。BFSearch(T，int i)表示對(duì)T樹的第i層節(jié)點(diǎn)進(jìn)行廣度優(yōu)先遍歷搜索。GetThePath(T，int i)為輸出路徑函數(shù)。其中，T表示兩棵中的公共子節(jié)點(diǎn)，i表示需要轉(zhuǎn)乘的次數(shù)。Buses( )為當(dāng)前站點(diǎn)表示的公交車沿路能轉(zhuǎn)乘的公交車號(hào)集合。

3.3 實(shí)例分析

下面以實(shí)例具體說明該算法的求解過程。求從起始站“山西財(cái)經(jīng)大學(xué)”(以S表示)到終點(diǎn)站“青年路口”(以E表示)的最優(yōu)路徑。

第一步，創(chuàng)建樹TS和TE。

第二步，擴(kuò)展TS樹，此時(shí)，TS的葉子節(jié)點(diǎn)集BUS(S)={861，103，39，849，824，877，870，868}。同理，擴(kuò)展TE樹，TE的葉子節(jié)點(diǎn)集BUS(E)={1，3，6，10，25，611，618，808，838，848，859}，

第三步，由于BUS(S)∩BUS(E)=Φ，不存在從S站點(diǎn)到E站點(diǎn)的直達(dá)路徑，因此在以后的查詢過程中可將BUS(S)集合中的數(shù)據(jù)視為無效的數(shù)據(jù)。

第四步，再次擴(kuò)展TS樹，將其葉子節(jié)點(diǎn)放入ALONG(BUS(S))集合，查看ALONG(BUS(S))與BUS(E)是否存在交集。比如在集合ALONG(BUS(S))中，“861”沿路能轉(zhuǎn)乘的公交車號(hào)的集合為ALONG(BUS(861))={861，6，101，1，102，39，103，611，618， 808，824， 830， 831，836，838，840，848，849，868，870，877}，從這個(gè)集合中可以看出此集合存在大量的無效數(shù)據(jù)，即{861，103， 39， 824， 849， 870， 877，868}，使得算法在運(yùn)行過程中重復(fù)這些數(shù)據(jù)進(jìn)行掃描，影響算法執(zhí)行的速度。故在創(chuàng)建樹時(shí)有必要?jiǎng)h除多余的節(jié)點(diǎn)。此時(shí)ALONG(BUS(861))={6，101，1，102，611，618，808，830，831，836，838，840，848}。由于ALONG(BUS(S))∩BUS(E)={1，6，611， 618，838， 808，848}，因此乘客可以轉(zhuǎn)乘此集合中的公交車到達(dá)終點(diǎn)站E。類似地，算法采用相同的方法對(duì)ALONG(BUS(S))集合中的數(shù)據(jù)進(jìn)行迭代查找，直到找出所有通過轉(zhuǎn)乘一次的公交路線。

第五步，輸出公交車乘車路線，用戶可以根據(jù)其所需求選擇相應(yīng)的路線。

4 小結(jié)

本文中所提出的公交車路線網(wǎng)絡(luò)抽象模型能夠有效地將復(fù)雜的公交車路線網(wǎng)絡(luò)模型化，較之傳統(tǒng)的抽象模型有較大的改進(jìn)，減少了數(shù)據(jù)的存儲(chǔ)量，提高了算法的查詢速度。另外，通過將本文所提出的改進(jìn)算法應(yīng)用在公交路線查詢系統(tǒng)中，驗(yàn)證了該算法可以有效的找出最少換乘路線，與傳統(tǒng)的廣度優(yōu)先搜索算法相比，提高了算法運(yùn)行的效率。

參考文獻(xiàn):

[1] 王建林.基于換乘次數(shù)最少的城市公交網(wǎng)絡(luò)最優(yōu)路徑算法[J].經(jīng)濟(jì)地理，2005，25(5):673-676.

[2] 胡霍真，戴光明，李穎.公交車網(wǎng)絡(luò)的最短路徑算法及實(shí)現(xiàn)[J].微機(jī)發(fā)展，2005，15(9):21-22.

[3] 李洪波，王茂波.Floyd最短路徑算法的動(dòng)態(tài)優(yōu)化[J].計(jì)算機(jī)工程與應(yīng)用，2006，34:60-63.

[4] E.W.Dijkstra.A Note on Two Problems in Connexion with Graphs.Numerische Mathematik 1959，(1):269-271.

[5] Annny Levitin.Introduction to the Design and Analysis of Algorithms[M].2007.

[6] 張仁平，周慶忠，熊偉，等.A*算法改進(jìn)算法及其應(yīng)用[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2009，(9):98-100.

[7] 王林，石金峰.智能交通系統(tǒng)中幾種最短路徑算法分析[J].交通科技與經(jīng)濟(jì)，2009，11(4):110-112.

[8] 常新功.基于混合進(jìn)化的子結(jié)構(gòu)發(fā)現(xiàn)[M].北京:國防工業(yè)出版社，2009.