趙建東　段曉紅　宋守信

(1．北京交通大學(xué) 機(jī)械與電子控制工程學(xué)院， 北京 100044；2．北京交通大學(xué) 經(jīng)濟(jì)管理學(xué)院， 北京 100044)

基于非合作博弈的應(yīng)急車(chē)輛調(diào)度與再配置*

趙建東1段曉紅1宋守信2

(1．北京交通大學(xué) 機(jī)械與電子控制工程學(xué)院， 北京 100044；2．北京交通大學(xué) 經(jīng)濟(jì)管理學(xué)院， 北京 100044)

摘要：多事故多救援站點(diǎn)的應(yīng)急車(chē)輛調(diào)度問(wèn)題中，在處置當(dāng)前事故時(shí)，若將空閑車(chē)輛再配置于救援站點(diǎn)，有利于對(duì)潛在事故的快速響應(yīng).文中采用雙層規(guī)劃理論和非合作博弈理論建立應(yīng)急車(chē)輛調(diào)度與再配置模型.上層模型在事故需求和救援時(shí)間窗約束下，最小化當(dāng)前事故響應(yīng)時(shí)間；下層模型將各救援站點(diǎn)視為非合作博弈的局中人，綜合考慮車(chē)輛再配置時(shí)間和救援站覆蓋區(qū)域潛在風(fēng)險(xiǎn)，確定局中人的收益函數(shù)，將優(yōu)化再配置策略轉(zhuǎn)化為尋求非合作博弈的納什均衡.然后，提出一種層次混合蛙跳算法，其中上層算法用于求解約束單目標(biāo)規(guī)劃問(wèn)題，下層算法用于求解非合作博弈模型.求解事故算例證明了應(yīng)急車(chē)輛調(diào)度與再配置模型的合理性和層次混合蛙跳算法的有效性.

關(guān)鍵詞：應(yīng)急車(chē)輛；調(diào)度算法；資源配置；博弈論

高速公路里程和路網(wǎng)密度的迅速增加、交通出行量和交通事故發(fā)生頻率的急劇上升、交通安全形勢(shì)的日趨嚴(yán)峻，對(duì)快速高效的事故應(yīng)急救援能力提出了迫切需求.科學(xué)合理地調(diào)度有限的應(yīng)急車(chē)輛是應(yīng)急救援的關(guān)鍵問(wèn)題，可有效減少事故損失.

目前，應(yīng)急車(chē)輛調(diào)度研究主要集中在調(diào)度建模方法和調(diào)度求解算法.調(diào)度建模方面，Yamada[1]提出僅考慮當(dāng)前事故救援需求，應(yīng)急資源調(diào)度決策可轉(zhuǎn)化為路網(wǎng)最短路的求解，以選擇事故最近出救點(diǎn).何建敏等[2]針對(duì)單事故下多出救點(diǎn)選擇問(wèn)題，引入時(shí)間最短的概念，提出了單目標(biāo)、多目標(biāo)等多種組合優(yōu)化模型.戴更新等[3]將單資源調(diào)度擴(kuò)展到多資源調(diào)度，以救援起始時(shí)間最早為目標(biāo)，建立了多資源調(diào)度數(shù)學(xué)模型.Carter等[4]指出考慮未來(lái)事故需求，選擇離事故點(diǎn)最近的出救點(diǎn)不一定是最優(yōu)策略.Sherali等[5]將資源調(diào)度總成本定義為當(dāng)前事故救援成本和潛在事故救援機(jī)會(huì)成本的總和，建立了應(yīng)急車(chē)輛調(diào)度的機(jī)會(huì)成本法模型.Ozbay等[6]針對(duì)潛在事故資源需求的隨機(jī)性，引入服務(wù)質(zhì)量概念，建立了一種帶有概率型約束的整數(shù)規(guī)劃模型，用以解決交通事故響應(yīng)和資源調(diào)配問(wèn)題.Zhao等[7]針對(duì)機(jī)會(huì)成本模型中車(chē)輛速度和潛在事故概率的不確定性問(wèn)題，引入削弱救援車(chē)速系數(shù)概念，修正了機(jī)會(huì)成本模型中的速度參數(shù).楊繼君等[8]研究了在應(yīng)急資源有限條件下的多災(zāi)點(diǎn)資源調(diào)度問(wèn)題，考慮到各災(zāi)點(diǎn)利益的沖突性，建立了基于非合作博弈的應(yīng)急資源調(diào)度模型.Yang等[9]建立了帶區(qū)域覆蓋約束的應(yīng)急優(yōu)化車(chē)輛調(diào)度模型，通過(guò)將空閑車(chē)輛重新配置于各救援站點(diǎn)的方法避免對(duì)潛在事故的救援延遲.

調(diào)度求解算法方面，Chang等[10]提出一種基于貪婪搜索的多目標(biāo)遺傳算法，自動(dòng)生成多種可行的應(yīng)急物資調(diào)度策略.Ichoua等[11]應(yīng)用并行禁忌搜索算法，分別求解了基于靜態(tài)和動(dòng)態(tài)參數(shù)的車(chē)輛調(diào)度模型.劉芹等[12]設(shè)計(jì)了一種混合粒子群算法來(lái)實(shí)現(xiàn)車(chē)輛調(diào)度模型的求解.楊仁法等[13]運(yùn)用蟻群算法把時(shí)間窗約束轉(zhuǎn)化為懲罰函數(shù)形式，求解了帶時(shí)間窗約束的配送中心車(chē)輛調(diào)度問(wèn)題.

綜述文獻(xiàn)，國(guó)內(nèi)外學(xué)者在應(yīng)急車(chē)輛調(diào)度建模時(shí)已考慮車(chē)輛再配置.筆者在文獻(xiàn)[14]中提出將救援站覆蓋區(qū)域潛在風(fēng)險(xiǎn)作為關(guān)鍵約束，建立了應(yīng)急車(chē)輛調(diào)度與再配置的多目標(biāo)規(guī)劃模型.接著，在文獻(xiàn)[15]中分析了應(yīng)急車(chē)輛調(diào)度和再配置兩類(lèi)目標(biāo)間的層級(jí)關(guān)系，建立了雙層規(guī)劃模型.模型以當(dāng)前事故響應(yīng)時(shí)間最短為上層目標(biāo)，應(yīng)急車(chē)輛再配置時(shí)間最短為下層目標(biāo).進(jìn)一步分析文獻(xiàn)[8]、[16-17]發(fā)現(xiàn)，非合作博弈理論在求解資源限制條件下的多災(zāi)點(diǎn)應(yīng)急資源調(diào)度、作業(yè)車(chē)間任務(wù)調(diào)度及出租車(chē)調(diào)度等競(jìng)爭(zhēng)問(wèn)題時(shí)均體現(xiàn)了考慮各局中人之間利益沖突的優(yōu)點(diǎn).因此，在文獻(xiàn)[14-15]的研究基礎(chǔ)上，文中提出應(yīng)用非合作博弈理論求解下層應(yīng)急車(chē)輛再配置過(guò)程中的沖突問(wèn)題.通過(guò)將各個(gè)救援站視為博弈模型的局中人，可能的車(chē)輛再配置方案映射為策略集，從而將應(yīng)急車(chē)輛再配置問(wèn)題轉(zhuǎn)化為對(duì)非合作博弈模型的納什均衡點(diǎn)求解.此外，還設(shè)計(jì)了一種層次混合蛙跳算法實(shí)現(xiàn)模型求解.

1問(wèn)題描述

圖1　多事故多救援點(diǎn)應(yīng)急車(chē)輛調(diào)度問(wèn)題Fig.1　Emergency vehicle scheduling problem with multiple accidents and multiple rescue sites

2模型構(gòu)建

路網(wǎng)內(nèi)應(yīng)急車(chē)輛儲(chǔ)備有限，導(dǎo)致當(dāng)前事故救援需求和潛在事故儲(chǔ)備之間存在著競(jìng)爭(zhēng)關(guān)系.應(yīng)急車(chē)輛應(yīng)優(yōu)先調(diào)度至事故點(diǎn)，以救援當(dāng)前事故.當(dāng)前事故救援策略可指導(dǎo)以保證潛在事故資源儲(chǔ)備為目標(biāo)的應(yīng)急車(chē)輛再配置決策.同時(shí)，應(yīng)急車(chē)輛調(diào)度決策也需兼顧考慮車(chē)輛再配置選擇.據(jù)此，文中將當(dāng)前事故救援問(wèn)題作為上層問(wèn)題，應(yīng)急車(chē)輛再配置問(wèn)題作為下層問(wèn)題，建立雙層規(guī)劃模型.

2.1上層模型構(gòu)建

2.1.1 上層目標(biāo)函數(shù)

事故響應(yīng)時(shí)間是調(diào)度決策的關(guān)鍵因素，事故響應(yīng)時(shí)間由調(diào)度決策時(shí)間與車(chē)輛在途時(shí)間構(gòu)成[5]，上層目標(biāo)函數(shù)用于最小化車(chē)輛在途時(shí)間：

(1)

2.1.2上層約束條件

(1)事故需求約束

前往事故ej的車(chē)輛總和與事故ej的需求Nj相一致：

(2)

(2)救援時(shí)間窗約束

(3)

(4)

2.2下層模型構(gòu)建

在路網(wǎng)內(nèi)應(yīng)急車(chē)輛有限的情況下，各個(gè)救援站所需資源是相互沖突的，各方利益相互影響，一方利益的增加必然導(dǎo)致其他救援站利益的減少.從博弈論角度來(lái)看，各救援站間潛在事故對(duì)應(yīng)急車(chē)輛的需求可認(rèn)為是非合作博弈的，博弈的目的是盡量為自身爭(zhēng)取更合理的效用，即以更少的成本獲得更多的資源.

(1)策略集

(5)

(2)效用函數(shù)

(6)

2.2.1下層目標(biāo)函數(shù)

定義1策略組合X2*是I人非合作博弈的一個(gè)納什均衡解，如果X2*滿(mǎn)足：

(7)

在應(yīng)急車(chē)輛再配置問(wèn)題中，每一個(gè)救援站si從其策略集Gi中選取某一種策略，組成I人博弈的策略組合X2.根據(jù)納什均衡定義，下層目標(biāo)函數(shù)為

(8)

2.2.2下層約束條件

應(yīng)急車(chē)輛vk可以派往當(dāng)前事故點(diǎn)或者再配置于救援站點(diǎn)，且只能處于兩種狀態(tài)之一：

(9)

3基于層次混合蛙跳算法的車(chē)輛調(diào)度模型求解

混合蛙跳算法(SFLA)是一種模因元啟發(fā)式算法，采用混合進(jìn)化算法(SCE)的全局尋優(yōu)策略和粒子群算法(PSO)的局部迭代規(guī)則.算法基于族群內(nèi)個(gè)體模因進(jìn)化和種群中全局信息交流，將青蛙種群分為多個(gè)族群，各族群內(nèi)青蛙通過(guò)信息交換實(shí)現(xiàn)局部深度進(jìn)化.一段時(shí)間后，將各子族群混合，使信息在整個(gè)種群內(nèi)得到交流.各子族群內(nèi)局部尋優(yōu)和全局信息融合往復(fù)執(zhí)行至達(dá)到指定進(jìn)化代數(shù).

(10)

其中，Mo表示第o個(gè)族群.

根據(jù)式(11)及(12)，各子族群中的最差青蛙位置W跟隨族群內(nèi)最優(yōu)青蛙位置Y或種群最優(yōu)青蛙位置Z進(jìn)行局部更新，直到完成指定迭代次數(shù)α.

(11)

Wnew=Wold+β

(12)

其中，r為一隨機(jī)數(shù)且r∈[0,1]，β表示青蛙個(gè)體的調(diào)整矢量，δ表示最大調(diào)整步長(zhǎng)，Wold和Wnew分別為更新前、后的最差青蛙位置 .

完成局部搜索的各族群重新混合，排序后執(zhí)行下一次分組及局部搜索，直至完成指定的外層迭代次數(shù)η.

3.1求解非合作博弈模型的混合蛙跳算法

求解非合作博弈模型的混合蛙跳算法中，每只青蛙的位置g=(g1,g2,…,gI),gi∈Gi,1≤i≤I，代表I人博弈的一個(gè)策略組合.青蛙群體在策略組合空間中尋找最優(yōu)位置，青蛙位置的優(yōu)劣由適應(yīng)度函數(shù)反應(yīng)，當(dāng)青蛙處于最優(yōu)位置時(shí)對(duì)應(yīng)的適應(yīng)度函數(shù)到達(dá)最大.與目標(biāo)函數(shù)相一致，應(yīng)急車(chē)輛再配置問(wèn)題的適應(yīng)度函數(shù)定義為

(13)

3.2求解雙層規(guī)劃問(wèn)題的層次混合蛙跳算法

采用與文獻(xiàn)[15]相同的雙層架構(gòu)，設(shè)計(jì)求解應(yīng)急車(chē)輛調(diào)度與再配置的層次混合蛙跳算法.該架構(gòu)集成了兩個(gè)基本混合蛙跳算法模型SFLA_U及SFLA_D.

3.2.1編碼方案設(shè)計(jì)

X(χ,:)=[xχ,1,xχ,2,…,xχ,k,…,xχ,K]

(14)

3.2.2適應(yīng)度函數(shù)設(shè)計(jì)

(15)

ωj=ξj

(16)

(17)

(18)

式中，εj、ξj分別表示事故ej的現(xiàn)場(chǎng)疏散能力及事故嚴(yán)重程度.同文獻(xiàn)[15]，εj定義見(jiàn)表1.對(duì)應(yīng)于事故由輕微到嚴(yán)重的4個(gè)等級(jí)，εj的取值依次為40、60、80、100.

表1時(shí)間窗約束懲罰

Table 1Punishment for time window constraints

被影響車(chē)道數(shù)目εjjmin1812.52616.7被影響車(chē)道數(shù)目εjjmin3425.0>3250.0

下層混合蛙跳算法SFLA_U用來(lái)求解基于非合作博弈論的應(yīng)急車(chē)輛再配置模型，其適應(yīng)度函數(shù)κD(X2)為

(19)

4算例分析

表2救援站參數(shù)

Table 2Rescue site parameters

si算例Ris1I25II21s2I22II24si算例Ris3I17II27s4I10II10

表3當(dāng)前事故參數(shù)

Table 3Current accident parameters

ej算例NjξjεjTjmaxTjminωjjmaxjmine1I2604155606025.0II1408100404012.5e2I140880404012.5II16062010606016.7e3III1804156808025.0

表4車(chē)輛在途時(shí)間

Table 4Travel time matrix

應(yīng)急車(chē)輛算例e1e2e3s1s2s3s4v1I810II6812010514v2I126II12814100128v3I612II713131111614v4I715II9167131209v5I1310II15149166155

根據(jù)決策變量規(guī)模大小，層次混合蛙跳算法參數(shù)選擇如表5所示.運(yùn)行層次混合蛙跳算法，經(jīng)過(guò)尋優(yōu)過(guò)程，獲得兩個(gè)算例的最優(yōu)解如表6所示.表中包含有文獻(xiàn)[15]原模型的最優(yōu)解數(shù)據(jù).并分別采用層次混合蛙跳算法(SFLA)和文獻(xiàn)[18]中的層次粒子群算法(PSO)對(duì)兩個(gè)算例進(jìn)行求解，結(jié)果見(jiàn)表7.

表5層次混合蛙跳算法參數(shù)設(shè)置

Table 5Selection of parameters of integrated bi-level shuffled frog-leaping algorithm

算例上層種群規(guī)模上層族群數(shù)上層組內(nèi)迭代次數(shù)上層全局迭代次數(shù)上層最大調(diào)整步長(zhǎng)I30020155[6,6,6,6,6]II500252010[7,7,7,7,7]編號(hào)下層種群規(guī)模下層族群數(shù)下層組內(nèi)迭代次數(shù)下層全局迭代次數(shù)下層最大調(diào)整步長(zhǎng)I15015105[6,6,6,6,6]II15015105[7,7,7,7,7]

表6算例最優(yōu)解

Table 6Optimal solutions of examples

算例上層目標(biāo)最優(yōu)值下層目標(biāo)最優(yōu)值最優(yōu)解本模型原模型文中模型原模型文中模型原模型I19460.3733113,2,1,1,43,2,1,1,4II28570.1900154,5,1,3,21,5,2,3,6

表7層次混合蛙跳算法與層次粒子群算法的對(duì)比

Table 7Comparison of integrated bi-level shuffled frog-leaping algorithm and particle swarm optimization algorithm

算例最優(yōu)解平均迭代次數(shù)求解時(shí)間/s10次運(yùn)行中獲得最優(yōu)解的比例/%SFLAPSOSFLAPSOSFLAPSOSFLAPSOI3,2,1,1,45.342.68.5225.489050II4,5,1,3,26.851.315.0344.379050

4.1算例I的結(jié)果分析

文中模型獲得的最優(yōu)解均為[3,2,1,1,4]，和原模型一樣.最優(yōu)調(diào)度與再配置策略如圖2所示，表示應(yīng)急車(chē)輛v1前往救援站s1，應(yīng)急車(chē)輛v2前往事故點(diǎn)e2，應(yīng)急車(chē)輛v3和v4前往事故點(diǎn)e1，應(yīng)急車(chē)輛v5前往救援站s2.最優(yōu)策略分析如下.

圖2　最優(yōu)調(diào)度與再配置策略Fig.2　Optimal scheduling and reallocation strategy

4.1.1對(duì)于事故e1的應(yīng)急車(chē)輛調(diào)度策略

事故e1的應(yīng)急車(chē)輛需求為2，將5輛車(chē)到達(dá)事故點(diǎn)e1的在途時(shí)間升序排列為(v3：6 min)，(v4：7 min)，(v1：8 min)，(v2：12 min)和(v5：13 min).若將車(chē)輛v3和v4派往事故e1，則滿(mǎn)足使應(yīng)急車(chē)輛在途時(shí)間最小的上層目標(biāo).然而，在滿(mǎn)足事故點(diǎn)e1應(yīng)急車(chē)輛需求的同時(shí)，還應(yīng)考慮事故點(diǎn)e2的需求及對(duì)各救援站的車(chē)輛再配置.假設(shè)選擇次優(yōu)策略，應(yīng)急車(chē)輛v1代替v3或v4被派往事故e1，則增加了車(chē)輛在途時(shí)間的同時(shí)，也使對(duì)救援站s1的再配置時(shí)間延長(zhǎng)了至少10 min.可見(jiàn)，將應(yīng)急車(chē)輛v3和v4派往事故e1是合理的.

4.1.2對(duì)于事故e2的應(yīng)急車(chē)輛調(diào)度策略

事故e2的應(yīng)急車(chē)輛需求為1，將5輛車(chē)到達(dá)事故點(diǎn)e2的在途時(shí)間升序排列為(v2：6 min)，(v1：10 min)，(v5：10 min)，(v3：12 min)和(v4：15 min).若將車(chē)輛v2派往事故e2，則滿(mǎn)足使應(yīng)急車(chē)輛在途時(shí)間最小的上層目標(biāo).假設(shè)選擇次優(yōu)策略，將車(chē)輛v1派往事故e2，則車(chē)輛在途時(shí)間增加了4 min，為保證對(duì)當(dāng)前事故e2的快速救援，應(yīng)將車(chē)輛v2派往事故e2.

4.1.3應(yīng)急車(chē)輛再配置策略

由于應(yīng)急車(chē)輛v2、v3和v4前往救援當(dāng)前事故，空閑車(chē)輛為v1和v5.為分析下層模型的有效性，計(jì)算所有可能再配置策略對(duì)應(yīng)的目標(biāo)函數(shù)值，結(jié)果如表8所示.

表8再配置策略下層目標(biāo)函數(shù)值

Table 8Performance function value of the second level of possible strategies

可能策略下層目標(biāo)函數(shù)值[3,2,1,1,3]0.6288[3,2,1,1,4]0.3733[3,2,1,1,5]0.3987[3,2,1,1,6]0.3900[4,2,1,1,3]0.6224[4,2,1,1,4]0.6325[4,2,1,1,5]0.6267[4,2,1,1,6]0.6180可能策略下層目標(biāo)函數(shù)值[5,2,1,1,3]0.6104[5,2,1,1,4]0.5893[5,2,1,1,5]0.6430[5,2,1,1,6]0.6060[6,2,1,1,3]0.6372[6,2,1,1,4]0.6162[6,2,1,1,5]0.6415[6,2,1,1,6]0.6495

由表可見(jiàn)，策略[3,2,1,1,4]的下層目標(biāo)函數(shù)值最小，該策略更符合應(yīng)急車(chē)輛調(diào)度與再配置模型的優(yōu)化目標(biāo).

4.2算例II的結(jié)果分析

文中模型求得的最優(yōu)解為[4,5,1,3,2]，而原模型的最優(yōu)解為[1,5,2,3,6]，如表9所示，將最優(yōu)解解碼并進(jìn)行比較.最優(yōu)調(diào)度與再配置策略如圖2所示，表示應(yīng)急車(chē)輛v1前往救援站s1，應(yīng)急車(chē)輛v2前往救援站s2，應(yīng)急車(chē)輛v3前往事故點(diǎn)e1，應(yīng)急車(chē)輛v4前往事故點(diǎn)e3，應(yīng)急車(chē)輛v5前往事故點(diǎn)e2.

4.2.1對(duì)于當(dāng)前事故的應(yīng)急車(chē)輛調(diào)度策略

事故e1的應(yīng)急車(chē)輛需求為1，將5輛車(chē)到達(dá)事故點(diǎn)e1的在途時(shí)間升序排列為(v1：6 min)，(v3：7 min)，(v4：9 min)，(v2：12 min)和(v5：15 min).若將車(chē)輛v1派往事故e1，則滿(mǎn)足使應(yīng)急車(chē)輛在途時(shí)間最小的上層目標(biāo).假設(shè)選擇次優(yōu)的策略，應(yīng)急車(chē)輛v3代替v1被派往事故e1，則當(dāng)前事故e1的救援時(shí)間僅延長(zhǎng)1 min，而對(duì)具有最高潛在風(fēng)險(xiǎn)的救援站s1的再配置時(shí)間縮短了10 min，可見(jiàn)，應(yīng)該將應(yīng)急車(chē)輛v3派往事故點(diǎn)e1.

同理，可證明對(duì)事故點(diǎn)e2和e3的調(diào)度策略是合理的.

4.2.2應(yīng)急車(chē)輛再配置策略

由表9可知，文中模型求得最優(yōu)策略的目標(biāo)函數(shù)值較原模型優(yōu)化了56%，說(shuō)明策略[4,5,1,3,2]的整體效用比 [1,5,2,3,6]高，因此文中模型獲得的策略更加合理.

表9算例II兩種最優(yōu)策略對(duì)比

Table 9Comparison of two optimum strategies of example II

模型最優(yōu)解最優(yōu)策略車(chē)輛在途時(shí)間/min時(shí)間窗約束懲罰當(dāng)前事故需求懲罰潛在事故需求懲罰改進(jìn)模型下層目標(biāo)函數(shù)值車(chē)輛再配置時(shí)間/min文中模型4,5,1,3,2v1→s1v2→s2v3→e1v4→e3v5→e22800—0.19000原模型1,5,2,3,6v1→e1v2→s2v3→e2v4→e3v5→s32600310.428715

4.3算法性能分析

表7中2個(gè)算例數(shù)據(jù)表明，層次混合蛙跳算法和層次粒子群算法在10次運(yùn)行后均能獲得最優(yōu)解，層次混合蛙跳算法平均求解時(shí)間大約為層次粒子群算法的1/3；前者10次運(yùn)行中獲得的最優(yōu)解比例高于后者.

5結(jié)語(yǔ)

事故發(fā)生后，調(diào)度應(yīng)急車(chē)輛對(duì)當(dāng)前事故進(jìn)行有效救援的同時(shí)，綜合考慮救援站覆蓋區(qū)域潛在風(fēng)險(xiǎn)情況，對(duì)應(yīng)急車(chē)輛進(jìn)行統(tǒng)籌再配置，可以有效縮短對(duì)潛在事故的響應(yīng)時(shí)間.文中基于應(yīng)急車(chē)輛調(diào)度與再配置雙層規(guī)劃模型，考慮各救援站點(diǎn)對(duì)于有限資源的競(jìng)爭(zhēng)關(guān)系，將各救援站點(diǎn)視為非合作博弈的局中人，定義了與再配置時(shí)間和救援站覆蓋區(qū)潛在風(fēng)險(xiǎn)相關(guān)的收益函數(shù)，通過(guò)尋求多人非合作博弈的納什均衡解獲得優(yōu)化的再配置策略；設(shè)計(jì)了一種層次混合蛙跳算法完成了模型的求解，上層算法采用基于權(quán)重的混合蛙跳算法模型，下層采用求解非合作博弈的混合蛙跳算法模型.模型的算例驗(yàn)證結(jié)果表明：文中雙層規(guī)劃模型符合應(yīng)急車(chē)輛調(diào)度與再配置問(wèn)題的決策規(guī)則；下層模型綜合考慮應(yīng)急車(chē)輛再配置時(shí)間和區(qū)域潛在風(fēng)險(xiǎn)，符合下層問(wèn)題的決策目標(biāo)；基于雙層規(guī)劃問(wèn)題及非合作博弈問(wèn)題求解思想設(shè)計(jì)的層次蛙跳算法，能較好地求解應(yīng)急車(chē)輛調(diào)度與再配置模型，且在求解速度和準(zhǔn)確度方面均優(yōu)于層次粒子群算法.

參考文獻(xiàn)：

[1]YAMADA Takeo. A network flow approach to a city emergency evacuation planning [J]. International Journal of Systems Science,1996,27(10):931-936.

[2]何建敏,劉春林,尤海燕. 應(yīng)急系統(tǒng)多出救點(diǎn)的選擇問(wèn)題 [J]. 系統(tǒng)工程理論與實(shí)踐,2001,21 (11):89-93.

HE Jian-min,LIU Chun-lin,YOU Hai-yan. Selection of multi-depot in emergency systems [J]. Systems Engineering—Theory and Practice,2001,21(11):89-93.

[3]戴更新,達(dá)慶利. 多資源組合應(yīng)急調(diào)度問(wèn)題的研究[J]. 系統(tǒng)工程理論與實(shí)踐,2000,20(9):52-55.

DAI Geng-xin,DA Qing-li. The study of combinatorial scheduling problem in emergency systems [J].Systems Engineering—Theory and Practice,2000,20 (9):52-55.

[4]CARTER G M,CHAIKEN J M,IGNALL E. Response area for two emergency units [J]. Operations Research,1972,20(3):571-594.

[5]SHERALI H D,SUBRAMANIAN S. Opportunity cost-based models for traffic incident response problems [J]. Journal of Transportation Engineering,1999,125(3):176-185.

[6]OZBAY Kaan,XIAO Weihua. Probabilistic programming models for response vehicle dispatching and resource allocation in traffic incident management[C]∥Proceedings of the 83rdAnnual Meeting Compendium of Papers CD-ROM. Washington D C: Transportation Research Board,2004.

[7]ZHAO Jiandong,DUAN Xiaohong,ZHANG Lina,et al. Traffic emergency resources dispatch based on opportunity cost method with GA-BP optimization model [J]. Advances in Information Sciences and Service Sciences,2013,5(9):301-309.

[8]楊繼君,許維勝,黃武軍,等. 基于多災(zāi)點(diǎn)非合作博弈的資源調(diào)度建模與仿真[J]. 計(jì)算機(jī)應(yīng)用,2008,28(6):1620-1623.

YANG Ji-jun,XU Wei-sheng,HUANG Wu-jun,et al. Modeling and analyzing of simulation based on non-coope-rative games for multiple emergency locations in resources scheduling [J]. Computer Applications,2008,28(6):1620-1623.

[9]YANG Saini,HAMEDI Masoud,HAGHANI Ali. Online dispatching and routing model for emergency vehicles with area coverage constraints [J]. Transportation Research Record,2005,1923:1-8.

[10]CHANG Fu-Sheng,WU Jain-Shing,LEE Chung-Nan,et al. Greedy-search-based multi-objective genetic algorithm for emergency logistics scheduling [J]. Expert Systems with Application,2014,41(6):2947-2956.

[11]ICHOUA Soumia,GENDREAU Michel,POTVIN Jean-Yves. Vehicle dispatching with time-dependent travel times [J]. European Journal of Operational Research,2003,144(2):379-396.

[12]劉芹,史忠科. 混合粒子群算法求解交通路網(wǎng)中的車(chē)輛調(diào)度問(wèn)題[J]. 控制與決策,2006,21 (11):1284-1288.

LIU Qin,SHI Zhong-ke. Hybrid particle swarm algorithm for vehicle routing problem in road networks [J]. Control and Decision,2006,21 (11):1284-1288.

[13]楊仁法,龔延成. 帶時(shí)間窗車(chē)輛調(diào)度問(wèn)題的蟻群算法[J]. 交通運(yùn)輸工程學(xué)報(bào),2009,9(4):71-74.

YANG Ren-fa,GONG Yan-cheng. Ant colony algorithm of vehicle scheduling problem with time windows [J]. Journal of Traffic and Transportation Engineering,2009,9(4):71-74.

[14]DUAN Xiaohong,SONG Shouxin,ZHAO Jiandong,et al. Emergency vehicle dispatching based on shuffled frog leaping algorithm [J]. Journal of Computational Information Systems,2013,9(24):9875-9884.

[15]DUAN Xiaohong,SONG Shouxin,ZHAO Jiandong. Emergency vehicle dispatching and redistribution in highway network based on bi-level programming [J]. Mathematical Problems in Engineering,2015,2015:1-12.

[16]周光輝,王蕊,江平宇，等. 作業(yè)車(chē)間調(diào)度的非合作博弈模型與混合自適應(yīng)遺傳算法[J]. 西安交通大學(xué)學(xué)報(bào),2010,44(5):35-39.

ZHOU Guang-hui,WANG Rui,JIANG Ping-yu,et al. Non-cooperation game model and hybrid adaptive genetic algorithm for job-shop scheduling [J]. Journal of Xi’an Jiaotong University,2010,44(5):35-39.

[17]BAI R B,LI J W,Atkin J A D,et al. A novel approach to independent taxi scheduling problem based on stable matching [J]. Journal of the Operational Research Society,2014,65(10):1501-1510.

[18]趙志剛,顧新一,李陶深. 求解雙層規(guī)劃模型的粒子群優(yōu)化算法[J]. 系統(tǒng)工程理論與實(shí)踐,2007,27(8):92-98.

ZHAO Zhi-gang,GU Xin-yi,LI Tao-shen. Particle swarm optimization for bi-level programming problem [J]. Systems Engineering—Theory and Practice,2007,27(8):92-98.

Emergency Vehicle Scheduling and Reallocation on the Basis of Non-Cooperative Game

ZHAOJian-dong1DUANXiao-hong1SONGShou-xin2

(1.School of Mechanical and Electronic Control Engineering, Beijing Jiaotong University, Beijing 100044, China;2.School of Economics and Management, Beijing Jiaotong University, Beijing 100044, China)

Abstract:When an emergency vehicle scheduling problem involving multiple accidents and multiple rescue sites occurs, the response time of potential accidents can be shortened by redistributing idle emergency vehicles on rescue sites, in addition to optimizing the scheduling of vehicles for current accidents.This paper presents an improved model of emergency vehicle scheduling and reallocation on the basis of bi-level programming and non-cooperative game.The upper level of the model is established under the constraints of accident requirements and accident rescue window to minimize the response time for current accidents, while in the lower level of the model, each rescue site is treated as a participant in a non-cooperative game, the payoff function of each participant is determined after taking into account the reallocation time of the vehicle and the potential risks within the coverage area of each rescue site, so that the optimal reallocation strategy is transferred into Nash equilibrium in a non-cooperative game.Afterwards, an integrated bi-level shuffled frog-leaping algorithm is proposed, which contains an upper-layer algorithm for single-objective programming and a lower-layer algorithm for solving the non-cooperative game.Several illustrative examples verify the rationality of the proposed model and the effectiveness of the integrated bi-level shuffled frog-leaping algorithm.

Key words:emergency vehicles; scheduling algorithms; resource allocation; game theory

收稿日期：2015- 05-11

*基金項(xiàng)目：國(guó)家科技支撐計(jì)劃項(xiàng)目(2011BAG07B05-2)

Foundation item:Supported by the National Key Technology Research and Development Program of the Ministry of Science and Technology of China(2011BAG07B05-2)

作者簡(jiǎn)介：趙建東(1975-)，男，博士，副教授，主要從事交通安全與控制研究.E-mail：zhaojd@bjtu.edu.cn

中圖分類(lèi)號(hào)：X951

doi：10.3969/j.issn.1000-565X.2016.03.016