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

韓東芮

(西南交通大學交通運輸與物流學院)

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

韓東芮

(西南交通大學交通運輸與物流學院)

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

城市交通;移動Agent;交通流分配;Wardrop均衡準則;混合策略的Nash均衡;改進蟻群算法

1 移動Agent與博弈方法

1.1 移動Agent技術

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

圖1 Agent結構模型圖

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

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

(1)個體Agent

個體Agent是基于出行者的愿望、目標、行為三大屬性而建立的智能Agent體。因為出行者是具有智能判斷的個體，所以個體Agent采取的是動態(tài)路由設計，即根據(jù)路網(wǎng)狀態(tài)自由更改自己的組合策略。

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

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

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

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

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

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

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

1.3 Agent博弈均衡

對于每個OD間個體Agent而言，由于相同OD間個體Agent是同質的，當路網(wǎng)達到用戶均衡時，Agent會選擇總走行時間最短的決策集合，即Wardrop第一均衡準則。

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

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

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

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

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

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

2 基于移動Agent的博弈配流模型

通過對Wardrop第一均衡準則下的混合策略Nash均衡博弈分析，基于移動Agent的建模可以表示為如下一維極值問題，對每個OD對j的智能體Agent來說，都有如下極值問題

3 改進蟻群求解算法

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

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

結合本文的研究情況，將對蟻群算法進行如下兩個方面改進:

第一，螞蟻能通過不同OD間的濃度進行識別;

第二，濃度的在不同范圍內能進行正負反饋;

第三，不同OD對的螞蟻能識別相應的路徑方向;

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

3.2 蟻群算法的改進

(1)能見度與轉移規(guī)則改進

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

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

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

此時蟻群Aj的螞蟻a由路段r轉移到路段s的轉移概率可表示為

(2)局部規(guī)則改進

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

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

基于以上改進方法，算法步驟如下

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

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

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

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

Step6:輸出最后的方案。

4 算法仿真

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

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

表1 節(jié)點走行時間表

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

表2 線路設計表

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

表3 OD表

續(xù)表3

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

表4 地鐵1號線各路段配流仿真表

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

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

5 結論

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

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

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

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

U491

C

1008－3383(2015)10－0161－03

2015－03－09

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