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

陳亮，何為，韓力群

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

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

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

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

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

1.1 各種存儲(chǔ)方式的比較

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

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

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

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

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

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

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

圖1 有向圖Fig.1 Directed graph

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

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

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

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

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

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

2)訪問(wèn)源點(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未被訪問(wèn)過(guò)的鄰接頂點(diǎn)壓入棧，同樣進(jìn)行判斷v是否為終點(diǎn)，如是終點(diǎn)則彈出，記錄路徑，否則進(jìn)行下一步;

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

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

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

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

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

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

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

首先定義節(jié)點(diǎn)信息，包括節(jié)點(diǎn)號(hào)、方位、指向下一節(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)過(guò)這3個(gè)步驟，一張城市交通網(wǎng)絡(luò)有向圖已經(jīng)映射至計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu)中.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

具體搜索方法如圖7所示，應(yīng)用本文的可達(dá)路徑搜索算法，計(jì)算出源點(diǎn)與A點(diǎn)之間的最優(yōu)路徑，再找到一級(jí)路網(wǎng)中A、B2節(jié)點(diǎn)之間的最優(yōu)路徑，最后確定B點(diǎn)與二級(jí)路網(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個(gè)二級(jí)路網(wǎng)節(jié)點(diǎn)看作源點(diǎn)與終點(diǎn)，同樣，再分別確定一級(jí)路網(wǎng)中，距離二級(jí)路網(wǎng)源點(diǎn)和終點(diǎn)最近的節(jié)點(diǎn)，分別命名為A點(diǎn)和B點(diǎn).

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

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

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

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

為了驗(yàn)證算法的有效性以及高效性，本文通過(guò)建立北京市五環(huán)內(nèi)的高等級(jí)道路路網(wǎng)圖數(shù)據(jù)作實(shí)驗(yàn)，如圖8所示.由于選取的道路等級(jí)較高，在圖中共有39個(gè)高級(jí)別道路節(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)不加任何限制條件時(shí)，運(yùn)行時(shí)間非常慢，不滿足實(shí)時(shí)性，主要是由于搜索的可達(dá)路徑數(shù)量非常龐大，當(dāng)加入限制條件后，可達(dá)路徑的數(shù)量減少許多，同時(shí)仍然能夠找到最優(yōu)路徑，這說(shuō)明不加限制條件時(shí)，深度優(yōu)先算法會(huì)找出許多不符合實(shí)際情況的道路，因此加一定的限制條件是可行而且必要的.第2條規(guī)則是限制2個(gè)方向，現(xiàn)將限制搜索范圍作為基礎(chǔ)規(guī)則，第2條規(guī)則與只限制一個(gè)方向規(guī)則的差異如表2所示.

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

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

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

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

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

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

圖9 地圖分級(jí)搜索路徑Fig.9 Map hierarchical searching diagram

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

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

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

3 結(jié)束語(yǔ)

本文提出了一種在城市道路中搜索最優(yōu)路徑的算法，與以往算法不同的是，先考慮了高等級(jí)道路網(wǎng)的特點(diǎn)，由于高等級(jí)道路節(jié)點(diǎn)較少，再加上可達(dá)路徑算法的優(yōu)化，因此能夠大大降低算法運(yùn)行的復(fù)雜度與運(yùn)算規(guī)模，經(jīng)驗(yàn)證能夠保證算法運(yùn)行的有效性與高效性，然后將低等級(jí)道路網(wǎng)絡(luò)與高等級(jí)道路網(wǎng)絡(luò)聯(lián)合考慮，在源點(diǎn)和終點(diǎn)分別優(yōu)化搜索可達(dá)路徑，保證了算法應(yīng)用于整個(gè)路網(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］.長(zhǎng)安大學(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ī)制的動(dòng)態(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］//第一屆中國(guó)交通地理信息系統(tǒng)技術(shù)研討會(huì).武漢，中國(guó)，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ò)的行車(chē)路徑代價(jià)函數(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］劉張雷，史忠科.城市動(dòng)態(tài)時(shí)間最短路徑誘導(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］萬(wàn)瑋，劉曄，李立宏，等.采用聯(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］王亞文，汪西莉，曹菡，等.一種動(dòng)態(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.