蔣斌 徐驍 楊超 李仁發(fā)
摘 要:智能交通系統(tǒng)領(lǐng)域中的路網(wǎng)擁塞控制是解決路網(wǎng)擁塞問題的主要手段之一,針對該問題,利用自底向上的agent建模方式,構(gòu)建一種多目標路徑?jīng)Q策agent移動模型.在該模型中,車輛agent兼顧最短路徑和擁塞避免兩個優(yōu)化目標,通過車輛agent行駛距離最短(最短路徑)和途經(jīng)區(qū)域的擁塞程度最低(擁塞避免)兩個目標優(yōu)化來動態(tài)進行路徑?jīng)Q策.基于多目標路徑?jīng)Q策移動模型一方面能夠?qū)崿F(xiàn)對交通擁堵路段的分流控制,另一方面能夠挖掘網(wǎng)絡(luò)拓撲結(jié)構(gòu)中易發(fā)生擁塞的路口的共同特征,為路網(wǎng)擁塞控制提供幫助.仿真實驗結(jié)果表明,該模型能較好地改善路網(wǎng)結(jié)構(gòu)中的擁塞路段.針對不同鏈路密度及鏈路分布的網(wǎng)絡(luò)所進行的仿真實驗結(jié)果進一步表明,路網(wǎng)結(jié)構(gòu)的鏈路密度對擁塞路段出現(xiàn)在網(wǎng)絡(luò)中的地理位置影響不同,而路口節(jié)點位置影響其擁塞程度;網(wǎng)絡(luò)結(jié)構(gòu)的鏈路分布形態(tài)對發(fā)生擁塞路段的地理位置和擁塞優(yōu)化結(jié)果具有直接影響.
關(guān)鍵詞:多目標優(yōu)化;路網(wǎng)擁塞;agent移動模型
中圖分類號:TP399 文獻標識碼:A
智能交通系統(tǒng)(ITS,Intelligent Transportation Systems)在交通領(lǐng)域的各個方面,例如路徑規(guī)劃、車輛導航及擁塞控制等方面已得到了許多成功應(yīng)用.擁塞控制作為ITS中的一個關(guān)鍵應(yīng)用,一直是研究熱點\[1\].目前,交通擁塞的研究方法大致可以分為3類:1)基于統(tǒng)計物理學的方法,如Liao等人使用熵復雜因果關(guān)系平面法分析交通數(shù)據(jù),實驗結(jié)果表明:其方法在評價交通動態(tài)狀態(tài)分級時效果最好,交通數(shù)據(jù)被分為:擁塞,中級,通暢\[2\].Helbing介紹了多種交通流以及自主性多粒子所描述的系統(tǒng),回顧和比較了交通領(lǐng)域中關(guān)于實證數(shù)據(jù)、行人和車輛通行的主要方法以及微觀中觀宏觀三種模型\[3\]. 2)基于數(shù)學規(guī)劃的方法.1985年,Sheffi運用數(shù)學動態(tài)規(guī)劃及其建模方法,系統(tǒng)地闡述了交通流量的擁塞問題,并且提出了多種用戶均衡狀態(tài)及交通流建模的解決方案\[4\].文孟飛等人利用一種基于增量搜索的多目標優(yōu)化方法實現(xiàn)了車輛的實時路徑誘導\[5\].3)基于ABMS(agentBased Modeling and Simulation)的智能交通擁塞控制方法.例如,Narzt等人運用昆蟲群集產(chǎn)生的電子信息素,通過對其它車輛信息素的搜集、區(qū)分及避開擁塞,采用非集中控制的方式在仿真交通系統(tǒng)中分析汽車多種規(guī)避擁塞的不同策略\[6\]. 梁滿朝、李文勇等人針對城市交通信號控制的動態(tài)路徑優(yōu)化問題,綜合考慮了路口距離和道路的飽和程度,通過基于蟻群算法和群決策理論的動態(tài)路徑優(yōu)化算法模型,并證明了其有效性\[7\]. Buscema等人則考慮駕駛員行為偏好對路徑選擇的影響,指出駕駛員對于路徑的選擇不僅僅依賴于交通引導系統(tǒng)同時也依賴于駕駛員的主觀感覺\[8\].此外,文獻\[9\]提出了一種基于agent的智能駕駛模型,通過結(jié)合網(wǎng)絡(luò)、車輛信息共享更新的基礎(chǔ)設(shè)備和自適應(yīng)巡航聯(lián)合控制的方法,證明了該agent智能駕駛模型的實用性以及如何使用該技術(shù)減少擁塞.
湖南大學學報(自然科學版)2015年第4期蔣 斌等:路網(wǎng)擁塞控制中的多目標路徑?jīng)Q策模型研究
交通系統(tǒng)涉及個體自主駕駛行為與復雜交通環(huán)境之間的實時交互和反饋機制,屬于典型的復雜系統(tǒng)研究范疇.本文采用自底向上的ABMS方法,聯(lián)系微觀個體行為與宏觀交通涌現(xiàn)現(xiàn)象來研究智能交通系統(tǒng)的擁塞控制問題.現(xiàn)有基于agent的擁塞控制方法主要從車輛個體行為出發(fā)來研究改善擁塞的方法,預(yù)測駕駛時間或者用戶行為,缺乏一定的宏觀視角分析整個交通系統(tǒng)擁塞分布的涌現(xiàn),從多目標優(yōu)化的角度來實現(xiàn)網(wǎng)絡(luò)擁塞均衡算法也較少.針對上述問題,本文提出一種基于多目標路網(wǎng)擁塞均衡算法的agent移動模型,同時考慮最短路徑和擁塞避免兩個目標來動態(tài)決定車輛agent的移動目標,依據(jù)該優(yōu)化策略自主地向各自預(yù)定目標移動,以實現(xiàn)整個網(wǎng)絡(luò)擁塞動態(tài)均衡的目的.
1 ODD協(xié)議模型描述
通過ODD協(xié)議(Overview, Design concepts,Details)\[10\]描述基于多目標路網(wǎng)擁塞均衡算法的agent移動模型的設(shè)計與實現(xiàn).
1.1 目的
本文提出一種基于多目標路徑?jīng)Q策移動模型分析路網(wǎng)的擁塞問題.模型同時考慮最短路徑和擁塞避免兩個目標的優(yōu)化,確保車輛抵達目的地的過程中整個網(wǎng)絡(luò)擁塞得到改善.仿真實驗驗證了模型的有效性,同時針對不同鏈路密度和鏈路分布的模型試驗,分析了不同網(wǎng)絡(luò)結(jié)構(gòu)對擁塞涌現(xiàn)和優(yōu)化結(jié)果的影響,為實際路網(wǎng)中擁塞控制提供理論參考.
1.2 實體, 狀態(tài)變量和尺度
如表1所示,模型包含兩類實體:路口節(jié)點和車輛.其中,路口節(jié)點表示仿真實驗預(yù)定義的路網(wǎng)結(jié)構(gòu)中的交通路口節(jié)點,車輛定義為網(wǎng)絡(luò)中依據(jù)一定移動策略自主移動的agent.
表2給出了模型中的狀態(tài)變量:1)路口節(jié)點狀態(tài),包括節(jié)點飽和度和當前等待的車輛agent隊列,節(jié)點飽和度指交通路口的最大通行能力,當車輛agent數(shù)目達到上限時將飽和度置1(具體定義及計算見2.4);2)網(wǎng)絡(luò)鏈路狀態(tài),表示整個路網(wǎng)不同路口節(jié)點間的連接狀況(即網(wǎng)絡(luò)中的邊);3)車輛agent的狀態(tài),包括出發(fā)地、目的地、當前路徑及當前狀態(tài)(等待或是移動至下一路口).對于每個路口節(jié)點r,我們定義狀態(tài)變量Ux來描述其在時刻t的擁塞狀況為:
Ux=preA(r,t)desiG(r,t), (1)
其中,preA(r, t)表示節(jié)點r在時刻t的前置影響,desiG(r,t)表示節(jié)點r在時刻t的節(jié)點飽和度,具體計算見1.4.本文中,為了簡化計算,我們將preA(r, t)的值設(shè)置為1.
表2 狀態(tài)變量定義及其描述
Tab.2 Status variables definition and description
1.3 過程與調(diào)度
仿真過程中,每個agent抵到一個路口節(jié)點i,會根據(jù)該路口節(jié)點i的鄰接節(jié)點集Si={v1, v2,…,vj,…,vn}進行計算(vj表示與節(jié)點i相鄰的節(jié)點j),通過多目標優(yōu)化算法計算集合中所有節(jié)點的效用值(效用函數(shù)定義及計算見2.6),處于移動狀態(tài)的agent會選擇集合Si中效用值最小的節(jié)點作為目標節(jié)點.若agent移動后到達最終目標路口節(jié)點,則將該agent從路網(wǎng)中移除.每一個仿真周期將執(zhí)行兩類實體和整個網(wǎng)絡(luò)狀態(tài)的更新.圖1是對該仿真過程和調(diào)度的偽代碼描述.
1.4 設(shè)計理念
基本原理. 本模型設(shè)計的主要原理來自于Sheffi提出的城市路網(wǎng)車流均衡最優(yōu)化理論[4].擁塞作為交通復雜系統(tǒng)中最重要的機制之一,直接影響著通行時間,并與該交通節(jié)點的車流數(shù)目相關(guān).在給定網(wǎng)絡(luò)結(jié)構(gòu)和平流量數(shù)據(jù)時,Sheffi將影響交通通行的因子細化為多類,其中最為重要的一點即是鏈路函數(shù),鏈路函數(shù)反應(yīng)為該道路關(guān)于車輛流量的通行時間函數(shù),通過時間的長短將直接反應(yīng)出車流擁塞的程度.Sheffi還提出UE(userequilibrium)狀態(tài)理論,即沒有駕駛員能夠通過改變路徑縮短他們的通行時間,該理想狀態(tài)在實際情況中很難達到.針對UE狀態(tài),他提出了多種解決該類均衡問題的方法,并指出最小路徑樹(Label connecting algorithm)方法是其中最有效的辦法之一.根據(jù)Sheffi的理論和建模方法,我們的模型選取避免擁塞和最短路徑作為兩個考慮的優(yōu)化目標,并基于其理論來建立我們agent移動模型的相關(guān)參數(shù)和移動規(guī)則.
Sheffi理論大多是建立在宏觀車流數(shù)學模型之上,通過數(shù)學規(guī)劃等方法為達到某種平衡而進行計算.模型結(jié)合其理論,將交通復雜系統(tǒng)通過多agent系統(tǒng)進行模擬仿真,將個體移動策略和全局擁塞分布動態(tài)聯(lián)系起來,是交通領(lǐng)域仿真模擬的新嘗試.
涌現(xiàn). 隨著車輛agent在路網(wǎng)中的自主移動,將形成路網(wǎng)中各路口節(jié)點不同的擁塞分布,并涌現(xiàn)出某些擁塞特別嚴重的路口節(jié)點.研究agent移動策略與擁塞現(xiàn)象涌現(xiàn)的內(nèi)在聯(lián)系,對實現(xiàn)擁塞均衡具有很大的意義.
適應(yīng)性. 在模型中, 車輛agent會基于最短路徑和擁塞避免兩個原則決定最終移動目標.車輛agent在移動過程中會基于周邊路口節(jié)點的擁塞程度改變移動策略.
目標. 假設(shè)路口節(jié)點的最大車輛通行數(shù)量為Max,若節(jié)點r在仿真時間步t內(nèi)通過的車輛數(shù)目為v,則節(jié)點r在時刻t的飽和度desiG定義為
desiG(r,t)=1v≥Max;
v+1Maxv 假設(shè)網(wǎng)絡(luò)由N個節(jié)點構(gòu)成,仿真實驗結(jié)束時間步為End,則定義模型的目標函數(shù)為整個仿真過程中的平均節(jié)點飽和度之和nwval,其值越小則整個網(wǎng)絡(luò)的擁塞分布情況越好. nwval=∑Endt=0∑Nr=1desiG(r,t).(3) 隨機特性. 模型中車輛agent的出發(fā)地、目的地以及加入到網(wǎng)絡(luò)中的時間都是隨機設(shè)定的.在每一個仿真時間步,車輛agent基于效用函數(shù)的計算決定下一目標路口節(jié)點,該效用函數(shù)的定義不僅考慮了主要因素的影響,還通過高斯隨機函數(shù)模擬了車輛移動過程中隨機影響. 觀察. 為分析不同網(wǎng)絡(luò)拓撲結(jié)構(gòu)下路口節(jié)點擁塞狀況的涌現(xiàn)特征,在每個仿真時間步,記錄下所有路口節(jié)點的節(jié)點飽和度desiG和整個模型的目標函數(shù)值nwval. 1.5 初始化 初始化階段,模型隨機產(chǎn)生500個具有不同移動策略、出發(fā)點和目的地的車輛agent;不同agent類別之間的比例,效用函數(shù)中的權(quán)值設(shè)定,根據(jù)實驗?zāi)康木唧w設(shè)定. 1.6 子模型 我們所定義的agent移動模型理論來自于朗之萬方程,假定agent移動是由主導因子和隨機因子兩部分共同的作用結(jié)果.據(jù)此我們定義agent的移動效用方程,見式(4),其中Λ(Ux,t,λ)代表了相鄰節(jié)點x在時間t的效用值.車輛agent i將會選擇其相鄰節(jié)點集合Si={v1,v2,…,vn}中效用值最小的一個作為目標節(jié)點.式(4)中的f(Ux,t)表示的是周邊路口節(jié)點x在時間t對車輛agent移動的外部作用,其值動態(tài)反應(yīng)了該鄰接節(jié)點x的飽和程度;g(x,t)代表對agent的路徑約束, 其值直接反應(yīng)出agent距離最終目標節(jié)點的路徑長度,g(x,t)將會約束agent朝著目的地行進.參數(shù)λ是這兩個目標之間(最短路徑和擁塞避免)的權(quán)值.此外, 為了保持移動過程中具有一定的隨機性, 我們在效用函數(shù)中加入高斯隨機擾動Gauss, Λ(Ux,t,λ)=(1-λ)f(Ux,t)+ λg(x,t)+Gauss. (4) 為簡化仿真實驗,我們進行了如下約束:在每個仿真時間步,每個路口節(jié)點只允許單個車輛agent通過,其他車輛按到達該路口節(jié)點的次序進入車輛agent隊列尾部等待. 2 實驗設(shè)定及結(jié)果 如表3所示,我們執(zhí)行3組實驗來分別1)驗證基于多目標的agent移動模型對網(wǎng)絡(luò)擁塞均衡的有效性,2)分析網(wǎng)絡(luò)鏈路密度對擁塞的影響. 對擁塞均衡的影響 網(wǎng)絡(luò)結(jié)構(gòu)及節(jié)點飽和度分析 分析網(wǎng)絡(luò)鏈路分布形態(tài)對擁塞的影響.仿真實驗中定義了兩類agent:第一類Floyd agent將沿著最短路徑向目的地移動;第二類Autonomous agent將同時考慮最短路徑和擁塞避免兩個優(yōu)化目標,根據(jù)效用函數(shù)公式(4)向目的地自主移動.通過仿真實驗采用的網(wǎng)絡(luò)拓撲結(jié)構(gòu)以及兩類agent在不同比例和權(quán)值下的網(wǎng)絡(luò)節(jié)點飽和度分布來分析仿真結(jié)果.3組實驗都分別給出了本組仿真所采用的網(wǎng)絡(luò)拓撲結(jié)構(gòu). 特別的,實驗2和3中的網(wǎng)絡(luò)拓撲結(jié)構(gòu)分別按照鏈路數(shù)目、鏈路分布形態(tài)的不同進行對比實驗,實驗2中用黑色圓圈進行標識的節(jié)點表示在仿真過程中出現(xiàn)明顯擁塞或異常的節(jié)點.3組仿真實驗都給出對應(yīng)其網(wǎng)絡(luò)拓撲結(jié)構(gòu)的平均節(jié)點飽和度分布,3種不同形狀的圖標(菱形、正方形、三角形)分別表示采用不同比例和權(quán)值構(gòu)成的agent運行得到的仿真實驗結(jié)果.如表4所示,3組仿真實驗中,當網(wǎng)絡(luò)中只含有Floyd agent時,用菱形圖標表示網(wǎng)絡(luò)節(jié)點的飽和度,而當兩類agent各占50%,權(quán)值為0.85和0.15(實驗1)或者0.95和0.2(實驗2和3)時,網(wǎng)絡(luò)節(jié)點飽和度分別采用正方形和三角形表示.表5給出了實驗的參數(shù)設(shè)定.500個車輛agent將在前50個時間步隨機加入到預(yù)定義的網(wǎng)絡(luò)結(jié)構(gòu)中,為保證所有agent都能夠達到目的地,設(shè)定仿真時間步長