蔣 斌,徐 驍,楊 超, 2,李仁發(fā)

(1．湖南大學 信息科學與工程學院,湖南 長沙 410082；2．東京工業(yè)大學 智能系統(tǒng)科學專攻 日本國,神奈川縣 橫濱市 226-8502)

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

蔣 斌1, 2?,徐 驍1,楊 超1, 2,李仁發(fā)1

(1．湖南大學 信息科學與工程學院,湖南 長沙 410082；2．東京工業(yè)大學 智能系統(tǒng)科學專攻 日本國,神奈川縣 橫濱市 226-8502)

智能交通系統(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)絡拓撲結(jié)構(gòu)中易發(fā)生擁塞的路口的共同特征，為路網(wǎng)擁塞控制提供幫助．仿真實驗結(jié)果表明，該模型能較好地改善路網(wǎng)結(jié)構(gòu)中的擁塞路段．針對不同鏈路密度及鏈路分布的網(wǎng)絡所進行的仿真實驗結(jié)果進一步表明，路網(wǎng)結(jié)構(gòu)的鏈路密度對擁塞路段出現(xiàn)在網(wǎng)絡中的地理位置影響不同，而路口節(jié)點位置影響其擁塞程度；網(wǎng)絡結(jié)構(gòu)的鏈路分布形態(tài)對發(fā)生擁塞路段的地理位置和擁塞優(yōu)化結(jié)果具有直接影響．

多目標優(yōu)化；路網(wǎng)擁塞；agent移動模型

智能交通系統(tǒng)(ITS，Intelligent Transportation Systems)在交通領(lǐng)域的各個方面，例如路徑規(guī)劃、車輛導航及擁塞控制等方面已得到了許多成功應用．擁塞控制作為ITS中的一個關(guān)鍵應用，一直是研究熱點[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(agent-Based Modeling and Simula-tion)的智能交通擁塞控制方法.例如，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)絡、車輛信息共享更新的基礎設備和自適應巡航聯(lián)合控制的方法，證明了該agent智能駕駛模型的實用性以及如何使用該技術(shù)減少擁塞.

交通系統(tǒng)涉及個體自主駕駛行為與復雜交通環(huán)境之間的實時交互和反饋機制，屬于典型的復雜系統(tǒng)研究范疇.本文采用自底向上的ABMS方法，聯(lián)系微觀個體行為與宏觀交通涌現(xiàn)現(xiàn)象來研究智能交通系統(tǒng)的擁塞控制問題.現(xiàn)有基于agent的擁塞控制方法主要從車輛個體行為出發(fā)來研究改善擁塞的方法，預測駕駛時間或者用戶行為，缺乏一定的宏觀視角分析整個交通系統(tǒng)擁塞分布的涌現(xiàn)，從多目標優(yōu)化的角度來實現(xiàn)網(wǎng)絡擁塞均衡算法也較少.針對上述問題，本文提出一種基于多目標路網(wǎng)擁塞均衡算法的agent移動模型，同時考慮最短路徑和擁塞避免兩個目標來動態(tài)決定車輛agent的移動目標，依據(jù)該優(yōu)化策略自主地向各自預定目標移動，以實現(xiàn)整個網(wǎng)絡擁塞動態(tài)均衡的目的.

1 ODD協(xié)議模型描述

通過ODD協(xié)議(Overview, Design concepts，Details)[10]描述基于多目標路網(wǎng)擁塞均衡算法的agent移動模型的設計與實現(xiàn).

1.1 目的

本文提出一種基于多目標路徑?jīng)Q策移動模型分析路網(wǎng)的擁塞問題.模型同時考慮最短路徑和擁塞避免兩個目標的優(yōu)化，確保車輛抵達目的地的過程中整個網(wǎng)絡擁塞得到改善.仿真實驗驗證了模型的有效性，同時針對不同鏈路密度和鏈路分布的模型試驗，分析了不同網(wǎng)絡結(jié)構(gòu)對擁塞涌現(xiàn)和優(yōu)化結(jié)果的影響，為實際路網(wǎng)中擁塞控制提供理論參考.

1.2 實體, 狀態(tài)變量和尺度

如表1所示，模型包含兩類實體：路口節(jié)點和車輛.其中，路口節(jié)點表示仿真實驗預定義的路網(wǎng)結(jié)構(gòu)中的交通路口節(jié)點，車輛定義為網(wǎng)絡中依據(jù)一定移動策略自主移動的agent.

表1 實體定義及其描述

表2給出了模型中的狀態(tài)變量：1)路口節(jié)點狀態(tài)，包括節(jié)點飽和度和當前等待的車輛agent隊列，節(jié)點飽和度指交通路口的最大通行能力，當車輛agent數(shù)目達到上限時將飽和度置1(具體定義及計算見2.4)；2)網(wǎng)絡鏈路狀態(tài)，表示整個路網(wǎng)不同路口節(jié)點間的連接狀況(即網(wǎng)絡中的邊)；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)的值設置為1.

表2 狀態(tài)變量定義及其描述

1.3 過程與調(diào)度

1.4 設計理念

基本原理. 本模型設計的主要原理來自于Sheffi提出的城市路網(wǎng)車流均衡最優(yōu)化理論[4].擁塞作為交通復雜系統(tǒng)中最重要的機制之一，直接影響著通行時間，并與該交通節(jié)點的車流數(shù)目相關(guān).在給定網(wǎng)絡結(jié)構(gòu)和平流量數(shù)據(jù)時，Sheffi將影響交通通行的因子細化為多類，其中最為重要的一點即是鏈路函數(shù)，鏈路函數(shù)反應為該道路關(guān)于車輛流量的通行時間函數(shù)，通過時間的長短將直接反應出車流擁塞的程度.Sheffi還提出UE(user-equilibrium)狀態(tài)理論，即沒有駕駛員能夠通過改變路徑縮短他們的通行時間，該理想狀態(tài)在實際情況中很難達到.針對UE狀態(tài),他提出了多種解決該類均衡問題的方法，并指出最小路徑樹(Labelconnectingalgorithm)方法是其中最有效的辦法之一.根據(jù)Sheffi的理論和建模方法，我們的模型選取避免擁塞和最短路徑作為兩個考慮的優(yōu)化目標，并基于其理論來建立我們agent移動模型的相關(guān)參數(shù)和移動規(guī)則.

每一個仿真周期

開始

fori= 0 to 最大車輛agent數(shù)

初始化網(wǎng)絡中所有的車輛agent；

end for

fori= 0 to 最大路口節(jié)點數(shù)

初始化網(wǎng)絡中所有的路口節(jié)點；

end for

for 仿真時間步 = 0 to 仿真終止時間步

fori= 0 to 最大車輛agent數(shù)

if (仿真時間步== agent加入模型時間步)

添加agent到路網(wǎng)中；

end if

end for

更新網(wǎng)絡中的路口節(jié)點信息；

fori= 0 to最大車輛agent數(shù)

if (agent在路網(wǎng)中 & agent處于移動狀態(tài))

計算agent 的下一跳節(jié)點并移動；

if (agent到達最終目的地)

從網(wǎng)絡中移除該agent；

end if

end if

end for

end for

End

圖1 agent移動模型的偽代碼描述

Fig.1 The pseudo code description of agent mobile model

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)擁塞均衡具有很大的意義.

適應性. 在模型中, 車輛agent會基于最短路徑和擁塞避免兩個原則決定最終移動目標.車輛agent在移動過程中會基于周邊路口節(jié)點的擁塞程度改變移動策略.

目標. 假設路口節(jié)點的最大車輛通行數(shù)量為Max，若節(jié)點r在仿真時間步t內(nèi)通過的車輛數(shù)目為v，則節(jié)點r在時刻t的飽和度desiG定義為

(2)

假設網(wǎng)絡由N個節(jié)點構(gòu)成，仿真實驗結(jié)束時間步為End，則定義模型的目標函數(shù)為整個仿真過程中的平均節(jié)點飽和度之和nwval，其值越小則整個網(wǎng)絡的擁塞分布情況越好.

(3)

隨機特性. 模型中車輛agent的出發(fā)地、目的地以及加入到網(wǎng)絡中的時間都是隨機設定的.在每一個仿真時間步，車輛agent基于效用函數(shù)的計算決定下一目標路口節(jié)點，該效用函數(shù)的定義不僅考慮了主要因素的影響，還通過高斯隨機函數(shù)模擬了車輛移動過程中隨機影響.

觀察. 為分析不同網(wǎng)絡拓撲結(jié)構(gòu)下路口節(jié)點擁塞狀況的涌現(xiàn)特征，在每個仿真時間步，記錄下所有路口節(jié)點的節(jié)點飽和度desiG和整個模型的目標函數(shù)值nwval.

1.5 初始化

初始化階段，模型隨機產(chǎn)生500個具有不同移動策略、出發(fā)點和目的地的車輛agent；不同agent類別之間的比例,效用函數(shù)中的權(quán)值設定,根據(jù)實驗目的具體設定.

1.6 子模型

Λ(Ux,t,λ)=(1-λ)f(Ux,t)+

λg(x,t)+Gauss．

(4)

為簡化仿真實驗，我們進行了如下約束：在每個仿真時間步，每個路口節(jié)點只允許單個車輛agent通過，其他車輛按到達該路口節(jié)點的次序進入車輛agent隊列尾部等待.

2 實驗設定及結(jié)果

如表3所示，我們執(zhí)行3組實驗來分別1)驗證基于多目標的agent移動模型對網(wǎng)絡擁塞均衡的有效性，2)分析網(wǎng)絡鏈路密度對擁塞的影響．

表3 3組仿真實驗描述

分析網(wǎng)絡鏈路分布形態(tài)對擁塞的影響.仿真實驗中定義了兩類agent：第一類Floyd agent將沿著最短路徑向目的地移動；第二類Autonomous agent將同時考慮最短路徑和擁塞避免兩個優(yōu)化目標，根據(jù)效用函數(shù)公式(4)向目的地自主移動.通過仿真實驗采用的網(wǎng)絡拓撲結(jié)構(gòu)以及兩類agent在不同比例和權(quán)值下的網(wǎng)絡節(jié)點飽和度分布來分析仿真結(jié)果．3組實驗都分別給出了本組仿真所采用的網(wǎng)絡拓撲結(jié)構(gòu).

特別的，實驗2和3中的網(wǎng)絡拓撲結(jié)構(gòu)分別按照鏈路數(shù)目、鏈路分布形態(tài)的不同進行對比實驗，實驗2中用黑色圓圈進行標識的節(jié)點表示在仿真過程中出現(xiàn)明顯擁塞或異常的節(jié)點.3組仿真實驗都給出對應其網(wǎng)絡拓撲結(jié)構(gòu)的平均節(jié)點飽和度分布，3種不同形狀的圖標(菱形、正方形、三角形)分別表示采用不同比例和權(quán)值構(gòu)成的agent運行得到的仿真實驗結(jié)果.如表4所示，3組仿真實驗中，當網(wǎng)絡中只含有Floyd agent時，用菱形圖標表示網(wǎng)絡節(jié)點的飽和度，而當兩類agent各占50%，權(quán)值為0.85和0.15(實驗1)或者0.95和0.2(實驗2和3)時，網(wǎng)絡節(jié)點飽和度分別采用正方形和三角形表示.表5給出了實驗的參數(shù)設定.500個車輛agent將在前50個時間步隨機加入到預定義的網(wǎng)絡結(jié)構(gòu)中，為保證所有agent都能夠達到目的地，設定仿真時間步長為500.同時，為了保證實驗結(jié)果的魯棒性和準確性，取50次仿真實驗的平均值為每組仿真實驗的最終結(jié)果.表6給出了車輛agent移動模型的相關(guān)參數(shù)設定.

表4 仿真實驗中采用的agent分組及其策略、權(quán)值設定

表5 實驗參數(shù)設定

表6 車輛agent移動模型的參數(shù)設定

2.1 實驗1 基于多目標優(yōu)化的agent移動模型對網(wǎng)絡擁塞均衡的有效性驗證

第一個實驗中，通過比較相同網(wǎng)絡結(jié)構(gòu)下采用單目標(Floyd)策略和采用多目標(Autonomous)策略的agent移動形成的網(wǎng)絡擁塞分布結(jié)果，驗證我們提出的多目標agent移動模型對網(wǎng)絡擁塞均衡的有效性.

仿真實驗的網(wǎng)絡結(jié)構(gòu)如圖2所示.采用3組不同agent進行的仿真實驗得到的平均節(jié)點飽和度見圖3.觀察可以發(fā)現(xiàn)，多數(shù)正方形、三角形圖標表示的飽和度值較菱形圖標表示的值都要小，特別是圖3中的的節(jié)點14, 22和27，這3個節(jié)點的飽和度值在Autonomous agent的作用下降低得尤為明顯，進一步觀察可以發(fā)現(xiàn)Autonomous agent權(quán)值的減小使得飽和度值更為減低，這三個節(jié)點的飽和度值最終分別從0.4 ～0.5左右下降至0.1左右.

2.2 實驗2 鏈路密度對網(wǎng)絡擁塞均衡的影響

第二組實驗中，我們設定與實驗1相同的交通路口節(jié)點位置和個數(shù)，通過對比不同網(wǎng)絡鏈路密度(鏈路數(shù)目)下的擁塞分布及優(yōu)化情況，分析鏈路密度對擁塞均衡的影響.首先，針對單個節(jié)點擁塞狀況的分析，我們通過圖4中給出的鏈路密度由密到疏(其鏈路數(shù)目分別為132，84，61，47)的4種網(wǎng)絡結(jié)構(gòu)進行對比仿真，黑色圓圈標記了4個網(wǎng)絡中出現(xiàn)了嚴重擁塞的節(jié)點，4個網(wǎng)絡結(jié)構(gòu)節(jié)點的平均飽和度分布見圖5，虛線框?qū)獔D4中黑色圓圈標記的節(jié)點在不同實驗設定下的飽和度值.其中圖4(a)網(wǎng)絡中黑色標記a, b對應圖5(a)中虛線框標記的節(jié)點20，27，其飽和度值分別從0.2，0.3降低到0.1，0.15左右，圖4(b)中c，d對應圖5(b)中虛線框標記的節(jié)點17，21，飽和度值從0.4，0.6降低到0.15左右．圖4(c)中黑色圓圈標示的節(jié)點對應圖5(c)中虛線框標記的節(jié)點5，10，14，17，27，其飽和度值經(jīng)過均衡作用都降低到了0.1左右．圖4(d)中黑色圓圈所標示的節(jié)點分別對應圖5(d)中虛線框標記的節(jié)點5，21，32，34，其飽和度也都降低到0.15左右.上述節(jié)點中正方形、三角形圖標表示的飽和度值均比菱形圖標表示的值要低，說明這些節(jié)點在未經(jīng)優(yōu)化前出現(xiàn)了嚴重的擁塞，但經(jīng)過Autonomous agent的均衡作用后，這些節(jié)點的擁塞狀況得到了顯著改善.

圖2 仿真實驗采用的網(wǎng)絡結(jié)構(gòu)

圖3 仿真實驗1的節(jié)點飽和度分布

上述實驗中，網(wǎng)絡中某些節(jié)點的飽和度在擁塞均衡過程中出現(xiàn)小幅上升.針對這一現(xiàn)象，定義3個不同鏈路密度的網(wǎng)絡，執(zhí)行相應仿真實驗來嘗試挖掘這些節(jié)點的共同特征.

仿真實驗結(jié)果如圖6為3個具有不同鏈路密度(鏈路數(shù)目分別為74, 84, 132)的網(wǎng)絡結(jié)構(gòu)及其對應的節(jié)點飽和度分布.左圖中黑色圓圈標記的是節(jié)點飽和度出現(xiàn)上升的異常節(jié)點，右側(cè)虛線框?qū)@些異常節(jié)點的飽和度分布.其中，圖6(a)中左側(cè)黑色圓圈標記的節(jié)點對應右側(cè)虛線框標示的節(jié)點.觀察發(fā)現(xiàn)，虛線框表示的節(jié)點大都位于左側(cè)網(wǎng)絡拓撲結(jié)構(gòu)的邊緣，經(jīng)過Autonomous agent的優(yōu)化策略后得到的節(jié)點飽和度值(三角形和正方形圖標)比未經(jīng)優(yōu)化(菱形圖標)之前的值反而要高，如圖6(a)中節(jié)點虛線框2選中的節(jié)點38，其飽和度從0.05小幅度增長到0.1.

圖4 4個不同鏈路密度(鏈路數(shù)目：132,84,61,47)網(wǎng)絡的擁塞分布結(jié)果

圖5 4個不同鏈路密度(鏈路數(shù)目：132,84,61,47)網(wǎng)絡的節(jié)點飽和度分布

(a)

(b)

(c)

進一步研究鏈路密度對整個網(wǎng)絡擁塞分布的影響，通過3個不同鏈路密度的網(wǎng)絡來進行分析.圖7中(a)，(b)和(c)分別對應著鏈路數(shù)目為61，74，132的3個網(wǎng)絡結(jié)構(gòu)及其對應的節(jié)點飽和度分布.觀察實驗結(jié)果可知，圖7(a)中菱形圖標表示的最大飽和度值比(b)，(c)中大多數(shù)菱形圖標表示的飽和度值要高，表明鏈路數(shù)目越小，網(wǎng)絡中發(fā)生擁塞節(jié)點的飽和度越大(擁塞越嚴重).表7給出了3個網(wǎng)絡在整個仿真過程中通過式(3)計算得到的網(wǎng)絡擁塞指標值.觀察其結(jié)果表明，隨著Autonomous agent的加入及權(quán)值的減小，網(wǎng)絡7(a)中平均節(jié)點飽和度之和從3.509 4降低到了2.749 0，說明整個仿真過程中網(wǎng)絡擁塞得到了改善.而網(wǎng)絡7(b)和7(c)的鏈路密度雖然分別增加到74和132，但平均節(jié)點飽和度值并沒有得到進一步減小，說明整個網(wǎng)絡的平均節(jié)點飽和度之和并沒有得到進一步優(yōu)化.

表7 網(wǎng)絡擁塞指標(nwval)分布

(a)

(b)

(c)

2.3 實驗3 鏈路分布形態(tài)對網(wǎng)絡擁塞的影響

在實驗3分析鏈路分布形態(tài)對網(wǎng)絡擁塞的影響.圖8～9給出了兩個具有不同鏈路分布的網(wǎng)絡及其節(jié)點飽和度分布的結(jié)果.圖8中網(wǎng)絡的鏈路是在不同的節(jié)點間隨機連邊形成；圖9中網(wǎng)絡鏈路分布呈現(xiàn)近似的路網(wǎng)拓撲結(jié)構(gòu)，沒有出現(xiàn)大量鏈路的交叉且同時滿足具有較小的特征路徑長度和較大的聚類系數(shù)特性.觀察圖8中的節(jié)點飽和度分布，我們發(fā)現(xiàn)大部分節(jié)點的飽和度沒有進一步改善.特別的，黑色矩形框表示的節(jié)點16，21，38經(jīng)過Autonomous agent的作用后節(jié)點飽和度(三角形和正方形圖標)比未經(jīng)優(yōu)化(菱形圖標)之前的值要高.在圖9右側(cè)的網(wǎng)絡平均節(jié)點飽和度分布中，發(fā)現(xiàn)大部分節(jié)點的飽和度值都維持在0.05這個較低的值左右，說明該網(wǎng)絡大多數(shù)節(jié)點擁塞情況并不嚴重.同時，觀察虛線框標示的出現(xiàn)嚴重擁塞的節(jié)點14，發(fā)現(xiàn)其節(jié)點飽和度值從菱形圖標表示的0.7降低至三角形圖標標示的0.15左右，說明擁塞嚴重的路口節(jié)點經(jīng)優(yōu)化后得到了較好的改善.

3 實驗結(jié)果分析

本文基于多目標的agent移動模型的三組實驗分別驗證了模型對路網(wǎng)擁塞均衡的有效性，從不同的鏈路密度和鏈路分布形態(tài)分析了模型對網(wǎng)絡擁塞的均衡程度，同時對不同網(wǎng)絡鏈路下?lián)砣植嫉挠楷F(xiàn)特征進行了分析和比較.

實驗1的結(jié)果表明，基于最短路徑和擁塞避免兩個目標優(yōu)化的agent移動模型較最短路徑的單一目標的agent移動模型具有一定程度的網(wǎng)絡擁塞均衡效果.

實驗2的結(jié)果表明，首先，網(wǎng)絡結(jié)構(gòu)中易發(fā)生擁塞的節(jié)點的地理坐標及特征和鏈路的稠密程度(鏈路數(shù)目)關(guān)連不大，如在圖4(a)，(b)和(c)網(wǎng)絡中的節(jié)點14，17，27，這些節(jié)點共同表現(xiàn)為處于整個網(wǎng)絡的中心區(qū)域；同時，在圖4(c)，(d)網(wǎng)絡中的節(jié)點5，32，這些節(jié)點則共同表現(xiàn)為處于網(wǎng)絡的割點或者是樞紐關(guān)鍵位置，該特性決定了易發(fā)生擁塞的路口節(jié)點的地理位置特性.其次，由于agent總是選擇網(wǎng)絡中通暢的區(qū)域行進以規(guī)避擁塞，所以agent趨向于繞開網(wǎng)絡中心的擁塞區(qū)域，選擇網(wǎng)絡邊緣區(qū)域通行，從而導致了邊緣區(qū)域agent的小幅度聚集涌現(xiàn)，使邊緣路口節(jié)點出現(xiàn)節(jié)點飽和度的小幅度上升，這是網(wǎng)絡擁塞均衡的必經(jīng)過程．例如在圖6(b)中的節(jié)點2和32，圖6(c)中的節(jié)點3，35，36，都是位于整個網(wǎng)絡的邊緣，隨著中心區(qū)域出現(xiàn)擁塞的節(jié)點擁塞狀況的改善，這些節(jié)點的飽和度出現(xiàn)小幅度上升.最后，整個網(wǎng)絡的擁塞均衡仿真實驗表明：網(wǎng)絡鏈路越稀疏，agent移動模型改善擁塞的效果就越好；但是，當網(wǎng)絡的鏈路密度過于密集，避免擁塞的特征行為使得Autonomous agent在網(wǎng)絡中滯留的時間延長，導致網(wǎng)絡擁塞得不到進一步的優(yōu)化，例如，表7(c)中的平均節(jié)點飽和度值沒有得到優(yōu)化.

實驗3比較了隨機網(wǎng)絡和近似路網(wǎng)結(jié)構(gòu)下的不同擁塞優(yōu)化結(jié)果.兩個網(wǎng)絡的節(jié)點飽和度分布結(jié)果表明：面對不規(guī)則的隨機網(wǎng)絡(圖8)，模型不能很好地改善網(wǎng)絡中嚴重擁塞的節(jié)點，同時，整個網(wǎng)絡擁塞的均衡效果也不佳；而針對近似路網(wǎng)結(jié)構(gòu)(圖9)，該模型能夠有效改善節(jié)點的擁塞，均衡網(wǎng)絡的擁塞.和傳統(tǒng)的最短路徑算法相比較，自主策略移動模型(最短路徑和擁塞避免)，對于網(wǎng)絡的擁塞均衡具有較好的效果.

圖8 不規(guī)則網(wǎng)絡結(jié)構(gòu)及其平均節(jié)點飽和度

圖9 近似路網(wǎng)拓撲結(jié)構(gòu)網(wǎng)絡及其平均節(jié)點飽和度

4 結(jié) 語

本文提出一種基于多目標路網(wǎng)擁塞均衡算法的agent移動模型，仿真實驗驗證了模型對擁塞均衡的有效性，并在不同網(wǎng)絡鏈路密度和鏈路分布形態(tài)下對網(wǎng)絡擁塞分布和優(yōu)化結(jié)果進行分析比較，是擁塞控制在實際交通路網(wǎng)中應用的新嘗試，在移動策略和路網(wǎng)結(jié)構(gòu)層面解決擁塞問題. 模型同時考慮最短路徑和擁塞避免兩個優(yōu)化目標，相比傳統(tǒng)的單一目標agent交通應用模型具有更好的宏觀視野；網(wǎng)絡中agent基于多目標優(yōu)化的自主移動行為使得整個網(wǎng)絡的擁塞也能得到很好的改善.借助GPS設備的幫助，該模型對于車輛導航和agent技術(shù)在智能交通領(lǐng)域的運用都具有理論價值和實際參考意義.

在后續(xù)的研究工作中，我們將結(jié)合實際交通路網(wǎng)結(jié)構(gòu)和交通網(wǎng)絡車流量數(shù)據(jù)對模型進行實證分析和驗證，并在此基礎上對模型進行擴充和完善.

[1] DESAI P, LOKE S W, DESAI A,etal. Multi-agent based vehicular congestion management [C]//Intelligent Vehicles Symposium (IV). Germany: 2011 IEEE. IEEE, 2011: 1031-1036.

[2] LIAO Gan-li, SHANG Peng-jian. Scaling and complexity-entropy analysis in discriminating traffic dynamics [J]. Fractals, 2012, 20(3/4): 233-243.

[3] HELBING D. Traffic and related self-driven many-particle systems [J]. Reviews of Modern Physics, 2001, 73(4): 1067-1141.

[4] SHEFFI Y. Urban transportation networks: equilibrium analysis with mathematical programming methods [M]. USA: PRENTICE-HALL INC, 1985:18-24.

[5] 文孟飛, 彭軍, 劉偉榮,等. 一種增量式多目標優(yōu)化的智能交通路徑誘導方法[J].湖南大學學報: 自然科學版, 2013, 40(5): 55-60.

WEN Meng-fei, PENG Jun, LIU Wei-rong,etal. An increment searching based multi-objective path guidance method in intelligent transportation [J]. Journal of Hunan University: Natural Science, 2013, 4(5): 55-60. (In Chinese)

[6] NARZT W, WILFLINGSEDER U, POMBERGER G,etal. Self-organizing congestion evasion strategies using ant-based pheromones [J]. Intelligent Transport Systems, IET, 2010, 4(1): 93-102.

[7] 梁滿朝, 李文勇, 李福祥. 基于蟻群算法和群決策理論的動態(tài)路徑優(yōu)化研究[J]. 西部交通科技, 2012(2): 58-63.

LIANG Man-chao, LI Wen-yong, LI Fu-xiang. Analyzes on dynamic route guidance based on group decision and ant colony algorithm [J]. Western China Communication Science & Technology, 2012(2): 58-63. (In Chinese)

[8] BUSCEMA D, IGNACCOLO M, INTURRI G,etal. The impact of real time information on transport network routing through intelligent agent-based simulation [C]//Science and Technology for Humanity (TIC-STH). Canada: 2009 IEEE Toronto International Conference. IEEE, 2009: 72-77.

[9] ARNAOUT G M, KHASAWNEH M T, ZHANG J,etal. An IntelliDrive application for reducing traffic congestions using agent-based approach [C]//Systems and Information Engineering Design Symposium (SIEDS). USA: 2010 IEEE. IEEE, 2010: 221-224.

[10]GRIMM V, BERGER U, DEANGELIS D L,etal. The ODD protocol: a review and first update [J]. Ecological Modelling, 2010, 221(23): 2760-2768.

A Multi-objective Routing Decision Model in Vehicle Transport Network Congestion Control

JIANG Bin1,2?,XU Xiao1,YANG Chao1,2, LI Ren-fa1

(1. College of Information Science and Engineering, Hunan Univ, Changsha, Hunan 410082, China;2. Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology,Yokohama, Kanagawa 226-8502, Japan)

Vehicle transport network congestion control in the field of ITS is one of the main means to solve the problem of network congestion. By using a bottom-up agent modeling method, a multi-objective routing decision agent model was constructed to solve the problem. In the model, vehicles were simulated as mobile agents, which determined the routing decision dynamically by a two-objective optimization: the shortest travel distance and the minimum congestion degree of the road network. The multi-objective routing decision model could improve the congestion intersection, and on the other hand, could dig out the common features of congestion intersection to help the network congestion control. The simulation results show that the model can improve road network congestion. And the simulations to compare the effect of network structure with different link densities and link distribution on the road network congestion distribution further indicate that link density of the road network has no effect on the location of the emergent congestion intersections in the network, and the intersection location affects the degree of congestion. It also indicates that the link distribution of the network has a direct effect on the location of the emergent congestion intersections in the network and congestion optimization results.

multi-objective optimization; road-network congestion; mobile agent model

1674-2974(2015)04-0121-09

2014-03-03

湖南省自然科學基金資助項目(13JJ3049); 湖南省科技計劃資助項目(2012FJ4131); 國家863高技術(shù)資助項目(2012AA01A301-01)

蔣 斌(1971-)，男，湖南邵陽人，湖南大學副教授，博士

?通訊聯(lián)系人，E-mail: jiangbin@hnu.edu.cn

TP399

A