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

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

關(guān)鍵詞：多目標(biāo)優(yōu)化；路網(wǎng)擁塞；agent移動(dòng)模型

中圖分類(lèi)號(hào)：TP399 文獻(xiàn)標(biāo)識(shí)碼：A

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

湖南大學(xué)學(xué)報(bào)（自然科學(xué)版）2015年第4期蔣 斌等：路網(wǎng)擁塞控制中的多目標(biāo)路徑?jīng)Q策模型研究

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

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

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

1.1 目的

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

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

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

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

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

Tab.2 Status variables definition and description

1.3 過(guò)程與調(diào)度

仿真過(guò)程中，每個(gè)agent抵到一個(gè)路口節(jié)點(diǎn)i，會(huì)根據(jù)該路口節(jié)點(diǎn)i的鄰接節(jié)點(diǎn)集Si={v1， v2，…，vj，…，vn}進(jìn)行計(jì)算（vj表示與節(jié)點(diǎn)i相鄰的節(jié)點(diǎn)j），通過(guò)多目標(biāo)優(yōu)化算法計(jì)算集合中所有節(jié)點(diǎn)的效用值（效用函數(shù)定義及計(jì)算見(jiàn)2.6），處于移動(dòng)狀態(tài)的agent會(huì)選擇集合Si中效用值最小的節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn).若agent移動(dòng)后到達(dá)最終目標(biāo)路口節(jié)點(diǎn)，則將該agent從路網(wǎng)中移除.每一個(gè)仿真周期將執(zhí)行兩類(lèi)實(shí)體和整個(gè)網(wǎng)絡(luò)狀態(tài)的更新.圖1是對(duì)該仿真過(guò)程和調(diào)度的偽代碼描述.

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

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

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

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

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

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

desiG（r，t）=1v≥Max；

v+1Maxv

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

nwval=∑Endt=0∑Nr=1desiG（r，t）.（3）

隨機(jī)特性. 模型中車(chē)輛agent的出發(fā)地、目的地以及加入到網(wǎng)絡(luò)中的時(shí)間都是隨機(jī)設(shè)定的.在每一個(gè)仿真時(shí)間步，車(chē)輛agent基于效用函數(shù)的計(jì)算決定下一目標(biāo)路口節(jié)點(diǎn)，該效用函數(shù)的定義不僅考慮了主要因素的影響，還通過(guò)高斯隨機(jī)函數(shù)模擬了車(chē)輛移動(dòng)過(guò)程中隨機(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è)具有不同移動(dòng)策略、出發(fā)點(diǎn)和目的地的車(chē)輛agent；不同agent類(lèi)別之間的比例，效用函數(shù)中的權(quán)值設(shè)定，根據(jù)實(shí)驗(yàn)?zāi)康木唧w設(shè)定.

1.6 子模型

我們所定義的agent移動(dòng)模型理論來(lái)自于朗之萬(wàn)方程，假定agent移動(dòng)是由主導(dǎo)因子和隨機(jī)因子兩部分共同的作用結(jié)果.據(jù)此我們定義agent的移動(dòng)效用方程，見(jiàn)式（4），其中Λ（Ux，t，λ）代表了相鄰節(jié)點(diǎn)x在時(shí)間t的效用值.車(chē)輛agent i將會(huì)選擇其相鄰節(jié)點(diǎn)集合Si={v1，v2，…，vn}中效用值最小的一個(gè)作為目標(biāo)節(jié)點(diǎn).式（4）中的f（Ux，t）表示的是周邊路口節(jié)點(diǎn)x在時(shí)間t對(duì)車(chē)輛agent移動(dòng)的外部作用，其值動(dòng)態(tài)反應(yīng)了該鄰接節(jié)點(diǎn)x的飽和程度；g（x，t）代表對(duì)agent的路徑約束， 其值直接反應(yīng)出agent距離最終目標(biāo)節(jié)點(diǎn)的路徑長(zhǎng)度，g（x，t）將會(huì)約束agent朝著目的地行進(jìn).參數(shù)λ是這兩個(gè)目標(biāo)之間（最短路徑和擁塞避免）的權(quán)值.此外， 為了保持移動(dòng)過(guò)程中具有一定的隨機(jī)性， 我們?cè)谛в煤瘮?shù)中加入高斯隨機(jī)擾動(dòng)Gauss，

Λ（Ux，t，λ）=（1-λ）f（Ux，t）+

λg（x，t）+Gauss. （4）

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

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

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

對(duì)擁塞均衡的影響

網(wǎng)絡(luò)結(jié)構(gòu)及節(jié)點(diǎn)飽和度分析

分析網(wǎng)絡(luò)鏈路分布形態(tài)對(duì)擁塞的影響.仿真實(shí)驗(yàn)中定義了兩類(lèi)agent：第一類(lèi)Floyd agent將沿著最短路徑向目的地移動(dòng)；第二類(lèi)Autonomous agent將同時(shí)考慮最短路徑和擁塞避免兩個(gè)優(yōu)化目標(biāo)，根據(jù)效用函數(shù)公式（4）向目的地自主移動(dòng).通過(guò)仿真實(shí)驗(yàn)采用的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)以及兩類(lèi)agent在不同比例和權(quán)值下的網(wǎng)絡(luò)節(jié)點(diǎn)飽和度分布來(lái)分析仿真結(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)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)2中用黑色圓圈進(jìn)行標(biāo)識(shí)的節(jié)點(diǎn)表示在仿真過(guò)程中出現(xiàn)明顯擁塞或異常的節(jié)點(diǎn).3組仿真實(shí)驗(yàn)都給出對(duì)應(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)兩類(lèi)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è)車(chē)輛agent將在前50個(gè)時(shí)間步隨機(jī)加入到預(yù)定義的網(wǎng)絡(luò)結(jié)構(gòu)中，為保證所有agent都能夠達(dá)到目的地，設(shè)定仿真時(shí)間步長(zhǎng)