基于演化博弈的車輛路徑選擇研究

安莉

摘 要：基于演化博弈論，圍繞如何在車輛路徑選擇中提高誘導(dǎo)信息有效性和誘導(dǎo)效率等問題展開了研究。通過建立無誘導(dǎo)信息條件下的路網(wǎng)模型和建立誘導(dǎo)信息模型，研究不同初始條件對駕駛員的作用規(guī)律；通過拓展無誘導(dǎo)信息條件下的車輛路徑選擇的模型，設(shè)計了結(jié)合八鄰域摩爾模型和公共物品博弈模型的駕駛員群體策略演化機(jī)制，提高了誘導(dǎo)信息有效性和誘導(dǎo)效率。

關(guān)鍵詞：演化博弈 路徑選擇 公共物品博弈

中圖分類號：U495 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2018）04（c）-0126-03

伴隨著我國經(jīng)濟(jì)的騰飛和“十三五”規(guī)劃的順利進(jìn)行，現(xiàn)在我國汽車數(shù)量的增長速度相當(dāng)驚人。汽車數(shù)量的井噴式增長，造成了對交通管理的嚴(yán)峻挑戰(zhàn)，如何實現(xiàn)對道路資源的有效配置，成為了國內(nèi)外學(xué)者研究的熱點問題。為了緩解這個問題，既需要增加基礎(chǔ)設(shè)施的建設(shè)，同時也需要加強對道路資源的有效配置優(yōu)化[1]。

交通誘導(dǎo)是智能交通最重要的研究領(lǐng)域之一，交通誘導(dǎo)可以為車輛駕駛員提供實時交通信息[2]，幫助車輛駕駛員做選擇和決策，提高整個網(wǎng)絡(luò)現(xiàn)有速率的綜合利用率，避免出現(xiàn)局部道路擁堵而另一部分道路沒有有效利用的情況[3]。因為上述對交通管理的重要作用，交通誘導(dǎo)一直是國內(nèi)外研究領(lǐng)域熱點。交通誘導(dǎo)是從整個系統(tǒng)的角度出發(fā)，通過發(fā)布誘導(dǎo)信息可以使整個網(wǎng)絡(luò)實現(xiàn)最高的利用率，降低車輛駕駛員選擇路徑的最低成本。誘導(dǎo)信息最直接的作用是通過提供適當(dāng)?shù)慕煌ㄐ畔碚T導(dǎo)車輛駕駛員的路徑選擇行為。

1 誘導(dǎo)信息條件下的車輛路徑選擇研究

1.1 路網(wǎng)模型描述

為了更好的分析道路網(wǎng)絡(luò)路徑誘導(dǎo)系統(tǒng)，構(gòu)建路網(wǎng)模型如圖所示：

1.2 誘導(dǎo)信息條件下車輛路徑選擇模型的建立

距離相近的駕駛員之間組成八鄰域摩爾模型，八鄰域摩爾模型屬于二維方格網(wǎng)絡(luò)的元胞自動機(jī)，具有周期邊界條件，每個節(jié)點代表每個車輛駕駛員，每個駕駛均有八個鄰域駕駛員，如圖表示，該拓?fù)潢P(guān)系表示駕駛員與其鄰域駕駛員的的群體博弈關(guān)系。

距離相近的駕駛員之間組成八鄰域摩爾模型，八鄰域摩爾模型屬于二維方格網(wǎng)絡(luò)的元胞自動機(jī)，具有周期邊界條件，每個節(jié)點代表每個車輛駕駛員，每個駕駛均有八個鄰域駕駛員，如圖表示，該拓?fù)潢P(guān)系表示駕駛員與其鄰域駕駛員的群體博弈關(guān)系。公共物品博弈模型中，每個駕駛員和鄰域駕駛員進(jìn)行博弈，每個駕駛員既參加以自己為中心的群體博弈，也要參與以其鄰域駕駛員為中心的群體博弈，整個模型初始狀態(tài)是接受誘導(dǎo)的駕駛員與拒絕誘導(dǎo)的駕駛員均勻混合分布在這個駕駛員群體中，每個駕駛員在初始時以等概率選擇接受誘導(dǎo)信息或拒絕誘導(dǎo)信息，即每個駕駛員的博弈策略可選有接受誘導(dǎo)信息（C）和拒絕誘導(dǎo)信息（D）兩種。

公式（3）中，nc與nd分別代表這個群體中選擇接受誘導(dǎo)的駕駛員數(shù)量和拒絕誘導(dǎo)信息的駕駛員數(shù)，c（x）代表駕駛員i的成本。駕駛員i收益將以r的倍數(shù)增值，然后平分給群體中的所有駕駛員。在該模型中，駕駛員在有誘導(dǎo)信息的條件下，為了提高自身收益，縮短出行時間，向周圍鄰域駕駛員學(xué)習(xí)，不斷改進(jìn)自身的策略，選擇更優(yōu)的路徑。

1.3 誘導(dǎo)信息條件下車輛路徑選擇模型的演化

其演化規(guī)則如圖3所示，其步驟如下：

Step 0：h=h+1，x=0.1，i=0，給r、k、T、β賦值（x為誘導(dǎo)路徑的流量所占比例）；

Step 1：初始化，給出模型的初始狀態(tài)；

Step 2：根據(jù)時間行程函數(shù)求得選擇路徑的通過時間；

Step 3：根判斷駕駛員第i次收益，確定博弈的初始狀態(tài)；

Step 4：由博弈初始狀態(tài)確定第i+1次路徑L的流量；

Step 5：i=i+1，若i<100，轉(zhuǎn) Step 2；否則轉(zhuǎn) Step 6；

Step 6：若Δpi>0，x=x+0.1，轉(zhuǎn) Step 1，否則轉(zhuǎn) Step 7；

Step 7：若Δpi<0，轉(zhuǎn) Step 0，否則結(jié)束。

1.4 數(shù)值仿真

如圖4-（a）所示，橫坐標(biāo)為演化代數(shù)，縱坐標(biāo)為接受誘導(dǎo)的駕駛員比例。在該初始條件 下，因為考慮一定的非理性因素，一部分駕駛員并沒有及時改進(jìn)自己的策略接受誘導(dǎo)，在演化前期接受誘導(dǎo)的駕駛員比例有一定的下降趨勢；隨著演化代數(shù)的繼續(xù)增加，駕駛員通過利用模仿鄰域駕駛員的學(xué)習(xí)機(jī)制，越來越多的駕駛員開始接受誘導(dǎo)并提高了自身收益。接受誘導(dǎo)的駕駛員比例提高迅速，很快就趨近于1，說明該學(xué)習(xí)機(jī)制下達(dá)到交通誘導(dǎo)需要的演化代數(shù)更少，收益提高更明顯，誘導(dǎo)效率更高，誘導(dǎo)效果更顯著。

將圖4-（a）與圖4-（b）做對比可發(fā)現(xiàn)，同樣的初始條件下，八領(lǐng)域摩爾模型協(xié)作機(jī)制下達(dá)到博弈均衡只需要20 代左右的演化，而傳統(tǒng)演化博弈機(jī)制下達(dá)到博弈均衡需要100 代左右的演化，說明結(jié)合八鄰域摩爾模型的交通誘導(dǎo)算法微觀上減少了駕駛員的行程時間，減少了需要到達(dá)博弈均衡的演化代數(shù)，加快了誘導(dǎo)效率。

2 結(jié)語

本文在現(xiàn)有車輛路徑選擇算法研究的基礎(chǔ)上，設(shè)計了基于演化博弈的誘導(dǎo)信息，進(jìn)而重點討論了誘導(dǎo)信息對車輛路徑誘導(dǎo)的作用規(guī)律并研究了如何提高誘導(dǎo)信息的有效性。并對上述的車輛路徑選擇算法進(jìn)行了仿真研究工作，取得了一定的成果。

參考文獻(xiàn)

[1] 中華人民共和國國家統(tǒng)計局.中華人民共和國2016 年國民經(jīng)濟(jì)和社會發(fā)展統(tǒng)計公報[N].人民日報，2017-03-01（010）.

[2] 陸化普，孫智源，屈聞聰.大數(shù)據(jù)及其在城市智能交通系統(tǒng)中的應(yīng)用綜述[J].交通運輸系統(tǒng)工程與信息，2015，15 （5）：45-52.

[3] 趙娜，袁家斌，徐晗.智能交通系統(tǒng)綜述[J].計算機(jī)科學(xué)，2014，5（11）：7-11.

[4] 何增鎮(zhèn).基于Multi-Agent 與博弈論的城市交通控制誘導(dǎo)系統(tǒng)及其關(guān)鍵技術(shù)研究[D].湖南：中南大學(xué)，2010.

[5] 董斌杰，李克平，廖明軍.誘導(dǎo)信息下基于博弈論的路徑選擇模型[J].北華大學(xué)學(xué)報：自然科學(xué)版，2007（1）：88-91.