一種增量式多目標(biāo)優(yōu)化的智能交通路徑誘導(dǎo)方法

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

摘要：路徑誘導(dǎo)是一種主動(dòng)引導(dǎo)車輛合理分流來解決城市交通擁堵的方法.本文提出了一種基于增量搜索的多目標(biāo)優(yōu)化路徑誘導(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)車輛的實(shí)時(shí)路徑誘導(dǎo).仿真結(jié)果表明該方法能有效地解決復(fù)雜路網(wǎng)中車輛的實(shí)時(shí)路徑誘導(dǎo)問題.

關(guān)鍵詞：動(dòng)態(tài)重規(guī)劃；增量搜索；路徑誘導(dǎo)

中圖分類號(hào)：U491.123文獻(xiàn)標(biāo)識(shí)碼：A

當(dāng)前，緩解城市交通擁堵問題的方法主要有兩種：一是加大城市路網(wǎng)建設(shè)力度，提升路網(wǎng)吞吐量；二是發(fā)展智能交通系統(tǒng)（Intelligent Transportation Systems，ITS），提高道路運(yùn)行效率.針對(duì)各大城市越來越有限的土地資源，以智能學(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í)交通信息采集、處理與傳輸，通過中心式、分布式等多種誘導(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ì)上來說，路徑選擇算法需集中式收集整個(gè)路網(wǎng)信息，選擇恰當(dāng)?shù)慕煌骱瘮?shù)，通過高效的算法對(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)路徑，從局部來說對(duì)駕駛員路徑選擇作出最優(yōu)安排，從總體上說可優(yōu)化城市路網(wǎng)流量的均衡分配，解決路網(wǎng)的擁堵問題.

動(dòng)態(tài)路徑誘導(dǎo)在ITS、通信系統(tǒng)和機(jī)器人等人工智能方面應(yīng)用廣泛.若城市路網(wǎng)是靜態(tài)網(wǎng)絡(luò)，路段信息不變且可知，則很容易通過全局規(guī)劃找尋一條從源狀態(tài)到最終狀態(tài)的最佳路徑.但實(shí)際情況卻是，交通信息時(shí)刻都在變化，環(huán)境信息動(dòng)態(tài)改變，實(shí)際行駛過程中的路網(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ù)保留，通過算法重用，減少了重新獲取整個(gè)路網(wǎng)信息的工作量.

經(jīng)典的路徑誘導(dǎo)方案通常只針對(duì)單個(gè)因素進(jìn)行優(yōu)化，但實(shí)際上現(xiàn)實(shí)問題往往由多方面因素相互制約，單個(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ò)展問題，將路徑擴(kuò)展引入多目標(biāo)啟發(fā)式搜索，提高了搜索算法的準(zhǔn)確性6-7]；Harikumar和Dasgupta總結(jié)了深度優(yōu)先搜索算法在多目標(biāo)路徑誘導(dǎo)上的應(yīng)用8-10].通過對(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)化問題中，環(huán)境信息只是局部變化，若重新進(jìn)行全局規(guī)劃會(huì)帶來不必要的計(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)過程中，一旦路網(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ù)?，用點(diǎn)代表平面交叉口，用線代表路段，如圖1所示.這樣路網(wǎng)可以抽象為由節(jié)點(diǎn)集合、弧段集合和路權(quán)集合等構(gòu)成的幾何賦權(quán)圖.

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

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

啟發(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í)刻變化給算法效率帶來的問題，可在之前已有的搜索信息上只對(duì)變化的部分進(jìn)行局部動(dòng)態(tài)重規(guī)劃，從而提高算法效率.增量搜索算法可實(shí)現(xiàn)局部的動(dòng)態(tài)重規(guī)劃，來解決環(huán)境時(shí)刻變化問題.本文將增量搜索算法引入到啟發(fā)式搜索算法，提出了動(dòng)態(tài)多目標(biāo)路徑誘導(dǎo)算法DMRGA（Dynamic Multiobjective 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)路徑的問題，解決車輛動(dòng)態(tài)路徑誘導(dǎo)問題.

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)全局性能.

實(shí)驗(yàn)結(jié)果表明，車輛在行駛過程隨著路網(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)問題.

參考文獻(xiàn)

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

[2]KOENIG S， LIKHACHEV M， FURCY D. Lifelong planning A*J]. Artificial Intelligence， 2004， 155（1/2）： 93-146.

[3]YANG J， ZHANG M. A twolevel path planning method for onroad autonomous drivingC]//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 environmentJ]. 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 bestfirst heuristic search algorithmsC]//Advances in Artificial IntelligenceSBIA.Sao Bernardo do Campo， Brazil： 2010：253-262.

[7]MANDOW L， PEREZ J L DE AL CRUZ. A new approach to multiobjective A* searchC]// 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 searchM]. Morgan Kaufman，1999

[9]XU Y Y，YUE W Y. A generalized framework for BDDbased replanning A* searchC]// 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 planningJ]. Artificial Intelligence， 2003， 145（1/2）： 1-32.

[12]SO M B，KAMBHAMDATI S. Sapa： A multiobjective metric temporal plannerJ]. Journal of Artificial Intelligence Research， 2003， 20： 155-194.

[13]SVEN K， MAXIM L， LIU Y X， et al. Incremental heuristic search in AIJ]. AI Magazine，2004， 25（2）：99-112.

[14]WEI W， OUYANG D T， LU N， et al. A multiobjective incremental heuristic search algorithmJ]. Journal of Jilin University：Science Edition， 2009， 47（4）：752-758.

[15]LU Y B， HUO X M， OKTAY A ，et al. Incremental multiscale search algorithm for dynamic path planning with low worstcase complexityJ]. IEEE Trannactionn on Systems， Man， and Cyberneticspart B： Cybernetics， 2011， 41（6）：1556-1569.

[16]SVEN K， SUN X X. Comparing realtime and incremental heuristic search for realtime situated agentsJ]. Auton Agent MultiAgent Syst，2009， 18：313-341.