鄧 競 偉

(西北民族大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，甘肅 蘭州，730124)

?

城市公交系統(tǒng)的最優(yōu)路徑搜索算法

鄧 競 偉

(西北民族大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，甘肅 蘭州，730124)

在分析城市公交系統(tǒng)特點(diǎn)的基礎(chǔ)上，利用改進(jìn)的最短路徑算法對此問題進(jìn)行闡述和分析，描述了Dijkstra算法和改進(jìn)的最短路徑算法，并將改進(jìn)的算法應(yīng)用于城市公交系統(tǒng)中，最后用一個簡單的例子進(jìn)行驗證。結(jié)果表明，在搜索效率上改進(jìn)后的算法比Dijkstra算法好。

Dijkstra算法；城市公交網(wǎng)絡(luò)；最優(yōu)路徑

隨著城市建設(shè)的飛速發(fā)展以及城市公交系統(tǒng)的不斷完善，公交車已成為城市居民出行的主要交通工具[1]。公交系統(tǒng)是城市交通系統(tǒng)的一個重要組成部分，最優(yōu)線路的選擇不僅是公交公司一直面臨的問題，也是乘客出行時關(guān)注的首要問題。能夠很好地解決城市擁堵的方法是大力發(fā)展公交，提高乘坐公交出行人數(shù)的比例，實現(xiàn)這一目標(biāo)的最好方法是乘坐公交的出行效率提高，減少乘坐公交的出行時間[2]。由于從一個地點(diǎn)到達(dá)另一個地點(diǎn)可能會有許多線路選擇，為了選擇一條最佳線路，對乘客的出行時間和費(fèi)用有著至關(guān)重要的作用，也就是說，總體考慮了距離、時間、費(fèi)用等問題，此類現(xiàn)實問題關(guān)系到如何求解最短路徑問題。最短路徑是人們一直關(guān)注的問題[3]，目前最短路徑的實際應(yīng)用仍是一個研究熱點(diǎn)[4]。有許多研究領(lǐng)域，如網(wǎng)絡(luò)分析、交通規(guī)劃、通信等起著重要作用[5]。

1 城市公交網(wǎng)絡(luò)

1.1 公交網(wǎng)絡(luò)的特點(diǎn)

在公交網(wǎng)絡(luò)中[6]，不同線路在行程上有著相同的公交站點(diǎn)，即在不同線路上會經(jīng)過相同的站點(diǎn)，但在公交站點(diǎn)分布的實際情況中，即使是同一個站點(diǎn)也會存在空間位置上的不同，若將一個公交站點(diǎn)看作一個節(jié)點(diǎn)，對網(wǎng)絡(luò)進(jìn)行分析時，需要把不同線路的公交站點(diǎn)抽象為一個節(jié)點(diǎn)，只有這樣才能模擬出不同公交線路之間的乘客可換車情況的網(wǎng)絡(luò)。

1.2 公交網(wǎng)絡(luò)最短路徑

公交網(wǎng)絡(luò)中的一個關(guān)鍵問題是最優(yōu)路徑的選擇，最優(yōu)路徑是計算2點(diǎn)間的距離最短，城市公交線路最佳選擇問題可以描述為：某乘客從起點(diǎn)S出發(fā)前往目的地E，S與E之間存在多條可供乘坐的線路，并且這些線路和經(jīng)過線路的公交站點(diǎn)組成了一個公交網(wǎng)絡(luò)圖。為了乘客出行方便，在研究網(wǎng)絡(luò)模型和最短路徑算法時，首先要了解公交乘客出行時所考慮的因素，通過對公交乘客出行心理行為的研究來確定模型的優(yōu)化目標(biāo)，通常乘客出行會從以下幾個方面考慮[7]：換車次數(shù)、時間、費(fèi)用、距離等，乘客滿意度一般有兩種形式：一個是總出行時間，另一個是乘客的出行總成本[8]。

2 公交網(wǎng)絡(luò)數(shù)學(xué)模型的建立

為了考慮公交乘客出行時間和費(fèi)用最少等問題時，只需將研究問題中的一些參數(shù)做一些調(diào)整后，這些考慮的問題將會是最短路徑問題。

城市公交網(wǎng)絡(luò)是由線路和站點(diǎn)組成，可以抽象成一個網(wǎng)絡(luò)拓?fù)鋱DG=[6](其中，V——頂點(diǎn)集，E——邊集，L——邊權(quán)值)。

3 傳統(tǒng)的最短路徑算法

目前，求解最短路徑問題算法很多[9]，Dijkstra算法[10]仍然是公交網(wǎng)絡(luò)最短路徑算法的首選算法，但是在求解時都有可能會搜索所有的網(wǎng)絡(luò)節(jié)點(diǎn)，在網(wǎng)絡(luò)節(jié)點(diǎn)多時，此算法的時間花費(fèi)增長速度很快，很難滿足實際運(yùn)算的需要[11]。

Dijkstra算法的核心過程[12]是將滿足條件的T(臨時標(biāo)號)節(jié)點(diǎn)變成P(固定標(biāo)號)節(jié)點(diǎn)，即計算每一步是把某個點(diǎn)的T標(biāo)號變成P標(biāo)號，這樣一旦終點(diǎn)到達(dá)P節(jié)點(diǎn)，計算就結(jié)束。

Dijkstra算法具體步驟描述如下[6]：

(1)給起點(diǎn)pi標(biāo)上P標(biāo)號，給其他各點(diǎn)標(biāo)上臨時標(biāo)號。

(2)在所有臨時標(biāo)號中取最小值，則把該點(diǎn)的臨時標(biāo)號改為固定標(biāo)號。

(3)重新計算具有臨時標(biāo)號的其他各點(diǎn)標(biāo)號：選擇臨時標(biāo)號中的較小者作為新標(biāo)號。

(4)重復(fù)上述步驟，當(dāng)算法結(jié)束時，從pi到pm的最短路徑的長度由標(biāo)號的終值給出，這時d(pm)就是從pi到pm的最短路徑。

4 改進(jìn)搜索算法

在城市公交網(wǎng)絡(luò)中，最短路徑是一種網(wǎng)絡(luò)優(yōu)化問題[13]。Dijkstra算法是用來求解圖上任一節(jié)點(diǎn)到其余各個節(jié)點(diǎn)的最短路徑，采用鄰接矩陣存儲網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，隨著節(jié)點(diǎn)數(shù)的增加，其計算效率和存儲效率越低[14]。尤其在站點(diǎn)和線路相對多的情況下，在實際應(yīng)用中，使用Dijkstra算法耗費(fèi)大量的計算時間[15]，即當(dāng)網(wǎng)絡(luò)模型中節(jié)點(diǎn)和邊數(shù)較多時，算法的計算量很大，時間花費(fèi)相對多，成為應(yīng)用Dijkstra算法的瓶頸[16～18]。

通過分析Dijkstra算法的不足，為了提高效率，考慮將最短路徑問題分解成2個子問題，即分別為由起點(diǎn)到終點(diǎn)和由終點(diǎn)到起點(diǎn)求解最短路徑的兩個問題，兩個問題并行處理，從2個站點(diǎn)同時搜索，到交叉時就可從2個站點(diǎn)都找到到達(dá)同一站點(diǎn)的最短路徑，然后再從結(jié)果中找出最短路徑，把搜索到的下一個站點(diǎn)放到一個集合里，從而大幅度減少搜索時間。

5 實 例

一個簡單的公交網(wǎng)絡(luò)帶權(quán)圖如圖1所示，圖中共有7個站點(diǎn)，15條線路。應(yīng)用上述算法計算公交乘客從起點(diǎn)S到終點(diǎn)E的最短路徑，圖中的每個頂點(diǎn)表示站點(diǎn)，邊表示2個站點(diǎn)之間的線路，邊上的權(quán)值表示2個站點(diǎn)之間的距離、途中所經(jīng)過的時間或者是交通費(fèi)用等，此時路徑長度是路徑上邊的權(quán)之和[19]。例如，從A點(diǎn)到B點(diǎn)，A點(diǎn)高于B點(diǎn)，考慮上坡下坡的車速不同，則有向邊和上表示行使時間的權(quán)值也不同，所以交通網(wǎng)絡(luò)屬于有向網(wǎng)。假設(shè)某乘客從起點(diǎn)S出發(fā)前往終點(diǎn)E，其間有多條線路可供選擇，兩點(diǎn)之間線路的權(quán)值表示該線路的線程，權(quán)值越大說明距離越長，反之則距離越短。

圖1 公交網(wǎng)絡(luò)帶權(quán)簡圖

各條線路的線程見表1。

表1 公交網(wǎng)絡(luò)帶權(quán)簡圖中的線路及距離

Dijkstra算法和改進(jìn)后的算法具體搜索過程分別見表2，表3。

表2 Dijkstra算法對公交網(wǎng)絡(luò)帶權(quán)簡圖中的最短路徑的具體搜索過程

表3 改進(jìn)后的算法對公交網(wǎng)絡(luò)帶權(quán)簡圖中的最短路徑的具體搜索過程

從表2，表3中可以看出，從起點(diǎn)S到終點(diǎn)E的最短線路是相同的，對于站點(diǎn)和線路少此算法不明顯，但是對于目前城市公交系統(tǒng)中站點(diǎn)多、線路多、道路擁堵等特點(diǎn)來看，改進(jìn)后的算法效率大幅度提高。

6 結(jié) 論

通過分析公交系統(tǒng)的特點(diǎn)以及乘客的需求，描述了Dijkstra算法，根據(jù)實例分析，對已有算法和改進(jìn)的算法進(jìn)行比較，驗證了在城市公交系統(tǒng)中，尤其是節(jié)點(diǎn)和線路較多時，改進(jìn)的算法可以有效提高效率，以此方便乘客出行。

[1] 梁虹，袁小群，劉蕊.一種新的公交數(shù)據(jù)模型與公交查詢系統(tǒng)實現(xiàn)[J].計算機(jī)工程與應(yīng)用，2007，43(3):234-238.

[2] Zhan F B.Three Shortest Path Algorithms on Real Road Networks:Date structure and procedures[J].Journal of Geographic Information and Decision Analysis,1997，1(1):69-82.

[3] Xu M H，Liu Y Q，Huang Q L，et al.An improved Dijkstra’s shortest path algorithm for sparse network[J].Applied Mathematics and Computation,2007,185(1)：247-254.

[4] T Takaoka.Shortest path algorithms for nearly acyclic directed graphs[J].Theor Comput Sci,1998(203):143-150.

[5] 譚國真，高文.時間依賴的網(wǎng)絡(luò)中最小時間路徑算法[J].計算機(jī)學(xué)報，2002，25(2):165-172.

[6] 龍光正，楊建軍.改進(jìn)的最短路算法[J].系統(tǒng)工程與電子技術(shù)，2002，24(6):106-108.

[7] 楊新苗，王煒，馬文騰.基于GIS的公交乘客出行路徑選擇模型[J].東南大學(xué)學(xué)報:自然科學(xué)版，2000，30(6):87-91.

[8] 何勝學(xué)，范炳全.公交網(wǎng)絡(luò)最優(yōu)路徑求解算法[J].交通運(yùn)輸工程與信息學(xué)報，2007，5(1):22-27.

[9] 周培德.交通道路網(wǎng)中任意兩點(diǎn)之間最短路徑的快速算法[J].計算機(jī)工程與科學(xué)，2002, 24(4)：35-37.

[10] Bondy J A，Murty U S R.Graph Theory with Applications[M].London: The Macmillan Press Ltd，1976.

[11] 嚴(yán)寒冰，劉迎春.基于GIS的城市道路網(wǎng)最短路徑算法探討[J].計算機(jī)學(xué)報，2000，23(2)：210-215.

[12] 王元彪.智能交通系統(tǒng)中Dijkstra算法的高效實現(xiàn)[J].計算機(jī)工程，2007，33(6):256-258,261.

[13] Cantone D，F(xiàn)aro S.Two-Levels-Greedy:a generalization of Dijkstra’s shortest path algorithm[J].Electronic Notes in Discrete Mathematics,2004,17(20):81-86.

[14] 章永龍.Dijkstra最短路徑算法優(yōu)化[J].南昌工程學(xué)院學(xué)報，2006，25(3)：30-33.

[15] 余冬梅，張秋余，馬少林，等.Dijkstra算法的優(yōu)化[J].計算機(jī)工程，2004，30(22):145-146.

[16] 鮑培明.距離尋優(yōu)中Dijkstra算法的優(yōu)化[J].計算機(jī)研究與發(fā)展,2001，38(3):307-311.

[17] 劉彥良，王鵬濤.復(fù)雜網(wǎng)絡(luò)的優(yōu)化模型及最短路徑求解[J].天津理工大學(xué)學(xué)報，2006，22(1)：33-35.

[18] Han Y J.A note of an O(n3/logn) time algorithm for all pairs shortest paths[J].Information Processing Letters，2008,105(3)：114-116.

[19] 張鑫，劉岳峰，鄭江華，等.針對公交的最優(yōu)路徑算法[J].計算機(jī)工程與應(yīng)用，2006(22):207-209.

(責(zé)任編輯：朱寶昌)

The Optimal Path Searching Algorithm of Urban Public Traffic Systems

DENG Jing-wei

(School of Mathematics and Computer Science，Northwest University for Nationalities，
Gansu Lanzhou，730124，China)

Based on the analysis of the characteristics of urban public transport system, we used the shortest path algorithm to carry on the elaboration and the analysis, then described the shortest path algorithm and improved Dijkstra algorithm. The improved algorithm was applied to the urban public transportation system and finally verified by a simple example. The results showed that the improved algorithm is efficiently better than the Dijkstra algorithm in searching function.

Dijkstra algorithm; urban public traffic network; optimal path

10.3969/J.ISSN.1672-7983.2015.02.014

教育部人文社會科學(xué)研究青年基金項目(項目編號：13YJCZH029;12YJCZH027)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項資金項目(項目編號：31920150039)。

2015-04-21; 修改稿收到日期: 2015-05-24

U491.17

A

1672-7983(2015)02-0066-04

鄧競偉(1980-)，女，講師，碩士。主要研究方向：復(fù)雜網(wǎng)絡(luò)、信息處理。