城市交通最優(yōu)路徑算法

陳亮，何為，韓力群

(北京工商大學(xué)計(jì)算機(jī)與信息工程學(xué)院，北京 100048)

路徑優(yōu)化是路徑規(guī)劃的核心問題，目前應(yīng)用最廣泛的是1959年Dijkstra［1］提出并以其名字命名的Dijkstra算法，可以解決帶有非負(fù)代價函數(shù)值的路網(wǎng)中的單源最短路徑，但是Dijkstra算法的復(fù)雜度為O(n2)［2］，由于路徑規(guī)劃要求實(shí)時性，因此人們在Dijkstra算法基礎(chǔ)上進(jìn)行各種改進(jìn)，如進(jìn)行啟發(fā)式搜索的A*算法［3］、在記憶路徑基礎(chǔ)上的啟發(fā)式搜索算法D*算法［4］等，但是這些算法通常只給出一條最優(yōu)路徑.

本文在路徑規(guī)劃的過程中，利用圖的深度優(yōu)先遍歷［5］算法，尋找源點(diǎn)與終點(diǎn)的所有可達(dá)路徑，并通過限制搜索的路網(wǎng)節(jié)點(diǎn)規(guī)模和限制搜索方向的規(guī)則，進(jìn)行算法的優(yōu)化，最后計(jì)算得到所有可達(dá)路徑的代價函數(shù)值，并按照從小到大的順序進(jìn)行排序.

在將本文的算法應(yīng)用至實(shí)際交通網(wǎng)絡(luò)中時，為了避免大規(guī)模稀疏網(wǎng)絡(luò)造成計(jì)算時間延長，在應(yīng)用優(yōu)化的可達(dá)路徑算法時，將道路網(wǎng)絡(luò)分成2個級別，得到了較好的效果.利用VC++6.0對算法進(jìn)行仿真，將未經(jīng)優(yōu)化的算法與優(yōu)化算法的結(jié)果進(jìn)行比較，并用實(shí)例驗(yàn)證，表明本文的算法能夠很好地實(shí)現(xiàn)實(shí)時性與最優(yōu)有效性.

1 可達(dá)路徑優(yōu)化算法

1.1 各種存儲方式的比較

路徑優(yōu)化問題首先要將實(shí)際道路的拓?fù)浣Y(jié)構(gòu)，通過一定的計(jì)算機(jī)存儲結(jié)構(gòu)進(jìn)行映射.主要的存儲結(jié)構(gòu)形式有鄰接矩陣、鄰接鏈表、十字鏈表、鄰接多重鏈表［6-7］.

鄰接矩陣的優(yōu)勢在于容易判斷2點(diǎn)間的關(guān)系，但缺點(diǎn)是存儲稀疏圖所占用的空間過大，并且算法時間復(fù)雜度較高，為O(n2+m*n)，這對于實(shí)際應(yīng)用中具有成千上萬個節(jié)點(diǎn)的交通路網(wǎng)圖并不合適.十字鏈表和鄰接多重鏈表要求的存儲空間都非常小，但是本身結(jié)構(gòu)較為復(fù)雜，在實(shí)際中應(yīng)用也比較有限.

鄰接鏈表的實(shí)現(xiàn)方法是鏈表，缺點(diǎn)在于不易判斷2點(diǎn)間的關(guān)系，但是對于關(guān)聯(lián)點(diǎn)的查詢較為有效，優(yōu)點(diǎn)是節(jié)省存儲空間，算法時間復(fù)雜度為O(m+n).因此適用于實(shí)際交通網(wǎng)絡(luò)這類大型稀疏圖，本文采用的存儲方式就是鄰接鏈表［8］.

1.2 路徑代價函數(shù)值的計(jì)算

源點(diǎn)和終點(diǎn)間的所有可達(dá)路徑中，路徑總代價函數(shù)值最小者即為最優(yōu)路徑.可達(dá)路徑的總代價函數(shù)值是全部構(gòu)成路段的代價函數(shù)值的總和，此外，由于交叉路口對轉(zhuǎn)向的種種限制，延誤時間可達(dá)到總時間的17% ～35%［9］，因此在計(jì)算每條可達(dá)路徑的代價函數(shù)值時，還必須考慮交叉口轉(zhuǎn)向因素的影響.

在作者前期的工作中［10］，已利用RBF神經(jīng)網(wǎng)絡(luò)方法建立了路段的代價函數(shù)模型，將5種道路屬性作為影響因素設(shè)為RBF網(wǎng)絡(luò)的輸入，網(wǎng)絡(luò)輸出為路段代價函數(shù)值，這5種道路屬性包括:道路交通實(shí)時路況、車道數(shù)、自助紅綠燈數(shù)、路段長度及車輛轉(zhuǎn)向方向?qū)π熊嚧鷥r函數(shù)值的影響，從而為計(jì)算整條路徑的總代價函數(shù)值打下了基礎(chǔ).

但是，計(jì)算整條路徑代價函數(shù)值的難度在于每一條路段的代價函數(shù)值是在已知轉(zhuǎn)向的情況下得到的結(jié)果.因此，本文通過建立前向關(guān)聯(lián)邊，并采用查表的方法解決每一條路徑總的代價函數(shù)值的計(jì)算［11］，即將3個點(diǎn)之間的關(guān)系兩兩合并，得出二維數(shù)組的行數(shù)和列數(shù)，然后將每一段加起來，即可得到每一條路徑的代價函數(shù)值.特別地，在終點(diǎn)和它上一個節(jié)點(diǎn)的代價函數(shù)值的計(jì)算中，設(shè)置了一個數(shù)組存放最后一段路段的代價，因?yàn)橥ǔ５竭_(dá)了終點(diǎn)不存在選擇方向的問題，從而將這個數(shù)組中的值設(shè)置為直行的代價函數(shù)值.以圖1為例，進(jìn)行簡單說明.

圖1 有向圖Fig.1 Directed graph

選取圖中的1、2、3、4、5 點(diǎn)作說明，如圖 2 所示.例如:節(jié)點(diǎn)1指向節(jié)點(diǎn)2、3，那么節(jié)點(diǎn)1的指針指向節(jié)點(diǎn)序列中的2、3，依此類推，將轉(zhuǎn)向條件計(jì)入在下一個節(jié)點(diǎn)中，就是圖2中代價函數(shù)值所代表的.

圖2 前向關(guān)聯(lián)邊結(jié)構(gòu)及其對應(yīng)代價函數(shù)值Fig.2 Associated side of the structure and its cost function value

根據(jù)指針對應(yīng)的節(jié)點(diǎn)序列找到二維數(shù)組的行，再通過下一結(jié)點(diǎn)的偏移量找到對應(yīng)的二維數(shù)組的列，即可求出每一段路徑的代價函數(shù)值，最后將路徑中每一路段的代價函數(shù)值加起來，就得到了整條路徑的代價函數(shù)值，然后根據(jù)代價函數(shù)值從小到大對可達(dá)路徑進(jìn)行排序并顯示出來，供使用者參考選擇［12］.

1.3 城市交通可達(dá)路徑算法的優(yōu)化

本文采用深度優(yōu)先遍歷算法求得交通圖中任意2點(diǎn)之間的所有可達(dá)路徑，具體通過深度優(yōu)先遍歷算法中的迭代算法來實(shí)現(xiàn).迭代算法利用一個堆棧S來記錄訪問過程，當(dāng)初始點(diǎn)(源點(diǎn))壓入棧后，并建立一個visit［］數(shù)組來標(biāo)記節(jié)點(diǎn)是否被訪問過，然后進(jìn)行迭代，步驟如下:

1)檢測堆棧是否為空，若堆棧為空，則迭代結(jié)束;否則，進(jìn)行下一步;

2)訪問源點(diǎn)的鄰接表中的點(diǎn)，找出visit［v］為0的點(diǎn)v，將其標(biāo)記為源點(diǎn)的下一節(jié)點(diǎn)，并置visit［v］的值為1，判斷v是否為終點(diǎn)，如是，則彈出終點(diǎn)，并記錄路徑數(shù)組route［］，否則進(jìn)行下一步;

3)求v的鄰接點(diǎn)表，將v未被訪問過的鄰接頂點(diǎn)壓入棧，同樣進(jìn)行判斷v是否為終點(diǎn)，如是終點(diǎn)則彈出，記錄路徑，否則進(jìn)行下一步;

重復(fù)進(jìn)行1)～3).

設(shè)計(jì)程序流程如圖3所示.在此過程中，每一個節(jié)點(diǎn)都已經(jīng)記錄了上一個節(jié)點(diǎn)，即route［v］，算法結(jié)束后，逆序打印每一條路徑，即可得到圖中任意2點(diǎn)間的所有可達(dá)路徑.

上述算法并不復(fù)雜，對于有向圖中尋找任意2點(diǎn)間所有可達(dá)路徑十分有效.但是該算法存在2個問題:1)搜索很多冗余可達(dá)路徑，不符合常理的“繞路”路徑;2)算法的效率有待提高.針對這2個問題，本小節(jié)將研究優(yōu)化算法的有效規(guī)則.

圖3 可達(dá)路徑搜索算法流程Fig.3 The flowchart of reachable route searching algorithm

1.3.1 城市交通有向圖映射至鄰接鏈表

在作者之前的工作中［10］，已經(jīng)解決了如何將城市交通路網(wǎng)圖抽象為城市交通有向圖，但是無法以數(shù)據(jù)元素在存儲區(qū)中的物理位置來表示元素之間的關(guān)系.可達(dá)路徑算法優(yōu)化問題，首先要將實(shí)際道路的拓?fù)浣Y(jié)構(gòu)通過一定的計(jì)算機(jī)存儲結(jié)構(gòu)進(jìn)行映射，其具體步驟如下:

1)設(shè)定節(jié)點(diǎn)信息.

首先定義節(jié)點(diǎn)信息，包括節(jié)點(diǎn)號、方位、指向下一節(jié)點(diǎn)、在地圖中的橫縱坐標(biāo).

2)定義棧并將節(jié)點(diǎn)壓入棧.

將設(shè)定好的節(jié)點(diǎn)，按照城市交通有向圖連接關(guān)系，壓入棧中.

3)建立前向關(guān)聯(lián)邊結(jié)構(gòu).

根據(jù)城市交通有向圖，按照1.2節(jié)所示，建立前向關(guān)聯(lián)邊結(jié)構(gòu).

經(jīng)過這3個步驟，一張城市交通網(wǎng)絡(luò)有向圖已經(jīng)映射至計(jì)算機(jī)的存儲結(jié)構(gòu)中.

1.3.2 城市可達(dá)路徑算法優(yōu)化

在深度優(yōu)先遍歷搜索可達(dá)路徑算法的基礎(chǔ)上，結(jié)合城市道路交通有向圖，制定3條優(yōu)化規(guī)則，分別是限制搜索區(qū)域、限制可達(dá)路徑的搜索方向、地圖分級搜索，下面來分別解釋這3條優(yōu)化規(guī)則.

1)限制搜索區(qū)域.

對于實(shí)際節(jié)點(diǎn)數(shù)量非常龐大的實(shí)際交通圖，如果遍歷所有圖中的節(jié)點(diǎn)，則將會導(dǎo)致計(jì)算量與計(jì)算時間成倍增加，因此，將交通圖的搜索區(qū)域限制在一定范圍內(nèi)，可以達(dá)到交通誘導(dǎo)系統(tǒng)的實(shí)時性要求［13］.

利用已有的節(jié)點(diǎn)坐標(biāo)信息，將搜索的區(qū)域設(shè)定為以源點(diǎn)和終點(diǎn)連線為對角線的矩形范圍內(nèi)，但是考慮到有時需要從源點(diǎn)先繞行至矩形范圍以外的節(jié)點(diǎn)路徑;因此，將矩形范圍擴(kuò)大一個節(jié)點(diǎn)范圍，如圖4所示.圖中的虛線范圍是以源點(diǎn)和終點(diǎn)為對角線的矩形，實(shí)際限制范圍為虛線矩形向外擴(kuò)一個節(jié)點(diǎn)的距離，即圖中粗實(shí)線矩形范圍.

圖4 限制搜索區(qū)域Fig.4 Limit searching area

2)限制節(jié)點(diǎn)的搜索方向.

源點(diǎn)與終點(diǎn)之間的距離會呈現(xiàn)東西方向相距較遠(yuǎn)，或者南北方向相距較遠(yuǎn)，例如，駕駛者在由東向西行走東西向較長的道路時，一般情況下不會再想到往西回繞道路，因此將這種相反的方向限制住.進(jìn)一步，限制節(jié)點(diǎn)的2個搜索方向，即以源點(diǎn)和終點(diǎn)連線為向量，限制這個向量的2個分量:第1種情況，當(dāng)源點(diǎn)和終點(diǎn)的距離為南北向相距較遠(yuǎn)時，禁止方向?yàn)榉聪?第2種情況，限制2個方向的示意圖如圖5所示.

圖5 限制節(jié)點(diǎn)搜索方向示意Fig.5 Limit node searching direction diagrams

駕駛者從起點(diǎn)出發(fā)時，有時會先向路況較好的相反方向行駛一段路程，這也可能是最優(yōu)路徑，因此不限制源點(diǎn)的行駛方向.

3)路網(wǎng)分級搜索.

路網(wǎng)分級方法:交通管理部門將城市道路分為4個級別，分別是國道以及城市快速路、城市主干路、次干路、支路.本文選取了一級路網(wǎng)和二級路網(wǎng)，即國道以及城市快速路、城市主干路作為主要研究對象，因?yàn)榈图墑e道路的實(shí)時交通路況不易獲得，所以暫不將低級別路網(wǎng)考慮進(jìn)入路徑規(guī)劃中.

實(shí)際的交通路網(wǎng)是龐大的稀疏網(wǎng)絡(luò)，如果考慮將所有的道路節(jié)點(diǎn)都包含進(jìn)算法計(jì)算最優(yōu)路徑，勢必會影響算法的效率;因此，采用將路網(wǎng)分級的方法，減少搜索節(jié)點(diǎn)的數(shù)量，提高算法效率，城市交通路網(wǎng)分級示意圖如圖6所示.

圖6 路網(wǎng)分級搜索示意Fig.6 Road network classification search diagram

具體搜索方法如圖7所示，應(yīng)用本文的可達(dá)路徑搜索算法，計(jì)算出源點(diǎn)與A點(diǎn)之間的最優(yōu)路徑，再找到一級路網(wǎng)中A、B2節(jié)點(diǎn)之間的最優(yōu)路徑，最后確定B點(diǎn)與二級路網(wǎng)中的終點(diǎn)之間的最優(yōu)路徑［14-15］.

確定路網(wǎng)范圍后，最優(yōu)路徑規(guī)劃分為2步進(jìn)行:

1)確定節(jié)點(diǎn).將距離源點(diǎn)和終點(diǎn)最近的2個二級路網(wǎng)節(jié)點(diǎn)看作源點(diǎn)與終點(diǎn)，同樣，再分別確定一級路網(wǎng)中，距離二級路網(wǎng)源點(diǎn)和終點(diǎn)最近的節(jié)點(diǎn)，分別命名為A點(diǎn)和B點(diǎn).

2)應(yīng)用可達(dá)路徑算法.將一級路網(wǎng)看作二級路網(wǎng)的子集，應(yīng)用本文的可達(dá)路徑優(yōu)化算法，計(jì)算出源點(diǎn)與A點(diǎn)之間的最優(yōu)路徑，再找到一級路網(wǎng)中A、B2節(jié)點(diǎn)之間的最優(yōu)路徑，最后確定B點(diǎn)與二級路網(wǎng)中的終點(diǎn)之間的最優(yōu)路徑.

圖7 路網(wǎng)分級搜索流程Fig.7 Road network classification flow chart

2 算法有效性驗(yàn)證及應(yīng)用實(shí)例

2.1 算法有效性驗(yàn)證

為了驗(yàn)證算法的有效性以及高效性，本文通過建立北京市五環(huán)內(nèi)的高等級道路路網(wǎng)圖數(shù)據(jù)作實(shí)驗(yàn)，如圖8所示.由于選取的道路等級較高，在圖中共有39個高級別道路節(jié)點(diǎn).編程工具采用Visual C++6.0，硬件環(huán)境為 Core2 CPU 2 GHz，內(nèi)存2 GB.

圖8 北京市內(nèi)五環(huán)路網(wǎng)Fig.8 Beijing road network within 5th ring map

由表1可知，當(dāng)不加任何限制條件時，運(yùn)行時間非常慢，不滿足實(shí)時性，主要是由于搜索的可達(dá)路徑數(shù)量非常龐大，當(dāng)加入限制條件后，可達(dá)路徑的數(shù)量減少許多，同時仍然能夠找到最優(yōu)路徑，這說明不加限制條件時，深度優(yōu)先算法會找出許多不符合實(shí)際情況的道路，因此加一定的限制條件是可行而且必要的.第2條規(guī)則是限制2個方向，現(xiàn)將限制搜索范圍作為基礎(chǔ)規(guī)則，第2條規(guī)則與只限制一個方向規(guī)則的差異如表2所示.

表1 限制規(guī)則結(jié)果對比Table 1 Limit rules results comparison

表2 單方向與雙向限制結(jié)果對比Table 2 One-direction and two-direction limit searching results comparison

由表2可知，限制雙方向行駛規(guī)則的運(yùn)行時間較單方向限制的規(guī)則成倍地減少，雖然2種規(guī)則下給出的路徑排序不完全相同;但是這2種規(guī)則下給出的最優(yōu)路徑是相同的，這就保證了算法的有效性，而且大大縮短了算法的運(yùn)行時間，證明了雙方向限制條件符合車輛誘導(dǎo)系統(tǒng)的實(shí)時性要求.

2.2 應(yīng)用實(shí)例

本文的實(shí)例選取的是從北京市大興區(qū)的康盛園至海淀區(qū)的北京工商大學(xué)阜成路校區(qū).

1)按照最優(yōu)路徑規(guī)劃的步驟，首先確定節(jié)點(diǎn).圖9(a)中，五角星為源點(diǎn)，一級道路上的節(jié)點(diǎn)為A點(diǎn).

圖9 地圖分級搜索路徑Fig.9 Map hierarchical searching diagram

2)分別找出圖9(a)、(b)、(c)中的可達(dá)路徑，算法的計(jì)算時間如表3所示.

表3 可達(dá)路徑計(jì)算時間Table 3 Reachable path calculating time

由表3可知，算法總共的運(yùn)行時間為5.6 ms，主要是由于優(yōu)化后的算法將搜索的節(jié)點(diǎn)數(shù)控制在較小的范圍內(nèi)，從而達(dá)到了提高搜索效率的目的，通過本例，進(jìn)一步驗(yàn)證了本文所提出算法的有效性與高效性.

3 結(jié)束語

本文提出了一種在城市道路中搜索最優(yōu)路徑的算法，與以往算法不同的是，先考慮了高等級道路網(wǎng)的特點(diǎn)，由于高等級道路節(jié)點(diǎn)較少，再加上可達(dá)路徑算法的優(yōu)化，因此能夠大大降低算法運(yùn)行的復(fù)雜度與運(yùn)算規(guī)模，經(jīng)驗(yàn)證能夠保證算法運(yùn)行的有效性與高效性，然后將低等級道路網(wǎng)絡(luò)與高等級道路網(wǎng)絡(luò)聯(lián)合考慮，在源點(diǎn)和終點(diǎn)分別優(yōu)化搜索可達(dá)路徑，保證了算法應(yīng)用于整個路網(wǎng)的可行性.

［1］DIJKSTRA E W.A note on two problems in connection with graphs［J］.Numerische Mathematik，1959(1):269-271.

［2］ZHAO Yilin.Vehicle location and navigation system［M］.Boston:Artech House，1997:16-102.

［3］張渭軍，王華.城市道路最短路徑的Dijkstra算法優(yōu)化［J］.長安大學(xué)學(xué)報(bào):自然科學(xué)版，2005，25(6):62-65.ZHANG Weijun，WANG Hua.Optimation Dijkstra arithmetic for shortest path of urban traffic net［J］.Journal of Chang’an University:Natural Science Edition，2005，25(6):62-65.

［4］姜桂艷，鄭祖舵.基于記憶機(jī)制的動態(tài)交通路徑優(yōu)化算法［J］.吉林大學(xué)學(xué)報(bào):工程技術(shù)版，2007，37(5):1043-1048.JIANG Guiyan，ZHENG Zuduo.Dynamic traffic path optimization algorithm based on mnemonic mechanism［J］.Journal of Jilin University:Engineering and Technology Edition，2007，37(5):1043-1048.

［5］梁磊.兩點(diǎn)間所有路徑的遍歷算法［J］.科技信息，2010，25(33):86-87.LIANG Lei.All paths between two points of traversal algorithm［J］.Science and Technology Information，2010，25(33):86-87.

［6］譚浩強(qiáng).C++面向?qū)ο蟪绦蛟O(shè)計(jì)［M］.北京:清華大學(xué)出版社，2006:25-60.

［7］嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)［M］.北京:清華大學(xué)出版社，2003:18-190.

［8］任剛，王煒.交通建模中的最短路徑算法研究綜述［C］//第一屆中國交通地理信息系統(tǒng)技術(shù)研討會.武漢，中國，2007:165-173.REN Gang，WANG Wei.Survey on shortest path algorithms in transportation modeling［C］//The First Session of the China Communications Symposium Geographic Information System Technology.Wuhan，China，2007:165-173.

［9］CALDWELL T.On finding minimum routes in a network with turn penalties［J］.Communication of the ACM，1961，4(2):107-108.

［10］陳亮，何為，韓力群.RBF神經(jīng)網(wǎng)絡(luò)的行車路徑代價函數(shù)建模［J］.智能系統(tǒng)學(xué)報(bào)，2011，6(5):424-431.CHEN Liang，HE Wei，HAN Liqun.Radial basis function neural network modeling of the traffic path cost function［J］.CAAI Transactions on Intelligent Systems，2011，6(5):424-431.

［11］劉張雷，史忠科.城市動態(tài)時間最短路徑誘導(dǎo)系統(tǒng)實(shí)現(xiàn)研究［J］.控制工程，2010，17(3):351-355.LIU Zhanglei，SHI Zhongke.Implementation of urban time-dependent shortest route guidance system［J］.Control Engineering of China，2010，17(3):351-355.

［12］萬瑋，劉曄，李立宏，等.采用聯(lián)合優(yōu)化方式的最佳路徑算法研究［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43(30):97-100.WAN Wei，LIU Ye，LI Lihong，et al.Reseach on optimal path search algorithm adopting union optimization method［J］.Computer Engineering and Applications，2007，43(30):97-100.

［13］王亞文，汪西莉，曹菡，等.一種動態(tài)限制搜索區(qū)域的最短路徑規(guī)劃算法［J］.計(jì)算機(jī)應(yīng)用研，2007，24(7):89-91.WANG Yawen，WANG Xili，CAO Han，et al.Shortest route-planning algorithm within dynamic restricted searching area［J］.Application Research of Computer，2007，24(7):89-91.

［14］苗洋，陳奇.嵌入式環(huán)境中分層路徑規(guī)劃算法改進(jìn)［J］.計(jì)算機(jī)工程，2010，36(14):243-245.MIAO Yang，CHEN Qi.Improvement of hierarchical path planning algorithm in embedded environment［J］.Computer Engineering，2010，36(14):243-245.

［15］蘇海濱，張繼濤.限制搜索區(qū)域的分層路徑規(guī)劃新算法［J］.河南大學(xué)學(xué)報(bào):自然科學(xué)版，2008，38(1):81-84.SU Haibin，ZHANG Jitao.A new algorithm of hierarchical route planning with restricted search area［J］.Journal of Henan University:Natural Science，2008，38(1):81-84.