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

1、<p>　　一種增量式多目標(biāo)優(yōu)化的智能交通路徑誘導(dǎo)方法</p><p>　　摘要：路徑誘導(dǎo)是一種主動引導(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ī)劃和局部動態(tài)重規(guī)劃，實(shí)現(xiàn)車輛的實(shí)時路徑誘導(dǎo).仿真結(jié)果表明該方法能有效地解決復(fù)雜路網(wǎng)

2、中車輛的實(shí)時路徑誘導(dǎo)問題. </p><p>　　關(guān)鍵詞：動態(tài)重規(guī)劃；增量搜索；路徑誘導(dǎo) </p><p>　　中圖分類號：U491.123文獻(xiàn)標(biāo)識碼：A </p><p>　　當(dāng)前，緩解城市交通擁堵問題的方法主要有兩種：一是加大城市路網(wǎng)建設(shè)力度，提升路網(wǎng)吞吐量；二是發(fā)展智能交通系統(tǒng)（Intelligent Transportation Systems，ITS），提

3、高道路運(yùn)行效率.針對各大城市越來越有限的土地資源，以智能學(xué)習(xí)的方式，優(yōu)化城市路網(wǎng)運(yùn)營和管理，顯然是一種最實(shí)際的解決方案.動態(tài)交通路徑誘導(dǎo)系統(tǒng)是ITS的一個重要方向，對城市交通路網(wǎng)管理的效果愈發(fā)顯著.它采用檢測技術(shù)、計(jì)算機(jī)技術(shù)、網(wǎng)絡(luò)技術(shù)等高新手段，基于實(shí)時交通信息采集、處理與傳輸，通過中心式、分布式等多種誘導(dǎo)方式，為駕駛員提供交通事件、行程時間和優(yōu)化路徑等動態(tài)信息，可引導(dǎo)駕駛員避開擁擠走最佳行駛路線，從而實(shí)現(xiàn)路網(wǎng)交通流的均衡動態(tài)分配，有效

4、緩解交通擁擠.高效的路徑選擇算法是動態(tài)交通路徑誘導(dǎo)系統(tǒng)的關(guān)鍵技術(shù).從本質(zhì)上來說，路徑選擇算法需集中式收集整個路網(wǎng)信息，選擇恰當(dāng)?shù)慕煌骱瘮?shù)，通過高效的算法對路網(wǎng)進(jìn)行快速更新，動態(tài)地找尋滿足一定約束條件的最優(yōu)路徑.構(gòu)建路網(wǎng)模型，選擇高效算法，動態(tài)地選擇源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最優(yōu)路徑，從局部來說對駕駛員路徑選擇作出最優(yōu)安排，從總體上說可優(yōu)化城市路網(wǎng)流量的均衡分配，解決路網(wǎng)的擁</p><p>　　動態(tài)路徑誘導(dǎo)在ITS、通

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

6、誘導(dǎo)，將歷史數(shù)據(jù)保留，通過算法重用，減少了重新獲取整個路網(wǎng)信息的工作量. </p><p>　　經(jīng)典的路徑誘導(dǎo)方案通常只針對單個因素進(jìn)行優(yōu)化，但實(shí)際上現(xiàn)實(shí)問題往往由多方面因素相互制約，單個因素很難正確描述，因而路徑誘導(dǎo)往往需對多個因素進(jìn)行同時處理和優(yōu)化，即多目標(biāo)路徑誘導(dǎo).作為人工智能的關(guān)鍵方法，啟發(fā)式搜索已應(yīng)用于多目標(biāo)路徑誘導(dǎo)研究，很多學(xué)者進(jìn)行了相關(guān)研究.Stewart和White將A*算法延伸到多個優(yōu)化變量，并

7、利用啟發(fā)式搜索解決路徑誘導(dǎo)，從而提出了多目標(biāo)啟發(fā)式搜索模型5]；Dasgupta改進(jìn)了多目標(biāo)啟發(fā)式搜索，引入非單調(diào)的啟發(fā)信息用于解決VLSI設(shè)計(jì)難題6]；Mandow針對節(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].通過對多個變量進(jìn)行優(yōu)化，多數(shù)狀態(tài)空間搜索規(guī)劃器改進(jìn)了智能規(guī)劃技術(shù)11-13]. </p&

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

9、信息，在之前規(guī)劃的信息前提上再作增量搜索，減少計(jì)算復(fù)雜度，提高算法效率，從而利用動態(tài)局部重規(guī)劃找尋目前狀態(tài)到最終狀態(tài)的最優(yōu)路徑方案. </p><p><b>　　1構(gòu)建路網(wǎng)模型 </b></p><p>　　城市交通網(wǎng)絡(luò)錯綜復(fù)雜，但都是由單個交叉路口構(gòu)成的，可利用圖論法抽象為點(diǎn)線的網(wǎng)格拓?fù)?，用點(diǎn)代表平面交叉口，用線代表路段，如圖1所示.這樣路網(wǎng)可以抽象為由節(jié)點(diǎn)集合、

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

11、</p><p>　　啟發(fā)式搜索算法應(yīng)用到復(fù)雜交通網(wǎng)路，且當(dāng)路況變化頻繁時，啟發(fā)式數(shù)量急劇增長，算法時間消耗較大，適應(yīng)性降低.增量搜索算法能很好地利用路網(wǎng)變化的局部變化信息，避免全局更新，對提高算法的效率具有積極意義. </p><p>　　3基于增量搜索交通動態(tài)路徑誘導(dǎo) </p><p>　　城市復(fù)雜交通網(wǎng)絡(luò)日益擁堵，動態(tài)交通誘導(dǎo)思想可以很好地改善交通狀況.考慮城

12、市交通環(huán)境時刻變化給算法效率帶來的問題，可在之前已有的搜索信息上只對變化的部分進(jìn)行局部動態(tài)重規(guī)劃，從而提高算法效率.增量搜索算法可實(shí)現(xiàn)局部的動態(tài)重規(guī)劃，來解決環(huán)境時刻變化問題.本文將增量搜索算法引入到啟發(fā)式搜索算法，提出了動態(tài)多目標(biāo)路徑誘導(dǎo)算法DMRGA（Dynamic Multiobjective Route Guidance Algorithm），該算法既保留了啟發(fā)式搜索快速高效的特點(diǎn)，又能適應(yīng)于復(fù)雜的動態(tài)網(wǎng)路環(huán)境，進(jìn)行動態(tài)路徑誘導(dǎo)

13、.在本文提出的路網(wǎng)模型上，結(jié)合啟發(fā)式搜索算法和增量搜索算法的思想，進(jìn)行全局規(guī)劃和動態(tài)局部重規(guī)劃，很好地解決了實(shí)時找尋最優(yōu)路徑的問題，解決車輛動態(tài)路徑誘導(dǎo)問題. </p><p>　　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ī)劃，然后在原有基礎(chǔ)上作增量搜索，進(jìn)行動態(tài)重規(guī)劃，實(shí)時調(diào)整最優(yōu)路

14、徑.當(dāng)檢測路網(wǎng)信息發(fā)生變化時，須馬上作出響應(yīng)，動態(tài)調(diào)整目前節(jié)點(diǎn)到最終節(jié)點(diǎn)的最優(yōu)路徑，以免造成不必要的延時，影響路網(wǎng)全局性能. 　　實(shí)驗(yàn)結(jié)果表明，車輛在行駛過程隨著路網(wǎng)某路段權(quán)重的更新，其最優(yōu)行駛路徑也在不斷更新，動態(tài)實(shí)時地調(diào)整行車路線，盡可能減少行車耗時.實(shí)驗(yàn)以一個小型的部分路網(wǎng)作為場景，可以擴(kuò)大到整個路網(wǎng)，實(shí)時給出車輛優(yōu)化路徑. </p><p><b>　　5結(jié)論 </b></p

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

16、提高效率，實(shí)時更新最優(yōu)路徑.最后仿真結(jié)果表明該方法能有效地實(shí)時解決復(fù)雜路網(wǎng)中車輛的動態(tài)路徑誘導(dǎo)問題. </p><p><b>　　參考文獻(xiàn) </b></p><p>　　[1]ZHU Q B. Ants predictive algorithm for path planning of robot in a complex dynamic environmentJ]

17、. Chinese Journal of Computers， 2005， 28（11）： 1898-1906. </p><p>　　[2]KOENIG S， LIKHACHEV M， FURCY D. Lifelong planning A*J]. Artificial Intelligence， 2004， 155（1/2）： 93-146. </p><p>　　[3]YANG J

18、， 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. </p><p>　　[4]XI Y

19、 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. </p><p>　　[5]STEWART S B，WHITE C C. Multiobjective A*J]. Journ

20、al of the ACM， 1991， 38（4）： 775-814. </p><p>　　[6]OLIVEIRA RIOS L H， CHAIMOWICZ L. A survey and classification of A* based bestfirst heuristic search algorithmsC]//Advances in Artificial IntelligenceSBIA.Sao

21、 Bernardo do Campo， Brazil： 2010：253-262. </p><p>　　[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 Inte

22、lligence. San Francisco， USA：2005：218-223. </p><p>　　[8]DASGUPTA P， CHAKRABARTI P P， DESAKAR S C. Multiobjective heuristic searchM]. Morgan Kaufman，1999 </p><p>　　[9]XU Y Y，YUE W Y. A generalize

23、d 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. </

24、p><p>　　[10]HARIKUMAR S， KUMAR S. Iterative deepening multiobjective A*J]. Information Processing Letters， 1996， 58（1）： 11-15. </p><p>　　[11]REFANIDIS， VLAHAVAS I. Multiobjective heuristic statespa

25、ce planningJ]. Artificial Intelligence， 2003， 145（1/2）： 1-32. </p><p>　　[12]SO M B，KAMBHAMDATI S. Sapa： A multiobjective metric temporal plannerJ]. Journal of Artificial Intelligence Research， 2003， 20： 155-

26、194. </p><p>　　[13]SVEN K， MAXIM L， LIU Y X， et al. Incremental heuristic search in AIJ]. AI Magazine，2004， 25（2）：99-112. </p><p>　　[14]WEI W， OUYANG D T， LU N， et al. A multiobjective increment

27、al heuristic search algorithmJ]. Journal of Jilin University：Science Edition， 2009， 47（4）：752-758. </p><p>　　[15]LU Y B， HUO X M， OKTAY A ，et al. Incremental multiscale search algorithm for dynamic path plan

28、ning with low worstcase complexityJ]. IEEE Trannactionn on Systems， Man， and Cyberneticspart B： Cybernetics， 2011， 41（6）：1556-1569. </p><p>　　[16]SVEN K， SUN X X. Comparing realtime and incremental heuristic