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

（中南大學 信息科學與工程學院，湖南 長沙 410075）

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

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

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

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

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

城市交通網(wǎng)絡錯綜復雜，但都是由單個交叉路口構成的，可利用圖論法抽象為點線的網(wǎng)格拓撲，用點代表平面交叉口，用線代表路段，如圖1所示.這樣路網(wǎng)可以抽象為由節(jié)點集合、弧段集合和路權集合等構成的幾何賦權圖.

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

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

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

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

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

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

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

啟發(fā)式搜索就是在搜索過程中對每一個搜索的狀態(tài)到目標狀態(tài)進行代價評估，選擇最好的下一個狀態(tài)直到目標狀態(tài)，從而減少了無用的搜索，提高了算法效率.

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

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

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

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

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

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

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

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

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

6）檢測INIT表是否為零，若不為零則轉到步1）；

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

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

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

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

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

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

動態(tài)多目標路徑誘導算法DMRGA（G，Nstart，Ngoal，U）.

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

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

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

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

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

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

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

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

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

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

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

5）算法結束.

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

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

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

4 仿真與分析

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

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

圖2 長沙市五一路中段道路Fig.2 Middle of Wuyi road in Changsha

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

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

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

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

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

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

5 結 論

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

[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.