文孟飛，彭 軍，劉偉榮，李 沖，張曉勇

（中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙 410075）

當(dāng)前，緩解城市交通擁堵問(wèn)題的方法主要有兩種：一是加大城市路網(wǎng)建設(shè)力度，提升路網(wǎng)吞吐量；二是發(fā)展智能交通系統(tǒng)（Intelligent Transportation Systems，ITS），提高道路運(yùn)行效率.針對(duì)各大城市越來(lái)越有限的土地資源，以智能學(xué)習(xí)的方式，優(yōu)化城市路網(wǎng)運(yùn)營(yíng)和管理，顯然是一種最實(shí)際的解決方案.動(dòng)態(tài)交通路徑誘導(dǎo)系統(tǒng)是ITS的一個(gè)重要方向，對(duì)城市交通路網(wǎng)管理的效果愈發(fā)顯著.它采用檢測(cè)技術(shù)、計(jì)算機(jī)技術(shù)、網(wǎng)絡(luò)技術(shù)等高新手段，基于實(shí)時(shí)交通信息采集、處理與傳輸，通過(guò)中心式、分布式等多種誘導(dǎo)方式，為駕駛員提供交通事件、行程時(shí)間和優(yōu)化路徑等動(dòng)態(tài)信息，可引導(dǎo)駕駛員避開擁擠走最佳行駛路線，從而實(shí)現(xiàn)路網(wǎng)交通流的均衡動(dòng)態(tài)分配，有效緩解交通擁擠.高效的路徑選擇算法是動(dòng)態(tài)交通路徑誘導(dǎo)系統(tǒng)的關(guān)鍵技術(shù).從本質(zhì)上來(lái)說(shuō)，路徑選擇算法需集中式收集整個(gè)路網(wǎng)信息，選擇恰當(dāng)?shù)慕煌骱瘮?shù)，通過(guò)高效的算法對(duì)路網(wǎng)進(jìn)行快速更新，動(dòng)態(tài)地找尋滿足一定約束條件的最優(yōu)路徑.構(gòu)建路網(wǎng)模型，選擇高效算法，動(dòng)態(tài)地選擇源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最優(yōu)路徑，從局部來(lái)說(shuō)對(duì)駕駛員路徑選擇作出最優(yōu)安排，從總體上說(shuō)可優(yōu)化城市路網(wǎng)流量的均衡分配，解決路網(wǎng)的擁堵問(wèn)題.

動(dòng)態(tài)路徑誘導(dǎo)在ITS、通信系統(tǒng)和機(jī)器人等人工智能方面應(yīng)用廣泛.若城市路網(wǎng)是靜態(tài)網(wǎng)絡(luò)，路段信息不變且可知，則很容易通過(guò)全局規(guī)劃找尋一條從源狀態(tài)到最終狀態(tài)的最佳路徑.但實(shí)際情況卻是，交通信息時(shí)刻都在變化，環(huán)境信息動(dòng)態(tài)改變，實(shí)際行駛過(guò)程中的路網(wǎng)情況和初始情況差異很大，此時(shí)需不斷更新路網(wǎng)信息，實(shí)時(shí)找尋源狀態(tài)節(jié)點(diǎn)到最終狀態(tài)節(jié)點(diǎn)的動(dòng)態(tài)最優(yōu)路徑.一些學(xué)者已研究了在動(dòng)態(tài)環(huán)境情況下找尋最優(yōu)路徑的方案和算法思想[1－4］，局部重規(guī)劃就是其中一種關(guān)鍵算法，能有效地實(shí)現(xiàn)動(dòng)態(tài)環(huán)境下的路徑誘導(dǎo)，將歷史數(shù)據(jù)保留，通過(guò)算法重用，減少了重新獲取整個(gè)路網(wǎng)信息的工作量.

經(jīng)典的路徑誘導(dǎo)方案通常只針對(duì)單個(gè)因素進(jìn)行優(yōu)化，但實(shí)際上現(xiàn)實(shí)問(wèn)題往往由多方面因素相互制約，單個(gè)因素很難正確描述，因而路徑誘導(dǎo)往往需對(duì)多個(gè)因素進(jìn)行同時(shí)處理和優(yōu)化，即多目標(biāo)路徑誘導(dǎo).作為人工智能的關(guān)鍵方法，啟發(fā)式搜索已應(yīng)用于多目標(biāo)路徑誘導(dǎo)研究，很多學(xué)者進(jìn)行了相關(guān)研究.Stewart和White將A＊算法延伸到多個(gè)優(yōu)化變量，并利用啟發(fā)式搜索解決路徑誘導(dǎo)，從而提出了多目標(biāo)啟發(fā)式搜索模型[5］；Dasgupta改進(jìn)了多目標(biāo)啟發(fā)式搜索，引入非單調(diào)的啟發(fā)信息用于解決VLSI設(shè)計(jì)難題[6］；Mandow針對(duì)節(jié)點(diǎn)難以擴(kuò)展問(wèn)題，將路徑擴(kuò)展引入多目標(biāo)啟發(fā)式搜索，提高了搜索算法的準(zhǔn)確性[6－7］；Harikumar和 Dasgupta總結(jié)了深度優(yōu)先搜索算法在多目標(biāo)路徑誘導(dǎo)上的應(yīng)用[8－10］.通過(guò)對(duì)多個(gè)變量進(jìn)行優(yōu)化，多數(shù)狀態(tài)空間搜索規(guī)劃器改進(jìn)了智能規(guī)劃技術(shù)[11－13］.

文獻(xiàn)[14－16］將增量搜索思想引入路徑誘導(dǎo)局部重規(guī)劃.在許多相似度較高的多目標(biāo)優(yōu)化問(wèn)題中，環(huán)境信息只是局部變化，若重新進(jìn)行全局規(guī)劃會(huì)帶來(lái)不必要的計(jì)算復(fù)雜度，若能夠?qū)v史信息重用，則可提高算法效率.本文提出了一種當(dāng)檢測(cè)到環(huán)境信息動(dòng)態(tài)改變時(shí)，怎樣實(shí)時(shí)選擇最優(yōu)路徑以實(shí)現(xiàn)全局最優(yōu)規(guī)劃的路徑誘導(dǎo)方案，先由當(dāng)前的靜態(tài)路網(wǎng)信息利用啟發(fā)式搜索算法作全局規(guī)劃，找尋最短路徑；車輛行進(jìn)過(guò)程中，一旦路網(wǎng)信息變化，就需不斷更新歷史信息，在之前規(guī)劃的信息前提上再作增量搜索，減少計(jì)算復(fù)雜度，提高算法效率，從而利用動(dòng)態(tài)局部重規(guī)劃找尋目前狀態(tài)到最終狀態(tài)的最優(yōu)路徑方案.

1 構(gòu)建路網(wǎng)模型

城市交通網(wǎng)絡(luò)錯(cuò)綜復(fù)雜，但都是由單個(gè)交叉路口構(gòu)成的，可利用圖論法抽象為點(diǎn)線的網(wǎng)格拓?fù)洌命c(diǎn)代表平面交叉口，用線代表路段，如圖1所示.這樣路網(wǎng)可以抽象為由節(jié)點(diǎn)集合、弧段集合和路權(quán)集合等構(gòu)成的幾何賦權(quán)圖.

圖1 帶路徑權(quán)重的多交叉口路網(wǎng)圖論模型Fig.1 Multi－intersection graph model with path weights

G＝（N，A，C）表示整個(gè)網(wǎng)絡(luò)的狀態(tài)空間圖，N＝ ｛Ni，i＝1，2，…，9｝為交叉口集合，A＝ ｛Ai，i＝1，2，…，11｝為任意兩相鄰交叉口之間的路段，C（Np，Nq）為路段權(quán)重，是指由交叉口Np到交叉口Nq所需代價(jià)值.本文中G為無(wú)向圖，C（Np，Nq）＝C（Nq，Np）.

實(shí)際路網(wǎng)中單個(gè)優(yōu)化變量很難準(zhǔn)確描述復(fù)雜的交通網(wǎng)絡(luò)，本文用多目標(biāo)優(yōu)化變量來(lái)精確描述交通狀態(tài).多目標(biāo)優(yōu)化變量存儲(chǔ)在向量m中，m的維數(shù)反映優(yōu)化變量個(gè)數(shù)，每一個(gè)優(yōu)化變量都反映單因素的優(yōu)化目標(biāo).路段的權(quán)重則是由多個(gè)優(yōu)化變量共同作用的結(jié)果.若考慮該路段車輛排隊(duì)長(zhǎng)度PA，t，車流阻塞密度KA和路段通行能力MA這3個(gè)多優(yōu)化目標(biāo)，則：

式（2）中：vA為路段A上的車輛自由流密度，xA，t為路段A在t時(shí)刻的交通負(fù)荷，LA為路段A的長(zhǎng)度，rA為路段A下游交叉口路口紅燈的相位時(shí)長(zhǎng)，T為信號(hào)周期.式（3）中n為單方向機(jī)動(dòng)車的車道數(shù)量，Lv為阻塞情況下平均車距，Lo為平均車身長(zhǎng)度.式（4）中tg表示該交叉口每個(gè)周期的路燈時(shí)間，to表示綠燈亮?xí)r，第一個(gè)通過(guò)停車線的車所消耗的時(shí)間，ti表示直行右轉(zhuǎn)通過(guò)停車線所需的平均時(shí)間，φ為折扣系數(shù)，通常取0.9.

多目標(biāo)路徑誘導(dǎo)問(wèn)題轉(zhuǎn)換為數(shù)學(xué)模型由四元組〈G，Nstart，Ngoal，U〉來(lái)表示，Nstart∈N 為初始節(jié)點(diǎn)；Ngoal∈N為目標(biāo)狀態(tài)節(jié)點(diǎn)，U為多目標(biāo)評(píng)價(jià)函數(shù)，即為所找路徑d各路段多目標(biāo)權(quán)重之和，如式（5）所示，按照搜索算法找出從Nstart到Ngoal最優(yōu)路徑.

通過(guò)將實(shí)際交通路網(wǎng)抽象出來(lái)，以數(shù)學(xué)形式存儲(chǔ)路網(wǎng)模型.首先根據(jù)啟發(fā)式搜索算法找出從起始狀態(tài)節(jié)點(diǎn)到目標(biāo)狀態(tài)節(jié)點(diǎn)的最優(yōu)路徑；當(dāng)車輛在行駛過(guò)程中某些路段權(quán)重發(fā)生變化，若全局更新則會(huì)降低系統(tǒng)實(shí)時(shí)性，本文通過(guò)動(dòng)態(tài)重規(guī)劃算法對(duì)經(jīng)過(guò)該路段的局部路徑網(wǎng)絡(luò)進(jìn)行代價(jià)更新，從而可提高算法效率和系統(tǒng)實(shí)時(shí)性.

2 多目標(biāo)啟發(fā)式搜索算法

啟發(fā)式搜索就是在搜索過(guò)程中對(duì)每一個(gè)搜索的狀態(tài)到目標(biāo)狀態(tài)進(jìn)行代價(jià)評(píng)估，選擇最好的下一個(gè)狀態(tài)直到目標(biāo)狀態(tài)，從而減少了無(wú)用的搜索，提高了算法效率.

多目標(biāo)啟發(fā)式搜索將多目標(biāo)優(yōu)化變量引入到路徑權(quán)重中去，由權(quán)重函數(shù)C（Np，Nq）算出路段的綜合權(quán)重來(lái)實(shí)現(xiàn)多目標(biāo)問(wèn)題的優(yōu)化.

算法設(shè)計(jì)中除了考慮各路段權(quán)重時(shí)，還要給出從當(dāng)前節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)的評(píng)估值.算法過(guò)程中將目前搜索的各節(jié)點(diǎn)的所有未被搜索的路徑保存在INIT表中，每一條路徑d可由三元組（Nm，g（d），f（d））表示，U為多目標(biāo)評(píng)價(jià)代價(jià)函數(shù)，根據(jù)多目標(biāo)變量得出路徑代價(jià)，END表記錄當(dāng)前找出來(lái)的解路徑代價(jià).其中g(shù)（d）表示從源節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的代價(jià)和，f（d）表示當(dāng)前節(jié)點(diǎn)到最終狀態(tài)節(jié)點(diǎn)的評(píng)估代價(jià)，即啟發(fā)函數(shù)，如式（6），取3個(gè)優(yōu)化變量的歷史平均值作為該路段的變量值，算出從當(dāng)前節(jié)點(diǎn)到最終狀態(tài)節(jié)點(diǎn)平均估計(jì)值，搜索主要以此信息提高效率.

多目標(biāo)啟發(fā)式搜索算法 MHA（〈G，Nstart，Ngoal，U〉，INIT，END）.

該算法輸入變量是〈G，Nstart，Ngoal，U〉，并初始化INIT表與END表，最后輸出Nstart到Ngoal的最優(yōu)路徑.

1）查詢INIT表，根據(jù)多目標(biāo)代價(jià)評(píng)價(jià)函數(shù)U選擇代價(jià)估值最小的dx路徑擴(kuò)展，dx代價(jià)由g（dx）表示；

2）在INIT表查詢并刪除dx的記錄項(xiàng)（Nm，g（dx），f（dx）），然后將dx從Ho（m）移到Hc（m）.其中Ho（m）保存經(jīng)Nm的所有未擴(kuò)展的路徑，Hc（m）保存經(jīng)Nm的所有已擴(kuò)展的路徑；

3）若Nm＝Nstart，則找到一條解路徑，去掉INIT表中小于g（dx）的與其有關(guān)的所有未搜索路徑，并在END表中加入g（dx）；

4）若Nm≠Nstart，則查詢未搜索的所有狀態(tài)Nn，產(chǎn)生到達(dá)Nn的路徑dy，且g（dy）＝g（dx）＋C（Nm，Nn）；

5）如果g（dy）小于Ho（n）∪Hc（n）中任意路徑代價(jià)，則將dy插入Ho（n），并刪除Ho（n）∪Hc（n）中所有小于dy的路徑.計(jì)算路徑dy的代價(jià)估值f（dy），若f（dy）小于 END 中任何解路徑，則將（Nn，g（dy），f（dy））加入INIT 表且保存之前的關(guān)聯(lián)代價(jià)值；

6）檢測(cè)INIT表是否為零，若不為零則轉(zhuǎn)到步1）；

7）輸出搜索出的Nstart和Ngoal間的最優(yōu)路徑，并給出最小代價(jià)值.

啟發(fā)式搜索算法應(yīng)用到復(fù)雜交通網(wǎng)路，且當(dāng)路況變化頻繁時(shí)，啟發(fā)式數(shù)量急劇增長(zhǎng)，算法時(shí)間消耗較大，適應(yīng)性降低.增量搜索算法能很好地利用路網(wǎng)變化的局部變化信息，避免全局更新，對(duì)提高算法的效率具有積極意義.

3 基于增量搜索交通動(dòng)態(tài)路徑誘導(dǎo)

城市復(fù)雜交通網(wǎng)絡(luò)日益擁堵，動(dòng)態(tài)交通誘導(dǎo)思想可以很好地改善交通狀況.考慮城市交通環(huán)境時(shí)刻變化給算法效率帶來(lái)的問(wèn)題，可在之前已有的搜索信息上只對(duì)變化的部分進(jìn)行局部動(dòng)態(tài)重規(guī)劃，從而提高算法效率.增量搜索算法可實(shí)現(xiàn)局部的動(dòng)態(tài)重規(guī)劃，來(lái)解決環(huán)境時(shí)刻變化問(wèn)題.本文將增量搜索算法引入到啟發(fā)式搜索算法，提出了動(dòng)態(tài)多目標(biāo)路徑 誘 導(dǎo) 算 法 DMRGA（Dynamic Multi－objective Route Guidance Algorithm），該算法既保留了啟發(fā)式搜索快速高效的特點(diǎn)，又能適應(yīng)于復(fù)雜的動(dòng)態(tài)網(wǎng)路環(huán)境，進(jìn)行動(dòng)態(tài)路徑誘導(dǎo).在本文提出的路網(wǎng)模型上，結(jié)合啟發(fā)式搜索算法和增量搜索算法的思想，進(jìn)行全局規(guī)劃和動(dòng)態(tài)局部重規(guī)劃，很好地解決了實(shí)時(shí)找尋最優(yōu)路徑的問(wèn)題，解決車輛動(dòng)態(tài)路徑誘導(dǎo)問(wèn)題.

DMRGA算法分為兩部分：全局規(guī)劃及局部動(dòng)態(tài)重規(guī)劃.全局規(guī)劃根據(jù)已知的靜態(tài)城市網(wǎng)路信息找尋源狀態(tài)到最終狀態(tài)的最優(yōu)路徑；局部規(guī)劃則是在路網(wǎng)環(huán)境信息動(dòng)態(tài)變化時(shí)，先在局部做靜態(tài)規(guī)劃，然后在原有基礎(chǔ)上作增量搜索，進(jìn)行動(dòng)態(tài)重規(guī)劃，實(shí)時(shí)調(diào)整最優(yōu)路徑.當(dāng)檢測(cè)路網(wǎng)信息發(fā)生變化時(shí)，須馬上作出響應(yīng)，動(dòng)態(tài)調(diào)整目前節(jié)點(diǎn)到最終節(jié)點(diǎn)的最優(yōu)路徑，以免造成不必要的延時(shí)，影響路網(wǎng)全局性能.

本節(jié)闡述的局部動(dòng)態(tài)重規(guī)劃是多目標(biāo)路徑誘導(dǎo)算法的關(guān)鍵算法，只對(duì)局部變化的信息實(shí)時(shí)更新，引入增量搜索算法動(dòng)態(tài)調(diào)整路徑.動(dòng)態(tài)多目標(biāo)路徑誘導(dǎo)算法DMRGA算法如下.

動(dòng)態(tài)多目標(biāo)路徑誘導(dǎo)算法DMRGA（G，Nstart，Ngoal，U）.

該算法輸入變量 〈G，Nstart，Ngoal，U〉，輸出源狀態(tài)節(jié)點(diǎn)到最終狀態(tài)節(jié)點(diǎn)間的最優(yōu)路徑

1）初始化.INIT ＝ （Ngoal，ggoal，fgoal），END 為空集；

2）全局規(guī)劃.執(zhí)行多目標(biāo)啟發(fā)式搜索過(guò)程MHA（〈G，Nstart，Ngoal，U〉，INIT，END），找 尋 源 狀態(tài)到最終狀態(tài)的最優(yōu)路徑集合，并選擇其中一條；

3）沿著算法得出的路徑行駛，若抵達(dá)最終狀態(tài)，則輸出該條搜索路徑，跳到5）；若移動(dòng)到某個(gè)節(jié)點(diǎn)Nchange時(shí)，其相鄰節(jié)點(diǎn)Nv代價(jià)信息變化，跳到4）；

4）基于增量搜索的局部重規(guī)劃：

Ⅰ 執(zhí)行更新過(guò)程UDDATE（Nchange）；

ⅰ 更新Ho（Nchange）∪Hc（Nchange）中所有包括（Nchange，Nv）的路徑；

ⅱ 令 END′＝Ho（Nchange）∪Hc（Nchange），Hc（Nchange）＝Ho（Nchange）∪Hc（Nchange），接下來(lái)并將Ho（Nchange）置為空集；

ⅲ對(duì)Ngoal擴(kuò)展到Nchange過(guò)程中所有中間狀態(tài)Nu的Ho（Nu）集合中所有路徑代價(jià)gu，接著算出抵達(dá)Nchange節(jié)點(diǎn)的估計(jì)代價(jià)值fu，且END′中解路徑均小于fu，則向INIT′插入記錄（Nu，gu，fu）.

Ⅱ 執(zhí)行多目標(biāo)啟發(fā)式搜索過(guò)程 MHA（〈G，Nchange，Ngoal，U〉，INIT′，END′），重新計(jì)算Nchange與目標(biāo)狀態(tài)Ngoal之間的最優(yōu)路徑集合；

Ⅲ 若成功到達(dá)目標(biāo)節(jié)點(diǎn)，則轉(zhuǎn)移到步驟5），否則跳到Ⅰ繼續(xù)循環(huán)搜索，直至找到目標(biāo)節(jié)點(diǎn).

5）算法結(jié)束.

DMRGA根據(jù)已知的靜態(tài)城市網(wǎng)路信息找尋源狀態(tài)到最終狀態(tài)的最優(yōu)路徑集合，并選擇其中一條，即先做全局規(guī)劃.Ho（m）∪Hc（m）保存了每一個(gè)搜索節(jié)點(diǎn)與最終目標(biāo)節(jié)點(diǎn)間所有的的最優(yōu)路徑.

在向最終目標(biāo)搜索移動(dòng)過(guò)程中，若環(huán)境信息變化，則進(jìn)行DMRGA算法第4步動(dòng)態(tài)局部重規(guī)劃，直至抵達(dá)最終節(jié)點(diǎn).若檢測(cè)到Nchange到Nv之間的路徑代價(jià)發(fā)生變化，則對(duì)Ho（Nchange）∪Hc（Nchange）中經(jīng)過(guò)（Nchange，Nv）的所有路徑代價(jià)進(jìn)行實(shí)時(shí)更新；當(dāng)Nchange與Nv之間出現(xiàn)障礙物阻塞時(shí)，刪除Ho（Nchange）∪Hc（Nchange）中所有經(jīng)過(guò)（Nchange，Nv）的路徑代價(jià).算法動(dòng)態(tài)更新后的Ho（Nchange）∪Hc（Nchange）既為重規(guī)劃過(guò)程所要求解的局部最優(yōu)路徑，重新遍歷Ngoal搜索到Nchange中所經(jīng)過(guò)的節(jié)點(diǎn)Nu的所有未搜索的路徑集合Ho（u），從而產(chǎn)生動(dòng)態(tài)局部重規(guī)劃的初始INIT表.在此INIT表基礎(chǔ)上，以Ngoal為源狀態(tài)節(jié)點(diǎn)，Nchange為最終狀態(tài)節(jié)點(diǎn)進(jìn)行逆向的啟發(fā)式搜索，找尋新的源狀態(tài)節(jié)點(diǎn)到最終狀態(tài)節(jié)點(diǎn)間的最優(yōu)路徑集合.

全局規(guī)劃是從最終狀態(tài)節(jié)點(diǎn)向源狀態(tài)節(jié)點(diǎn)進(jìn)行搜索，然局部重規(guī)劃則是從最終狀態(tài)節(jié)點(diǎn)向發(fā)生變化的節(jié)點(diǎn)進(jìn)行局部搜索，兩次搜索算法相同但意義卻不同.故局部動(dòng)態(tài)重規(guī)劃能很大程度上重用全局規(guī)劃中各狀態(tài)節(jié)點(diǎn)的Ho與Hc，以后的進(jìn)一步重規(guī)劃則是在先前規(guī)劃基礎(chǔ)上進(jìn)行局部增量搜索，盡可能重用歷史信息，提高算法效率.可被重用的歷史信息有兩類：1）初始INIT已提供所有狀態(tài)節(jié)點(diǎn)的所有位擴(kuò)展路徑，而無(wú)需每次規(guī)劃都擴(kuò)展節(jié)點(diǎn)路徑；2）由Ho（Nchange）∪Hc（Nchange）可以直接獲得重規(guī)劃過(guò)程的部分解路徑，而不需要逐個(gè)求解.

4 仿真與分析

本仿真以VS2010作為開發(fā)平臺(tái)，搭建實(shí)驗(yàn)平臺(tái)，選擇長(zhǎng)沙市五一大道中段一段路網(wǎng)，提取出路網(wǎng)模型，驗(yàn)證基于增量搜索的啟發(fā)式路徑誘導(dǎo)方法的效率和實(shí)時(shí)性.

圖2為選擇的長(zhǎng)沙市五一路中段某一道路，本文將交叉路口看作節(jié)點(diǎn)，各路段看作節(jié)點(diǎn)間的連線和權(quán)重，為了便于算法設(shè)計(jì)，將路網(wǎng)抽象如圖3所示的標(biāo)準(zhǔn)網(wǎng)格型網(wǎng)絡(luò).圖3中加深的N2號(hào)表示起點(diǎn)，加深的N17號(hào)為終點(diǎn)，本仿真是從N2尋找到達(dá)N17的最優(yōu)路徑.

圖2 長(zhǎng)沙市五一路中段道路Fig.2 Middle of Wuyi road in Changsha

圖3 長(zhǎng)沙市五一路中段路網(wǎng)模型Fig.3 Model for middle of Wuyi road in Changsha

圖4中權(quán)值加粗表示該路段狀況實(shí)時(shí)變化，加粗箭頭為選出的最優(yōu)路徑.提取出路網(wǎng)后，算法根據(jù)啟發(fā)式搜索進(jìn)行全局規(guī)劃找出最優(yōu)路徑，如圖5所示.隨著車輛行駛到交叉口N6時(shí)，A9路段車流密度及延時(shí)明顯增大，根據(jù)增量算法進(jìn)行局部動(dòng)態(tài)重規(guī)劃，將經(jīng)過(guò)該路段的路徑代價(jià)進(jìn)行局部更新，其他路徑則不變，從而有效地提高了效率，此時(shí)選擇A13路段前進(jìn).當(dāng)?shù)竭_(dá)N11時(shí)，A22路段明顯得到改善，又進(jìn)行動(dòng)態(tài)重規(guī)劃選擇A22繼續(xù)前進(jìn).車輛行駛過(guò)程所需時(shí)間代價(jià)表如表1所示.

圖4 局部動(dòng)態(tài)重規(guī)劃Fig.4 Local dynamic re－planning

圖5 全局規(guī)劃路徑Fig.5 Global path planning

表1 全局規(guī)劃和動(dòng)態(tài)重規(guī)劃時(shí)間比較表Tab.1 Global planning and dynamic re－planning time table

實(shí)驗(yàn)結(jié)果表明，車輛在行駛過(guò)程隨著路網(wǎng)某路段權(quán)重的更新，其最優(yōu)行駛路徑也在不斷更新，動(dòng)態(tài)實(shí)時(shí)地調(diào)整行車路線，盡可能減少行車耗時(shí).實(shí)驗(yàn)以一個(gè)小型的部分路網(wǎng)作為場(chǎng)景，可以擴(kuò)大到整個(gè)路網(wǎng)，實(shí)時(shí)給出車輛優(yōu)化路徑.

5 結(jié) 論

本文針對(duì)時(shí)刻變化的路網(wǎng)信息，提出一種基于增量搜索的多目標(biāo)路徑誘導(dǎo)方法.該方法首先利用圖論法將復(fù)雜路網(wǎng)抽象為點(diǎn)線的賦權(quán)圖，引入多目標(biāo)優(yōu)化變量，建立路網(wǎng)模型.然后在啟發(fā)式搜索基礎(chǔ)上引入增量搜索，結(jié)合全局規(guī)劃和局部動(dòng)態(tài)重規(guī)劃，實(shí)現(xiàn)車輛的動(dòng)態(tài)路徑誘導(dǎo).首先進(jìn)行全局規(guī)劃，利用多目標(biāo)啟發(fā)式搜索算法找尋最優(yōu)路徑集合；當(dāng)檢測(cè)到環(huán)境信息變化時(shí)，進(jìn)行動(dòng)態(tài)局部重規(guī)劃，在盡可能保留前次規(guī)劃的基礎(chǔ)上進(jìn)行增量搜索，減少算法復(fù)雜度，提高效率，實(shí)時(shí)更新最優(yōu)路徑.最后仿真結(jié)果表明該方法能有效地實(shí)時(shí)解決復(fù)雜路網(wǎng)中車輛的動(dòng)態(tài)路徑誘導(dǎo)問(wèn)題.

[1]ZHU Q B.Ants predictive algorithm for path planning of robot in a complex dynamic environment[J］.Chinese Journal of Computers，2005，28（11）：1898－1906.

[2]KOENIG S，LIKHACHEV M，F(xiàn)URCY D.Lifelong planning A＊[J］.Artificial Intelligence，2004，155（1/2）：93－146.

[3]YANG J，ZHANG M.A two－level path planning method for on－road autonomous driving[C］//2th International Conference on Intelligent System Design and Engineering Application，Sanya，China：2012：661－664.

[4]XI Y G，ZHANG C G.Rolling path planning of mobile robot in a kind of dynamic uncertain environment[J］.Acta Automatica Sinica，2002，28（2）：161－175.

[5]STEWART S B，WHITE C C.Multiobjective A＊[J］.Journal of the ACM，1991，38（4）：775－814.

[6]OLIVEIRA RIOS L H，CHAIMOWICZ L.A survey and classification of A＊based best－first heuristic search algorithms[C］//Advances in Artificial Intelligence－SBIA.Sao Bernardo do Campo，Brazil：2010：253－262.

[7]MANDOW L，PEREZ J L DE AL CRUZ.A new approach to multi－objective A＊search[C］//Proceedings of the 19th International Joint Conference on Artificial Intelligence.San Francisco，USA：2005：218－223.

[8]DASGUPTA P，CHAKRABARTI P P，DESAKAR S C.Multiobjective heuristic search[M］.Morgan Kaufman，1999.

[9]XU Y Y，YUE W Y.A generalized framework for BDD－based replanning A＊search[C］//Artifical Intelligences，Networking and Parallel/Distributed Computing.10th ACIN International Conference on Software Engineering.Daegu South Korea，2009：133－139.

[10］HARIKUMAR S，KUMAR S.Iterative deepening multiobjective A＊[J］.Information Processing Letters，1996，58（1）：11－15.

[11］REFANIDIS，VLAHAVAS I.Multiobjective heuristic statespace planning[J］.Artificial Intelligence，2003，145（1/2）：1－32.

[12］SO M B，KAMBHAMDATI S.Sapa：A multi－objective metric temporal planner[J］.Journal of Artificial Intelligence Research，2003，20：155－194.

[13］SVEN K，MAXIM L，LIU Y X，etal.Incremental heuristic search in AI[J］.AI Magazine，2004，25（2）：99－112.

[14］WEI W，OUYANG D T，LU N，etal.A multiobjective incremental heuristic search algorithm[J］.Journal of Jilin University：Science Edition，2009，47（4）：752－758.

[15］LU Y B，HUO X M，OKTAY A ，etal.Incremental multiscale search algorithm for dynamic path planning with low worst－case complexity[J］.IEEE Trannactionn on Systems，Man，and Cybernetics－part B：Cybernetics，2011，41（6）：1556－1569.

[16］SVEN K，SUN X X.Comparing real－time and incremental heuristic search for real－time situated agents[J］.Auton Agent Multi－Agent Syst，2009，18：313－341.