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

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

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

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

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

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

智能交通系統(tǒng)領(lǐng)域中的路網(wǎng)擁塞控制是解決路網(wǎng)擁塞問題的主要手段之一，針對該問題，利用自底向上的agent建模方式，構(gòu)建一種多目標(biāo)路徑?jīng)Q策agent移動模型．在該模型中，車輛agent兼顧最短路徑和擁塞避免兩個(gè)優(yōu)化目標(biāo)，通過車輛agent行駛距離最短(最短路徑)和途經(jīng)區(qū)域的擁塞程度最低(擁塞避免)兩個(gè)目標(biāo)優(yōu)化來動態(tài)進(jìn)行路徑?jīng)Q策．基于多目標(biāo)路徑?jīng)Q策移動模型一方面能夠?qū)崿F(xiàn)對交通擁堵路段的分流控制，另一方面能夠挖掘網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中易發(fā)生擁塞的路口的共同特征，為路網(wǎng)擁塞控制提供幫助．仿真實(shí)驗(yàn)結(jié)果表明，該模型能較好地改善路網(wǎng)結(jié)構(gòu)中的擁塞路段．針對不同鏈路密度及鏈路分布的網(wǎng)絡(luò)所進(jìn)行的仿真實(shí)驗(yàn)結(jié)果進(jìn)一步表明，路網(wǎng)結(jié)構(gòu)的鏈路密度對擁塞路段出現(xiàn)在網(wǎng)絡(luò)中的地理位置影響不同，而路口節(jié)點(diǎn)位置影響其擁塞程度；網(wǎng)絡(luò)結(jié)構(gòu)的鏈路分布形態(tài)對發(fā)生擁塞路段的地理位置和擁塞優(yōu)化結(jié)果具有直接影響．

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

智能交通系統(tǒng)(ITS，Intelligent Transportation Systems)在交通領(lǐng)域的各個(gè)方面，例如路徑規(guī)劃、車輛導(dǎo)航及擁塞控制等方面已得到了許多成功應(yīng)用．擁塞控制作為ITS中的一個(gè)關(guān)鍵應(yīng)用，一直是研究熱點(diǎn)[1].目前，交通擁塞的研究方法大致可以分為3類：1)基于統(tǒng)計(jì)物理學(xué)的方法，如Liao等人使用熵復(fù)雜因果關(guān)系平面法分析交通數(shù)據(jù)，實(shí)驗(yàn)結(jié)果表明：其方法在評價(jià)交通動態(tài)狀態(tài)分級時(shí)效果最好，交通數(shù)據(jù)被分為：擁塞，中級，通暢[2]．Helbing介紹了多種交通流以及自主性多粒子所描述的系統(tǒng)，回顧和比較了交通領(lǐng)域中關(guān)于實(shí)證數(shù)據(jù)、行人和車輛通行的主要方法以及微觀中觀宏觀三種模型[3]. 2)基于數(shù)學(xué)規(guī)劃的方法．1985年，Sheffi運(yùn)用數(shù)學(xué)動態(tài)規(guī)劃及其建模方法，系統(tǒng)地闡述了交通流量的擁塞問題,并且提出了多種用戶均衡狀態(tài)及交通流建模的解決方案[4]．文孟飛等人利用一種基于增量搜索的多目標(biāo)優(yōu)化方法實(shí)現(xiàn)了車輛的實(shí)時(shí)路徑誘導(dǎo)[5].3)基于ABMS(agent-Based Modeling and Simula-tion)的智能交通擁塞控制方法.例如，Narzt等人運(yùn)用昆蟲群集產(chǎn)生的電子信息素，通過對其它車輛信息素的搜集、區(qū)分及避開擁塞，采用非集中控制的方式在仿真交通系統(tǒng)中分析汽車多種規(guī)避擁塞的不同策略[6]． 梁滿朝、李文勇等人針對城市交通信號控制的動態(tài)路徑優(yōu)化問題，綜合考慮了路口距離和道路的飽和程度，通過基于蟻群算法和群決策理論的動態(tài)路徑優(yōu)化算法模型，并證明了其有效性[7]． Buscema等人則考慮駕駛員行為偏好對路徑選擇的影響，指出駕駛員對于路徑的選擇不僅僅依賴于交通引導(dǎo)系統(tǒng)同時(shí)也依賴于駕駛員的主觀感覺[8].此外，文獻(xiàn)[9]提出了一種基于agent的智能駕駛模型，通過結(jié)合網(wǎng)絡(luò)、車輛信息共享更新的基礎(chǔ)設(shè)備和自適應(yīng)巡航聯(lián)合控制的方法，證明了該agent智能駕駛模型的實(shí)用性以及如何使用該技術(shù)減少擁塞.

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

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

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

1.1 目的

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

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

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

表1 實(shí)體定義及其描述

表2給出了模型中的狀態(tài)變量：1)路口節(jié)點(diǎn)狀態(tài)，包括節(jié)點(diǎn)飽和度和當(dāng)前等待的車輛agent隊(duì)列，節(jié)點(diǎn)飽和度指交通路口的最大通行能力，當(dāng)車輛agent數(shù)目達(dá)到上限時(shí)將飽和度置1(具體定義及計(jì)算見2.4)；2)網(wǎng)絡(luò)鏈路狀態(tài)，表示整個(gè)路網(wǎng)不同路口節(jié)點(diǎn)間的連接狀況(即網(wǎng)絡(luò)中的邊)；3)車輛agent的狀態(tài)，包括出發(fā)地、目的地、當(dāng)前路徑及當(dāng)前狀態(tài)(等待或是移動至下一路口).對于每個(gè)路口節(jié)點(diǎn)r，我們定義狀態(tài)變量Ux來描述其在時(shí)刻t的擁塞狀況為：

Ux=preA(r,t)desiG(r,t),

(1)

其中，preA(r,t)表示節(jié)點(diǎn)r在時(shí)刻t的前置影響，desiG(r,t)表示節(jié)點(diǎn)r在時(shí)刻t的節(jié)點(diǎn)飽和度，具體計(jì)算見1.4.本文中，為了簡化計(jì)算，我們將preA(r,t)的值設(shè)置為1.

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

1.3 過程與調(diào)度

1.4 設(shè)計(jì)理念

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

每一個(gè)仿真周期

開始

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

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

end for

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

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

end for

for 仿真時(shí)間步 = 0 to 仿真終止時(shí)間步

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

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

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

end if

end for

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

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

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

計(jì)算agent 的下一跳節(jié)點(diǎn)并移動；

if (agent到達(dá)最終目的地)

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

end if

end if

end for

end for

End

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

Fig.1 The pseudo code description of agent mobile model

Sheffi理論大多是建立在宏觀車流數(shù)學(xué)模型之上，通過數(shù)學(xué)規(guī)劃等方法為達(dá)到某種平衡而進(jìn)行計(jì)算.模型結(jié)合其理論，將交通復(fù)雜系統(tǒng)通過多agent系統(tǒng)進(jìn)行模擬仿真，將個(gè)體移動策略和全局擁塞分布動態(tài)聯(lián)系起來，是交通領(lǐng)域仿真模擬的新嘗試.

涌現(xiàn). 隨著車輛agent在路網(wǎng)中的自主移動，將形成路網(wǎng)中各路口節(jié)點(diǎn)不同的擁塞分布，并涌現(xiàn)出某些擁塞特別嚴(yán)重的路口節(jié)點(diǎn).研究agent移動策略與擁塞現(xiàn)象涌現(xiàn)的內(nèi)在聯(lián)系，對實(shí)現(xiàn)擁塞均衡具有很大的意義.

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

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

(2)

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

(3)

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

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

1.5 初始化

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

1.6 子模型

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

λg(x,t)+Gauss．

(4)

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

2 實(shí)驗(yàn)設(shè)定及結(jié)果

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

表3 3組仿真實(shí)驗(yàn)描述

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

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

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

表5 實(shí)驗(yàn)參數(shù)設(shè)定

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

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

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

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

2.2 實(shí)驗(yàn)2 鏈路密度對網(wǎng)絡(luò)擁塞均衡的影響

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

圖2 仿真實(shí)驗(yàn)采用的網(wǎng)絡(luò)結(jié)構(gòu)

圖3 仿真實(shí)驗(yàn)1的節(jié)點(diǎn)飽和度分布

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

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

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

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

(a)

(b)

(c)

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

表7 網(wǎng)絡(luò)擁塞指標(biāo)(nwval)分布

(a)

(b)

(c)

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

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

3 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

圖9 近似路網(wǎng)拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)及其平均節(jié)點(diǎn)飽和度

4 結(jié) 語

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

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

[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] 文孟飛, 彭軍, 劉偉榮,等. 一種增量式多目標(biāo)優(yōu)化的智能交通路徑誘導(dǎo)方法[J].湖南大學(xué)學(xué)報(bào): 自然科學(xué)版, 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

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

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

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

TP399

A