基于蟻群算法的多維Stackelberg博弈配流研究

（西南交通大學(xué)交通運(yùn)輸與物流學(xué)院，610031，成都∥第一作者，碩士研究生）

基于蟻群算法的多維Stackelberg博弈配流研究

艾 毅 李宗平

（西南交通大學(xué)交通運(yùn)輸與物流學(xué)院，610031，成都∥第一作者，碩士研究生）

根據(jù)Stackelberg博弈對道路公交系統(tǒng)與城市軌道交通進(jìn)行交通流分配，并建立Nash均衡。假設(shè)路網(wǎng)上有多個OD（起止點）對，通過Wardrop均衡準(zhǔn)則證明每個OD間出行的用戶是同質(zhì)的。據(jù)此假設(shè)建立道路公交路徑與城市軌道交通路徑的j維混合策略Stackelberg-Nash均衡博弈模型。采用改進(jìn)的蟻群算法對出行用戶的均衡過程進(jìn)行模擬。結(jié)果表明，改進(jìn)的蟻群算法合理地仿真了Stackelberg博弈的均衡過程。

道路公交；城市軌道交通；交通流分配；Stackelberg博弈；改進(jìn)蟻群算法

First-author's address Transportation and Logistics Institute，Southwest Jiaotong University，610031，Chengdu，China

隨著城市軌道交通的出現(xiàn)，人們的出行方式由當(dāng)初單一的道路公交系統(tǒng)逐漸轉(zhuǎn)變?yōu)榈缆饭幌到y(tǒng)與城市軌道交通并存的方式。因此，交通流在這兩種出行策略中的協(xié)調(diào)分配問題是合理規(guī)劃路網(wǎng)的重要工作。在以往的研究結(jié)果中，交通流分配基本集中在單一層面上，對其在不同交通方式之間和在路網(wǎng)不同路徑中的辯證和博弈關(guān)系并沒有進(jìn)行探討。本文將探討不同出行用戶在選擇路徑和選擇出行方式上的博弈思路，即j維OD（起止點）對之間的博弈均衡。

1 博弈論方法

1.1 路網(wǎng)博弈分析

博弈論模型的主要思想是建立在一個假想的博弈游戲上，包括局中人、策略空間和得益等方面［1］。可以將道路公交與城市軌道交通之間的博弈看作是路網(wǎng)中j個OD間出行的用戶之間的非合作博弈，他們通過對交通資源的效益判斷得出自己的最優(yōu)線路，這樣就形成了j維出行用戶之間的博弈。他們的支付函數(shù)就是綜合支付函數(shù)。因此，可將出行用戶相互之間的關(guān)系轉(zhuǎn)化為j維混合策略Nash均衡博弈。利用Stackelberg-Nash均衡來建立出行用戶關(guān)于道路公交系統(tǒng)路徑和城市軌道交通路徑的j維博弈模型［2］。

1.2 Wardrop均衡與混合策略Nash均衡

通過博弈分析，構(gòu)建Wardrop均衡和混合策略Nash均衡的關(guān)系。根據(jù)文獻(xiàn)［3］提出的方法，在第j個OD間，由于相同OD間出行用戶是同質(zhì)的，因此，當(dāng)路網(wǎng)達(dá)到用戶均衡時，某OD間出行的用戶選擇總走行時間最短的策略集合。即Wardrop第一均衡準(zhǔn)則。其數(shù)學(xué)表達(dá)為：

式中：

Djk---第j個OD間出行的用戶采取第k種乘車策略所包含城市軌道交通路徑的集合；

Gjk---第j個OD間出行的用戶采取第k種乘車策略所包含道路公交路徑的集合；

Zjk（Djk，Gjk，tjk）---在混合策略下的綜合支付函數(shù)。

當(dāng)Zjk（Djk，Gjk，tjk）＞min Zjk（Djk，Gjk，tjk）時，說明該混合策略不是最優(yōu)，出行用戶不會選擇該策略下的路徑集合，即Djk+Gjk=0。同理，當(dāng)出行用戶選擇該混合策略時，說明該混合策略等價于最優(yōu)策略。

使用博弈論的方法考慮交通策略問題，第j個OD間出行的用戶面臨著不同路徑選擇的混合策略Nash均衡博弈。第j個OD間出行的用戶的混合策略Sjk為道路公交與城市軌道交通混合乘車策略與策略概率的線性組合。即：

式中：

pjk---第j個OD間出行的用戶選擇策略k的概率。

當(dāng)OD對j的綜合支付函數(shù)的變量包含狀態(tài)集合時，可以將混合策略的綜合支付函數(shù)表達(dá)為：

式中：

S-j---第j個OD以外各OD間的策略集合；

h---第h個OD間出行的用戶（h≠j）；

ah---第h個OD間的策略組合個數(shù)。

由于相同OD間出行用戶都是同質(zhì)的，根據(jù)Wardrop第一均衡準(zhǔn)則，對任意OD對來說，出行用戶都會選擇期望最大的混合策略［4］：

對于有j個OD間出行的用戶狀況，不同出行用戶獨(dú)立無合作追求最大利益（時間和擁擠負(fù)載的綜合收益最大）情形下的博弈平衡，這樣就形成在Wardrop第一均衡準(zhǔn)則下的混合策略Nash均衡［5］。

2 Stackelberg-Nash博弈配流模型

根據(jù)Wardrop第一均衡準(zhǔn)則下的混合策略Nash均衡準(zhǔn)則，可以將模型改寫為一維極值問題。對每個OD對j來說，都有如下極值問題：

式中：

Q---目標(biāo)函數(shù)；

min Q---配流最優(yōu)；

w---OD個數(shù)；

Fjk---第j個OD間采取第k種城市策略的路徑擁擠函數(shù)；

Zjk（Fjk，tjk）---第j個OD間采取第k種策略的綜合支付函數(shù)；

djk，rs---第j個OD間的第k種軌道交通策略是否經(jīng)過路段rs的0-1變量，o和i表示城市軌道交通路段的任意節(jié)點組合；

gjk，rs---第j個OD間的第k種道路公交策略是否經(jīng)過路段rs的0-1變量，u和v表示道路公交路段的任意節(jié)點組合；

aj---第j個OD間的策略組合個數(shù)；

求得的pjkDjk，rs和pjkGjk，rs即交通流分配方案。

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

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

根據(jù)出行用戶路線走向設(shè)計的配流博弈模型是多個OD之間的混合策略博弈。其體現(xiàn)了OD對之間的相互抑制，是逆向反饋的過程；相同OD之間的影響體現(xiàn)了人與人之間的相互吸引，是正向反饋的過程。這是人工智能的一般應(yīng)用，而對蟻群算法的改進(jìn)恰好可以實現(xiàn)上述兩個方面的智能。所以本文選擇了蟻群算法。這是一種模擬螞蟻外出覓食時根據(jù)前面螞蟻所留下的信息素的存在及其強(qiáng)度來指導(dǎo)自己的運(yùn)動的方法［6］。

由于本文研究的情況復(fù)雜，對算法進(jìn)行了兩個方面的改進(jìn)：

第一，對轉(zhuǎn)移規(guī)則中對能見度ηrs進(jìn)行修正，解決搜索的方向性問題。同一個OD的出行用戶之間通過信息素進(jìn)行正向反饋，而不同OD所屬的出行用戶之間則通過信息素相互抑制。

第二，考慮到路段擁擠和排隊消散等問題，需對局部更新規(guī)則進(jìn)行改進(jìn)。

3.1.1 轉(zhuǎn)移規(guī)則改進(jìn)

由于乘客傾向于乘坐路徑綜合支付函數(shù)較小的交通工具，所以對能見度ηrs進(jìn)行如下更新：

式中：ZD，rs（Frs，trs），ZG，rs（Frs，trs）分別表示路徑rs中乘坐城市軌道交通與乘坐道路公交的綜合支付函數(shù)。

將w個OD對假設(shè)為蟻群A1，A2，…Aw，t時刻城市軌道交通路徑rs上信息素濃度為τD，rs（t，1），τD，rs（t，2），…τD，rs（t，w），道路公交路徑rs上信息素濃度為τG，rs（t，1），τG，rs（t，2），…τG，rs（t，w）。則屬于蟻群Aj的螞蟻a由區(qū)域r行駛到區(qū)域s的轉(zhuǎn)移概率可表示為：

當(dāng)s∈Sallowedk時，

當(dāng)s?Sallowedk時，

當(dāng)s∈Sallowedk時，

當(dāng)s?Sallowedk時，

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

對局部規(guī)則的更新可有效避免螞蟻收斂到同一路徑。螞蟻在每一步搜索后，更新它所經(jīng)過路徑的信息素強(qiáng)度，更新規(guī)則為：

式中：

Δτrs---信息素增量；

Δτrs，a---螞蟻a遺留的信息素數(shù)量。

如果第a只螞蟻經(jīng)過路段（r，s），

否則

式中：

Q---信息素強(qiáng)度，它在一定程度上影響算法的收斂速度；

La---第a只螞蟻在本次循環(huán)中所走路徑的總長度。

基于以上改進(jìn)方法的算法如下：

步驟1：初始化τrs和Δτrs，禁忌表tua置空，將A1，A2，…Aw只螞蟻置于1～w個頂點上；

步驟2：螞蟻以概率prs，a嘗試選擇下一節(jié)點s，將s添入至tua中，直至禁忌表滿；

步驟3：根據(jù)tua的記錄，更新τrs與Δτrs；

步驟4：對各路徑（r，s）置Δτrs=0；

步驟5：記錄到目前為止最短的路徑，若不滿足終止條件，清空禁忌表，轉(zhuǎn)步驟2；

步驟6：輸出配流方案。

4 算法仿真

利用圖1的網(wǎng)絡(luò)布局圖進(jìn)行算法仿真。其中，實線表示道路公交連通線路；空心箭頭表示城市軌道交通連通線路。布局圖節(jié)點之間無擁擠走行時間數(shù)據(jù)見表1。表中G開頭表示道路公交線路時間，D開頭表示城市軌道交通線路時間，單位為min。

道路公交線路與城市軌道交通線路設(shè)計見表2。設(shè)計不同節(jié)點之間的OD，如表3所示。

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

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

表2 道路公交線路與城市軌道交通線路設(shè)計表

針對上述參數(shù)設(shè)計，對換乘進(jìn)行相關(guān)時間疊加，規(guī)定換乘一次的時間為2 min，并按算法步驟進(jìn)行迭代。迭代出的部分配流結(jié)果如表4、表5所示。從表中可以看出，出行用戶在蟻群算法中的配流結(jié)果基本符合蟻群算法的相關(guān)智能要求。通過對求解過程和結(jié)果的分析，改進(jìn)蟻群算法基本實現(xiàn)了博弈的均衡過程，是合理的。

表3 不同OD間走行時間 min

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

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

5 結(jié)語

本文根據(jù)Stackelberg博弈構(gòu)造了含有使用混合策略Nash的均衡準(zhǔn)則，用來表述出行選擇，能夠體現(xiàn)出行行為的多重性和多元性。而蟻群算法的引入，合理地解決了這個復(fù)雜的博弈模型的求解方法問題，也為問題的完善開辟了一條新思路。

［1］ 施錫銓.博弈論［M］.上海：上海財經(jīng)大學(xué)出版社，2000.

［2］ 陳濤，陳森發(fā)，陶耘.公交與軌道交通的多維Stackelberg博弈與均衡［J］.系統(tǒng)工程學(xué)報，2010，25（5）：638.

［3］ Bell M G H.A game theory approach to measuring the performance reliability of transport networks［J］. Transportation Research Part B，2000，34（6）：533.

［4］ Bell M G H，Cassir C.Risk averse user equilibrium traffic assignment：an application of game theory［J］.Transportation Research Part B，2002，36（8）：671.

［5］ Perez T，Goodwin G C.Constrained predictive control of ship fin stabilizers to prevent dynamic stall［J］.Control Engineering Practice，2008，16（4）：482.

［6］ 李士勇.蟻群算法的改進(jìn)及應(yīng)用研究進(jìn)展［J］.計算機(jī)測量與控制，2003，11（12）：911.

Multidimensional Stackelberg Game Assignment Based on Ant Colony Algorithm

Ai Yi，Li Zongping

To discuss the network traffic flow in urban bus system and the distribution of urban rail transit，Stackelberg Game is used for traffic distribution study and the Nash equilibriumis established.According to an assumption，there aremultipleOD（origin of departure）on road network，based on the Wardrop equilibrium standards，the trip users of each OD is proved to be homogeneous.Thus，a mixed strategy Stackelberg-Nash equilibrium game model for bus route and rail transit route is established.Then，with an improved ant colony algorithm for travelers，the process of equilibrium is simulated.The numerical results show that the improved ant colony simulates the matchup Stackelberg Game equilibrium process very reasonably.

urban traffic；urban rail transit；traffic flow distribution；Stackelberg game；improved ant colony algorithm

U 491.1+12

2012-04-13）