路網(wǎng)擁塞控制中的多目標路徑?jīng)Q策模型研究

蔣斌　徐驍　楊超　李仁發(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è)定仿真時間步長