韓東芮

(西南交通大學(xué)交通運(yùn)輸與物流學(xué)院)

基于移動(dòng)Agent的公交與城軌路網(wǎng)博弈配流研究

韓東芮

(西南交通大學(xué)交通運(yùn)輸與物流學(xué)院)

為更深入的研究路網(wǎng)交通流的分配問題，采用移動(dòng)Agent技術(shù)進(jìn)行系統(tǒng)的構(gòu)建，并采用博弈論方法、均衡方法進(jìn)行建模的分析與論證，以此建立基于移動(dòng)Agent的博弈配流模型。假設(shè)路網(wǎng)上有多個(gè)OD對(duì)，通過Wardrop第一均衡準(zhǔn)則證明每個(gè)OD間的個(gè)體Agent是同質(zhì)的，并建立混合策略的Nash均衡，得出路網(wǎng)交通流的均衡分配辦法。在求解過程中，采用改進(jìn)的蟻群算法對(duì)個(gè)體Agent的均衡過程進(jìn)行模擬。算例結(jié)果表明:改進(jìn)的蟻群結(jié)果非常合理的仿真了移動(dòng)Agent博弈均衡過程。

城市交通;移動(dòng)Agent;交通流分配;Wardrop均衡準(zhǔn)則;混合策略的Nash均衡;改進(jìn)蟻群算法

1 移動(dòng)Agent與博弈方法

1.1 移動(dòng)Agent技術(shù)

移動(dòng)Agent具有可移動(dòng)的特性，具有自我控制移動(dòng)能力、跨平臺(tái)兼容運(yùn)行的能力，并且可以模擬人類智能行為，提供一定人類智能交互和服務(wù)的程序。移動(dòng)Agent可以根據(jù)系統(tǒng)的需要生成子Agent，子Agent具有同父Agent相同的性質(zhì)并在此基礎(chǔ)上進(jìn)行一定的延生和改進(jìn)。移動(dòng)Agent在分布式人工智能領(lǐng)域及分布對(duì)象領(lǐng)域運(yùn)用廣泛，它主要由六大模塊組成，分別是Agent模塊、生命周期模塊、計(jì)算模塊、安全模塊、通訊模塊和導(dǎo)航模塊組成。這些模塊共同組成了兩個(gè)子系統(tǒng):思考子系統(tǒng)和反應(yīng)子系統(tǒng)。思考子系統(tǒng)中含有用符號(hào)和標(biāo)號(hào)構(gòu)成的目標(biāo)模型，并在決策庫中生成的人工智能的規(guī)劃和決策。另一個(gè)是反應(yīng)子系統(tǒng)，對(duì)系統(tǒng)中的重要事件立即做出反應(yīng)。本文構(gòu)建移動(dòng)Agent結(jié)構(gòu)模型圖如圖1所示，通過下圖機(jī)制，將出行者轉(zhuǎn)化為移動(dòng)智能Agent體。

圖1 Agent結(jié)構(gòu)模型圖

1.2 移動(dòng)Agent交互系統(tǒng)的建立

通過基于Agent技術(shù)的交通分配分析，本文擬將公交與軌道交通之間的交通分配看作是路網(wǎng)中個(gè)OD間出行者之間的非合作博弈，但他們可以通過與其他Agent信息共享和路網(wǎng)agent之間的信息交互得出自己想要的信息，經(jīng)過目標(biāo)模型的轉(zhuǎn)化后，最后通過決策系統(tǒng)得出將要采取的行為。這種基于Agent的交互和不斷學(xué)習(xí)的過程實(shí)際就是Agent之間不斷博弈以達(dá)到均衡的過程。

(1)個(gè)體Agent

個(gè)體Agent是基于出行者的愿望、目標(biāo)、行為三大屬性而建立的智能Agent體。因?yàn)槌鲂姓呤蔷哂兄悄芘袛嗟膫€(gè)體，所以個(gè)體Agent采取的是動(dòng)態(tài)路由設(shè)計(jì)，即根據(jù)路網(wǎng)狀態(tài)自由更改自己的組合策略。

個(gè)體Agent通過反應(yīng)子系統(tǒng)與路網(wǎng)狀態(tài)Agent進(jìn)行人機(jī)交互，接受路網(wǎng)狀態(tài)Agent傳輸?shù)穆肪W(wǎng)狀態(tài)(DLrs，GLrs)

式中:DLrs和GLrs表示路段rs上軌道交通方式和公交方式的客流量負(fù)荷，用分?jǐn)?shù)表示;和分別表示第j個(gè)OD的A-gent進(jìn)行第k種乘車組合決策下采用軌道交通方式和公交方式是否經(jīng)過路段rs(0－1變量);FDrs和FGrs分別表示公交路段rs和軌道交通路段rs上能容納的最大客流量。

作為個(gè)體Agent而言，它們都有著共同的愿望，即以最少的支付到達(dá)目的地，且受路網(wǎng)狀態(tài)、選擇的路徑和交通方式的影響，但這需要通過目標(biāo)模型將愿望轉(zhuǎn)化為決策系統(tǒng)可識(shí)別的目標(biāo)。本文通過將純乘車時(shí)間(零負(fù)荷狀態(tài)下的乘車時(shí)間)與路網(wǎng)負(fù)荷對(duì)出行支出的影響進(jìn)行整合，得出個(gè)體Agent的目標(biāo)模型如下所示

式中:Zjk表示第j個(gè)OD的Agent進(jìn)行第k種乘車組合決策下的綜合支付函數(shù);tk表示采用第K中乘車組合決策下的純乘車時(shí)間;λk表示第k種乘車組合決策下的路段數(shù);ξ表示修正系數(shù)。

決策系統(tǒng)是基于目標(biāo)模型所得出的可識(shí)別目標(biāo)進(jìn)行路徑和交通方式的搜索，對(duì)于每個(gè)Agent而言，都有自己的決策庫;這些決策都是基于路網(wǎng)可達(dá)性條件下出行者可能采取的不同策略集合下的。個(gè)體Agent通過思考子系統(tǒng)中的目標(biāo)模型的轉(zhuǎn)化和決策系統(tǒng)的決策機(jī)制的搜索得到一種交通路線與方式聯(lián)合函數(shù);再將決策反饋給路網(wǎng)狀態(tài)Agent，并更新此時(shí)路網(wǎng)的狀態(tài)。該決策即為出行者采取的行為。

(2)路網(wǎng)狀態(tài)Agent

對(duì)路網(wǎng)狀態(tài)Agent來說，它其實(shí)就是出行個(gè)體Agent與路網(wǎng)交通的一個(gè)交互與共享的終端，當(dāng)個(gè)體Agent出行并選用其中一種交通路線與方式組合策略的時(shí)候，個(gè)體Agent就會(huì)與路網(wǎng)狀態(tài)Agent發(fā)生交互，路網(wǎng)狀態(tài)Agent接受到每個(gè)出行Agent的組合信息，并及時(shí)更新歷史路網(wǎng)狀態(tài)。

1.3 Agent博弈均衡

對(duì)于每個(gè)OD間個(gè)體Agent而言，由于相同OD間個(gè)體Agent是同質(zhì)的，當(dāng)路網(wǎng)達(dá)到用戶均衡時(shí)，Agent會(huì)選擇總走行時(shí)間最短的決策集合，即Wardrop第一均衡準(zhǔn)則。

由于不同個(gè)體Agent存在著博弈關(guān)系，本文使用博弈論的方法考慮交通均衡問題，不同OD間的Agent面臨著不同組合策略選擇的混合策略Nash均衡博弈。第j個(gè)OD的智能體Agent的混合策略為公交與軌道交通的組合決策與概率的線性組合

式中:pjk表示第j個(gè)OD的個(gè)體Agent做出決策k的概率。其中

綜合支付函數(shù)包含路徑、方式、路網(wǎng)狀態(tài)的因素，本文將混合策略的綜合支付函數(shù)表達(dá)如下

式中:DL、GL分別表示軌道交通和公交的路網(wǎng)狀態(tài)。

同理，其他OD間的組合決策與概率的線性組合

對(duì)于有j個(gè)OD的Agent系統(tǒng)而言，不同個(gè)體Agent在信息共享和與終端Agent交互條件下，獨(dú)立無合作追求最大利益情形下的博弈平衡，這樣就形成在Wardrop第一均衡準(zhǔn)則下的混合策略Nash均衡。

2 基于移動(dòng)Agent的博弈配流模型

通過對(duì)Wardrop第一均衡準(zhǔn)則下的混合策略Nash均衡博弈分析，基于移動(dòng)Agent的建?？梢员硎緸槿缦乱痪S極值問題，對(duì)每個(gè)OD對(duì)j的智能體Agent來說，都有如下極值問題

3 改進(jìn)蟻群求解算法

3.1 改進(jìn)蟻群算法依據(jù)

根據(jù)對(duì)移動(dòng)Agent路徑、方式走向設(shè)計(jì)的博弈配流模型建立與分析，一方面，通過個(gè)體Agent與路網(wǎng)Agent終端的交互，體現(xiàn)了OD對(duì)之間的相互抑制，是逆向反饋的過程;另一方面，相同OD對(duì)之間的信息共享，體現(xiàn)了個(gè)體Agent之間的相互促進(jìn)作用，是正向反饋的過程。這是人工智能的表現(xiàn)。蟻群算法也是一種智能算法，通過模擬螞蟻外出覓食時(shí)根據(jù)前面螞蟻所遺留下的信息素的強(qiáng)度來指導(dǎo)自己的運(yùn)動(dòng)，而通過的對(duì)信息素識(shí)別和正負(fù)反饋的改進(jìn)剛好可以實(shí)現(xiàn)上述兩個(gè)方面的智能。所以本文選擇了蟻群算法。

結(jié)合本文的研究情況，將對(duì)蟻群算法進(jìn)行如下兩個(gè)方面改進(jìn):

第一，螞蟻能通過不同OD間的濃度進(jìn)行識(shí)別;

第二，濃度的在不同范圍內(nèi)能進(jìn)行正負(fù)反饋;

第三，不同OD對(duì)的螞蟻能識(shí)別相應(yīng)的路徑方向;

第四，需對(duì)同一個(gè)OD間的個(gè)體Agent之間通過信息素來進(jìn)行正向反饋，而不同OD間的個(gè)體Agent之間則通過信息素相互抑制的問題進(jìn)行修正。

3.2 蟻群算法的改進(jìn)

(1)能見度與轉(zhuǎn)移規(guī)則改進(jìn)

將j個(gè)OD對(duì)集合假設(shè)為蟻群A1，A2，…Aj，由于個(gè)體A-gent傾向于采用路徑綜合支付函數(shù)較小的組合決策，所以對(duì)能見度ηrs規(guī)則進(jìn)行如下修正

G(t，1)，(t，2)，…(t，j);軌道交通決策方式路徑rs上信息素濃度為(t，1)(t，2)，…(t，j)。為了濃度的在不同范圍內(nèi)能進(jìn)行正負(fù)反饋，定義一個(gè)負(fù)指數(shù)函數(shù)

式中:τrs為路段rs上的最佳濃度;ε為負(fù)指數(shù)分布的陡峭系數(shù)，ε越小，曲線越陡峭。

此時(shí)蟻群Aj的螞蟻a由路段r轉(zhuǎn)移到路段s的轉(zhuǎn)移概率可表示為

(2)局部規(guī)則改進(jìn)

對(duì)局部規(guī)則的改進(jìn)可以有效地避免個(gè)體Agent大量收斂到某一路徑或方式，個(gè)體Agent在完成每一步搜索后，應(yīng)用下面的更新規(guī)則更新它所經(jīng)過路徑的信息素強(qiáng)度

式中:Q表示信息素強(qiáng)度;La表示第a個(gè)體Agent在本次循環(huán)中所走路徑組合長(zhǎng)度。

基于以上改進(jìn)方法，算法步驟如下

Step1:禁忌表tabua置空，初始化τrs和Δτrs(歸0)，將個(gè)體Agent A1，A2…，Aj分別置于1…j個(gè)頂點(diǎn)上;

Step3:根據(jù)tabua的記錄，不斷更新τrs與Δτrs;

Step4:對(duì)各路徑(r，s)分別設(shè)置Δτrs=0;

Step5:記錄到目前為止路徑組合，若不滿足終止條件，清空禁忌表，轉(zhuǎn)步驟(2);

Step6:輸出最后的方案。

4 算法仿真

本文假設(shè)一個(gè)路網(wǎng)圖進(jìn)行算例分析如圖1所示，其中紅色箭頭表示軌道交通線路(雙向);直線表示公交線路;其布局圖節(jié)點(diǎn)之間純走行時(shí)間數(shù)據(jù)如表1所示，其中G開頭表示公交線路時(shí)間，D開頭表示軌道交通線路時(shí)間(min)。

圖2 網(wǎng)絡(luò)布局圖

表1 節(jié)點(diǎn)走行時(shí)間表

公交線路與軌道交通開通路線設(shè)置如表2所示。

表2 線路設(shè)計(jì)表

我們初始化OD如表3所示，單位為min。

表3 OD表

續(xù)表3

本文為了仿真更真實(shí)，對(duì)換乘時(shí)間做如下規(guī)定:換乘時(shí)間隨著換乘次數(shù)進(jìn)行累加，時(shí)間為5 min，現(xiàn)在按照算法步驟進(jìn)行迭代，迭代出的配流部分結(jié)果如表4所示。

表4 地鐵1號(hào)線各路段配流仿真表

表5 1路公交車各路段配流仿真表

部分計(jì)算結(jié)果見表4、表5，由試驗(yàn)結(jié)果可以看出，相對(duì)于傳統(tǒng)的蟻群算法，改進(jìn)的算法在基于Agent人工智能方面的做了相當(dāng)大的提升，能非常好的模擬智能體也就是出行者的出行選擇的思維和博弈的過程;迭代次數(shù)也大幅度減少。相對(duì)于傳統(tǒng)的蟻群算法而言，改進(jìn)的智能蟻群算法具有更好的全局最優(yōu)解搜索能力和智能性，收斂性更好。通過對(duì)蟻群算法的改進(jìn)，本文很好的實(shí)現(xiàn)了移動(dòng)Agent系統(tǒng)的仿真與求解。

5 結(jié)論

用移動(dòng)Agent理論結(jié)合博弈論來模擬解決交通分配中的出行者意愿選擇是非常具有研究意義的;根據(jù)對(duì)War drop均衡和混合策略Nash均衡準(zhǔn)則研究用來表述出行選擇能夠體現(xiàn)出行行為的多重性和多元性。而蟻群算法的引入求解非常合理的解決了這個(gè)復(fù)雜的Agent智能博弈模型的求解方法問題，也為問題的完善開辟了一條新思路。

［1］ 艾毅，李宗平.基于蟻群算法的多維Stackelberg博弈配流研究［J］.城市軌道交通研究，2014，(1):95－98.

［2］ 何增鎮(zhèn).基于Mu1ti－Agent與博弈論的城市交通控制誘導(dǎo)系統(tǒng)及其關(guān)鍵技術(shù)研究［D］.博士學(xué)位論文.中南大學(xué)，2009.

［3］ 袁長(zhǎng)偉，蔚欣欣，陸化普，卞長(zhǎng)志.基于斯塔克爾伯格博弈的路網(wǎng)均衡交通分配方法［J］.中國公路學(xué)報(bào)，2009，(5):90－93.

U491

C

1008－3383(2015)10－0161－03

2015－03－09

韓東芮(1988－)，男，碩士研究生，研究方向:城市軌道交通。