王付宇，葉春明，王濤（.安徽工業(yè)大學(xué)管理科學(xué)與工程學(xué)院，安徽馬鞍山4303；.上海理工大學(xué)管理學(xué)院，上海00093）

城市突發(fā)事件下的應(yīng)急物資配送路徑尋優(yōu)

王付宇1，2，葉春明2，王濤1
（1.安徽工業(yè)大學(xué)管理科學(xué)與工程學(xué)院，安徽馬鞍山243032；2.上海理工大學(xué)管理學(xué)院，上海200093）

針對(duì)城市突發(fā)事件環(huán)境下的應(yīng)急物資配送車輛行駛路徑尋優(yōu)問(wèn)題，分析城市道路擁堵?tīng)顩r對(duì)于救援車輛行駛速度的影響。以車輛到達(dá)待救點(diǎn)的時(shí)間和行駛成本最少為目標(biāo)，構(gòu)建雙層規(guī)劃路徑尋優(yōu)模型。為提高全局搜索和局部尋優(yōu)能力，采用一種改進(jìn)的兩階段式螢火蟲(chóng)算法。算例結(jié)果表明所提出的模型和算法可有效解決城市突發(fā)事件下的應(yīng)急物資配送問(wèn)題。

應(yīng)急救援；路徑尋優(yōu)；雙層理論；螢火蟲(chóng)算法

近年來(lái)，除了地震、洪澇等大規(guī)模自然災(zāi)害頻發(fā)，城市內(nèi)部公共突發(fā)性事件也層出不窮，其帶來(lái)的生命威脅與財(cái)產(chǎn)損失不可忽視。此類城市范圍內(nèi)突發(fā)性事件的救援工作對(duì)于救援響應(yīng)時(shí)間和救援時(shí)間周期的緊迫性更加嚴(yán)格。然而城市區(qū)域內(nèi)復(fù)雜的路網(wǎng)和時(shí)變的路況對(duì)于救援車輛行駛速度有著明顯的影響。因此，為了確保城市發(fā)生各種突發(fā)事件后城市應(yīng)急救援中心能夠及時(shí)響應(yīng)、選擇最佳救援路線、實(shí)施高效救援，面向城市交通復(fù)雜路況下的應(yīng)急物資配送路徑尋優(yōu)已成為目前亟待解決的問(wèn)題［1-2］。

目前，國(guó)內(nèi)外學(xué)者就應(yīng)急救援物資配送路徑問(wèn)題作了大量研究。Dantzig等［3］于1959年提出車輛路徑問(wèn)題，并指出該問(wèn)題本質(zhì)上屬于運(yùn)籌學(xué)與組合優(yōu)化領(lǐng)域。Balcik等［4］針對(duì)災(zāi)害后不確定信息下的救援和物資配送進(jìn)行研究，以總成本最小為目標(biāo)，建立了從供應(yīng)點(diǎn)到資源需求點(diǎn)的多物品網(wǎng)絡(luò)流模型。Ceyhun［5］研究基于救援中心屬于覆蓋模型環(huán)境下的車輛路徑尋優(yōu)問(wèn)題，為使得每臺(tái)救援車輛能夠高效地服務(wù)更多的待救點(diǎn)，建立了一種多目標(biāo)車輛路徑尋優(yōu)模型。Pretolani［6］分析某城市路段行駛時(shí)間的結(jié)果分布規(guī)律，總結(jié)出該城市路段行駛時(shí)間呈正態(tài)分布，該結(jié)果對(duì)應(yīng)急救援車輛行駛速度的判定有著很大啟發(fā)作用。馬祖軍等［7-8］對(duì)洪災(zāi)地震等自然災(zāi)害和城市公共突發(fā)事件下的應(yīng)急救援中心的選址及車輛路徑尋優(yōu)問(wèn)題進(jìn)行研究，提出應(yīng)急物資配送中心定位與配送車輛路徑安排的聯(lián)合決策問(wèn)題，對(duì)此建立了模糊多目標(biāo)定位及路徑尋優(yōu)模型。喬茹等［9］基于改進(jìn)蟻群算法研究移動(dòng)機(jī)器人全局路徑規(guī)劃問(wèn)題。姜金貴等［10］針對(duì)城市內(nèi)澇突發(fā)情況下，引用連通系數(shù)和暢通系數(shù)來(lái)計(jì)算車行速度，從而反映出道路積水阻礙交通等影響因素，建立相應(yīng)的救援路徑尋優(yōu)模型，以提高救援效率降低災(zāi)害損失。在求解方法上，Purezza等［11］運(yùn)用禁忌搜索算法求解車輛優(yōu)化調(diào)度的問(wèn)題；Torki等［12］提出用自組織的神經(jīng)網(wǎng)絡(luò)算法來(lái)求解車輛路線優(yōu)化問(wèn)題；宋曉宇等［13］用遺傳算法求解了灰色規(guī)劃模型，通過(guò)測(cè)試種群數(shù)目、交叉率和變異率3種控制參數(shù)值以提高算法性能。

上述有關(guān)應(yīng)急救援車輛路徑尋優(yōu)研究中，僅僅采用1-0決策判斷方法處理道路是否能夠通行，而忽略了城市本身道路交通擁堵特征。其中采用的多目標(biāo)路徑尋優(yōu)模型在建立目標(biāo)函數(shù)時(shí)，大多是采用權(quán)重分配的方法處理時(shí)間最短和成本最低多目標(biāo)之間的關(guān)系，而該方法所得出的結(jié)果容易忽略應(yīng)急救援過(guò)程中的及時(shí)性，即使時(shí)間的權(quán)重比較大，也會(huì)出現(xiàn)結(jié)果偏向于所耗時(shí)間和成本較小的可能。在求解方法上基本采取智能啟發(fā)式算法，對(duì)于群體智能算法的應(yīng)用相對(duì)不夠成熟?；诖?，本文針對(duì)城市車輛行駛速度特征進(jìn)行分析，提出道路擁擠條件下的雙層路徑尋優(yōu)模型，并構(gòu)建混沌螢火蟲(chóng)算法進(jìn)行求解。

1　路徑尋優(yōu)模型

1.1問(wèn)題描述

傳統(tǒng)物流配送車輛路徑尋優(yōu)問(wèn)題，是在物流配送中心以及物資需求點(diǎn)坐標(biāo)位置、道路交通狀況、需求點(diǎn)物資需求量等因素已知的基礎(chǔ)上進(jìn)行的。而應(yīng)急救援車輛路徑規(guī)劃的過(guò)程中，救援需求點(diǎn)位置的隨機(jī)性、道路修復(fù)狀況、時(shí)變下的道路擁堵信息等不確定因素使得該情景下的車輛路徑尋優(yōu)問(wèn)題變得異常復(fù)雜。對(duì)應(yīng)急救援路徑選擇問(wèn)題的描述如下：選擇車輛行駛時(shí)間最短以及車輛運(yùn)輸成本最少作為目標(biāo)。系統(tǒng)中只有一個(gè)救援配送中心，且地理坐標(biāo)位置及所擁有的救援車型、數(shù)量、單車容量已知，救援中心派出車輛對(duì)多個(gè)待救點(diǎn)進(jìn)行服務(wù)，完成物資配送后返回救援中心。

車輛行駛過(guò)程中應(yīng)滿足以下幾個(gè)假設(shè)條件：

1）道路節(jié)點(diǎn)之間有可行通路；

2）每個(gè)待救點(diǎn)只能接受一輛車一次救援；

3）每輛車在一次救援巡回過(guò)程中的載重不能超過(guò)其最大容量；

4）車輛行駛速度小于等于其最大限制行駛速度。

以城市交通路網(wǎng)作為建立應(yīng)急救援車輛最優(yōu)路徑模型基礎(chǔ)，節(jié)點(diǎn)（待救點(diǎn)）與節(jié)點(diǎn)之間的路線設(shè)定為一條弧段。應(yīng)急救援車輛路徑問(wèn)題可以用圖論形式表示出來(lái)：記G（I,L）為賦權(quán)圖，I為頂點(diǎn)集，L為邊集，定義決策變量如下：

其中：i，j表示待救點(diǎn)序號(hào)，i，j=0，1，…，m；k代表派使的第k臺(tái)救援車輛，k=1，2，…，K；其中i，j=0，表示救援中心。式（1），（2）為決策變量，判斷救援車輛是否通過(guò)i和j節(jié)點(diǎn)，以及節(jié)點(diǎn)i是否被第k輛救援車所提供服務(wù)。

1.2數(shù)學(xué)模型

雙層路徑尋優(yōu)模型不同于以往的多目標(biāo)路徑尋優(yōu)模型［14］。多目標(biāo)模型一般是以車輛行駛路徑最短、成本最低、時(shí)間最短等作為目標(biāo)，并且諸多目標(biāo)之間以設(shè)定權(quán)值綜合考慮。而雙層路徑尋優(yōu)模型更加強(qiáng)調(diào)突發(fā)事件發(fā)生后對(duì)應(yīng)急物資配送的及時(shí)性，該模型以應(yīng)急救援物資配送車輛行駛總時(shí)間最短為主要優(yōu)化目標(biāo)，在充分體現(xiàn)及時(shí)性的基礎(chǔ)上再以車輛行駛所耗總成本最低為輔助目標(biāo)，從而使救援中心位置能夠及時(shí)服務(wù)于待救點(diǎn)傷員并且盡量降低救援車輛所耗成本。雙層路徑尋優(yōu)數(shù)學(xué)模型表達(dá)如下：

目標(biāo)函數(shù)：

其中：

約束條件：

其中：（x0，y0）表示救援中心位置；（xi，yi）表示待救點(diǎn)位置；di表示各待救點(diǎn)對(duì)該物資的需求量；D表示每輛救援車的最大容量；ck表示第k輛車，每行駛單位距離所消耗的成本；lij表示i與j之間距離；vij表示車輛行駛于i與j之間的速度；τij表示車輛行駛于i與j之間所耗時(shí)間；vˉ表示車輛的平均速度；vmax表示車輛的最大速度；qij表示i與j之間道路的暢通度；pij表示i與j之間道路的最大通行量。式（5）引入最大速度和平均速度，當(dāng)路徑暢通度與路容量以及平均速度的乘積小于最大速度時(shí)，則實(shí)際速度為三者之積；反之，速度則控制在最大速度，不允許超速；式（3），（4）分別為應(yīng)急物資配送車輛行駛時(shí)間和所耗成本優(yōu)化函數(shù)；式（7），（8）表示每個(gè)待救點(diǎn)均得到車輛救助，并且每個(gè)待救點(diǎn)只出現(xiàn)在一臺(tái)救援車輛的路徑上；式（9）保證每臺(tái)救援車輛歷經(jīng)的所有待救點(diǎn)的總需求量小于該車最大容量；式（10）～（12）保證每一臺(tái)車輛能夠形成可行回路。

2　算法設(shè)計(jì)

2.1混沌螢火蟲(chóng)算法思路

在標(biāo)準(zhǔn)螢火蟲(chóng)算法的基礎(chǔ)上引入慣性權(quán)重，使算法的全局搜索和局部尋優(yōu)能力得到一定改善。但是，實(shí)驗(yàn)發(fā)現(xiàn)，一旦達(dá)到局部極值點(diǎn)附近，算法收斂速率慢，且在極值點(diǎn)附近振蕩；對(duì)于一些多峰多極值點(diǎn)問(wèn)題，算法仍存在陷入局部最優(yōu)問(wèn)題?；煦邕\(yùn)動(dòng)具有遍歷性、隨機(jī)性等特點(diǎn)，為此，本文在螢火蟲(chóng)算法的基礎(chǔ)上引入混沌思想，從而提高螢火蟲(chóng)種群的多樣性和尋優(yōu)的遍歷性，增加算法擺脫陷入局部極值點(diǎn)的能力。改進(jìn)后的混沌螢火蟲(chóng)算法是利用載波的方式，將混沌變量映射到螢火蟲(chóng)優(yōu)化算法的搜索空間，再利用混沌變量進(jìn)行搜索尋優(yōu)［16］。搜索的過(guò)程分為2個(gè)階段。

1）粗略搜索

為提高算法收斂速度，在迭代運(yùn)算初期，利用基于慣性權(quán)重的螢火蟲(chóng)算法進(jìn)行大范圍全局搜索，尋找整個(gè)搜索空間中的滿意極值點(diǎn)。

2）細(xì)致搜索

選取粗略搜索法所得適應(yīng)度高的10%至20%螢火蟲(chóng)，結(jié)合混沌映射再進(jìn)行局部搜索，在粗略搜索的極值點(diǎn)附近尋找出全局下最優(yōu)解。

2.2混沌螢火蟲(chóng)算法求解步驟

改進(jìn)混沌螢火蟲(chóng)算法流程如下。

1）系統(tǒng)初始化，生成螢火蟲(chóng)初始種群的規(guī)模、位置信息（Xa（t）），設(shè)置光強(qiáng)吸收系數(shù)（γ）、最大吸引度（β0）和步長(zhǎng)因子（α）等參數(shù)。

2）計(jì)算群體中每個(gè)螢火蟲(chóng)的熒光亮度，

其中I0表示螢火蟲(chóng)的最大熒光亮度，即自身r=0處。

3）對(duì)所有螢火蟲(chóng)個(gè)體進(jìn)行鄰域搜索，此時(shí)的搜索半徑最大，并且計(jì)算出鄰域中所有候選螢火蟲(chóng)個(gè)體的吸引度，

4）根據(jù)式（15），（16）更新螢火蟲(chóng)位置，最亮的螢火蟲(chóng)個(gè)體隨機(jī)移動(dòng)，

其中：t表示迭代次數(shù)；tmax表示最大迭代次數(shù)；ω（t）表示慣性權(quán)重；ωmax,ωmin表示最大、最小權(quán)重。

5）在有限的迭代次數(shù)內(nèi)，通過(guò)以上步驟可以得出一組螢火蟲(chóng)亮度數(shù)據(jù)，從中選取螢火蟲(chóng)種群中適應(yīng)度高的20%個(gè)體，進(jìn)行混沌局部搜索。

6）將螢火蟲(chóng)位置信息Xbt按下式映射為0到1之間的混沌參量C（Xbt），

其中Xmax s和Xmin s分別為搜索空間中s維的上界和下界（假設(shè)螢火蟲(chóng)的位置空間為s維，當(dāng)s=1時(shí)，Xmaxs=Xmax，Xmins=Xmin）。

7）當(dāng)?shù)螖?shù)t=t+1時(shí)，根據(jù)式（17）計(jì)算得到下步迭代的混沌參量，并將混沌參量）按式（18）映射轉(zhuǎn)化為Xt+1b，

8）候選螢火蟲(chóng)個(gè)體適應(yīng)度值大于當(dāng)前螢火蟲(chóng)的適應(yīng)度值，則替換當(dāng)前螢火蟲(chóng)個(gè)體，實(shí)現(xiàn)螢火蟲(chóng)對(duì)較優(yōu)個(gè)體位置的移動(dòng)。

9）按下式收縮搜索區(qū)域

其中Xmaxlight.s表示當(dāng)前最亮螢火蟲(chóng)個(gè)體的第s維變量的值。

10）若混沌搜索已到預(yù)先設(shè)定的精度或迭代次數(shù)，則將新解作為算法的最終結(jié)果，否則令t=t+1并返回步驟6）。

3　算例

3.1算例背景

某城市道路車輛行駛速度一般在20 km/h左右，但是在高峰期時(shí)段內(nèi)，由于車流量過(guò)大導(dǎo)致車速受到嚴(yán)重影響。由該城市道路交通部門(mén)的車輛行駛監(jiān)控資料分析路網(wǎng)擁堵?tīng)顩r，道路暢通系數(shù)取值于0.5～1.0，道路交通容量取值范圍2～4，根據(jù)抽檢的車輛速度計(jì)算得該城市內(nèi)車輛行駛的最大速度為9.6 km/h、平均速度為3.6 km/h。另外，該城市大多數(shù)道路為東西和南北方向，為了方便理解在求解過(guò)程中直接取絕對(duì)值距離。

取應(yīng)急救援中心周圍長(zhǎng)寬均為10 km區(qū)域?yàn)檠芯糠秶O(shè)待救點(diǎn)的坐標(biāo)為（xi，yi），根據(jù)該城市歷史突發(fā)事件相關(guān)數(shù)據(jù)，救援中心（5，5）和待救點(diǎn)具體數(shù)據(jù)如表1所示。此外假設(shè)，應(yīng)急物資配送車輛最大的容量為10 t，車輛行駛1 km所耗成本為5元。

以該城市路網(wǎng)擁堵環(huán)境下的應(yīng)急物資配送問(wèn)題為研究對(duì)象，優(yōu)化目標(biāo)是在應(yīng)急物資配送車輛總行駛時(shí)間（T）可以接受的范圍內(nèi)（［Tmin，Tmin（1%+2%）］）使得車輛行駛成本最低。

表1　需求點(diǎn)坐標(biāo)及需求量Tab.1 Demand Point CoordinateAnd Demand

3.2算例求解

1）參數(shù)設(shè)定

在Matlab環(huán)境下建立相關(guān)數(shù)據(jù)庫(kù)，其中包括救援中心及待救點(diǎn)坐標(biāo)（xi，yi）、各待救點(diǎn)的物資需求量（di）、車輛數(shù)目（K）、車輛k行駛單位距離消耗成本（ck）、單車最大容量（D）、車輛平均速度）、最大速度（vmax）、待救點(diǎn)間距離（lij）。另外，隨機(jī)產(chǎn)生21×21組道路暢通系數(shù)和通行容量（pij，qij）。該案例涉及的救援中心及待救點(diǎn)地理分布如圖1所示。螢火蟲(chóng)算法求解參數(shù)設(shè)定為螢火蟲(chóng)數(shù)m=10，光強(qiáng)吸收系數(shù)γ= 1.0，最大吸引度 β0=1.0，步長(zhǎng)因子α=0.2，迭代次數(shù)tmax=200，ωmax=1，ωmin=0.4。

圖1　需求點(diǎn)分布Fig.1 Demand Point Distribution

2）初始路徑方案

根據(jù)最近鄰域法得出第一個(gè)車輛行駛路徑方案，共派出3輛應(yīng)急物資配送車輛，第1輛共載重為9.3 t，行駛22 km，路徑為0-2-3-4-5-20-7-6-0；第2輛共載重為9.0 t，行駛24.4 km，路徑為0-16-9-19-14-8-10-1-0；第3輛共載重為9.5 t，行駛38 km，路徑為0-15-12-13-11-17-18-0（簡(jiǎn)記①：0-2-3-4-5-20-7-6-0；0-16-9-19-14-8-10-1-0；0-15-12-13-11-17-18-0），如圖2所示。

圖2　初始車輛行駛路徑方案Fig.2 Initial Vehicle Routing Scheme

對(duì)第一個(gè)車輛行駛路徑方案進(jìn)行鄰域搜索，再產(chǎn)生9個(gè)初始方案，方法如下：

（a）同一車輛，將某2個(gè)待救點(diǎn)位置進(jìn)行互換，共3種方案。

每輛車歷經(jīng)的第2，4點(diǎn)交換；每輛車歷經(jīng)的第3，5點(diǎn)交換；每輛車歷經(jīng)的第4，7點(diǎn)交換。

（b）兩個(gè)車輛路線，各選取一個(gè)待救點(diǎn)位置進(jìn)行互換，共3種方案。

第1，2輛車所歷經(jīng)的第3點(diǎn)交換；第1，3輛車所歷經(jīng)的4點(diǎn)交換；第2，3輛車所歷經(jīng)的6點(diǎn)交換。

（c）兩個(gè)車輛路線，取前者當(dāng)中某個(gè)待救點(diǎn)，將其插入到后者車輛路徑當(dāng)中，共3種方案。

將第1輛車經(jīng)過(guò)的第2待救點(diǎn)，轉(zhuǎn)移到第2輛車經(jīng)過(guò)的第2待救點(diǎn)；將第1輛車經(jīng)過(guò)的第2待救點(diǎn)，轉(zhuǎn)移到第3輛車經(jīng)過(guò)的第2待救點(diǎn)；將第2輛車經(jīng)過(guò)的第5待救點(diǎn)，轉(zhuǎn)移到第3輛車經(jīng)過(guò)的第5待救點(diǎn)。

3）全局尋優(yōu)

將以上10個(gè)應(yīng)急物資配送車輛路徑方案及對(duì)應(yīng)的目標(biāo)函數(shù)值（由式（5），（6）計(jì)算得出）看作螢火蟲(chóng)初始種群，根據(jù)慣性權(quán)重螢火蟲(chóng)算法進(jìn)行求解得最優(yōu)的10個(gè)路徑方案及時(shí)間值。以①車輛行駛路徑方案為例，再次進(jìn)行鄰域搜索，比較當(dāng)前螢火蟲(chóng)亮度值和候選螢火蟲(chóng)亮度值，再根據(jù)位置更新公式實(shí)現(xiàn)螢火蟲(chóng)位置的優(yōu)化，經(jīng)過(guò)200次迭代，最終得出①方案對(duì)應(yīng)的最優(yōu)結(jié)果，記作①"，同樣方法，得到另外9個(gè)最優(yōu)方案。全局搜索環(huán)境下車輛耗時(shí)的尋優(yōu)結(jié)果如圖3所示。

圖3　全局搜索尋優(yōu)結(jié)果Fig.3 Global Search Optimization Results

4）混沌序列

從上述10個(gè)最優(yōu)方案當(dāng)中選取目標(biāo)值最小的前2個(gè)方案。路徑方案A（0-2-14-6-5-4-17-18-1-0；0-3-10-19-13-7-11-0；0-8-9-16-15-12-20-0），車輛總行駛時(shí)間為9.312 h，車輛總行駛距離為76.4 km，車輛總行駛所耗成本382元；路徑方案B（0-2-14-6-4-5-17-18-1-0；0-3-10-19-13-7-11-0；0-8-9-16-15-12-20-0），車輛總行駛時(shí)間為9.191 h，車輛總行駛距離為75.6 km，車輛總行駛所耗成本378元。

將以上兩個(gè)結(jié)果對(duì)應(yīng)的螢火蟲(chóng)位置信息，按照式（17）映射到0到1之間的混沌參量，其中解為1維空間（j=1），xmin代表路徑方案A（0-2-14-6-5-4-17-18-1-0；0-3-10-19-13-7-11-0；0-8-9-16-15-12-20-0）作為搜索空間下限，xmax代表路徑方案B（0-2-14-6-4-5-17-18-1-0；0-3-10-19-13-7-11-0；0-89-16-15-12-20-0）作為搜索空間上限。

5）局部尋優(yōu)

在局部尋優(yōu)過(guò)程中先不考慮救援中心，把路徑方案看作20進(jìn)制的一個(gè)數(shù)字（且每個(gè)位置上的數(shù)字不重復(fù)），由此可根據(jù)式（17）來(lái)實(shí)現(xiàn)方案A和方案B的［0，1］映射。需要注意的是，在搜索的過(guò)程中，會(huì)產(chǎn)生不可行解，對(duì)于不可行解點(diǎn)進(jìn)行“+1”處理，直至找到該數(shù)值的最近可行解，然后通過(guò)式（18）進(jìn)行循環(huán)比較擇優(yōu)，在限制的迭代次數(shù)內(nèi)得到最優(yōu)局部解點(diǎn)。局部搜索環(huán)境下車輛耗時(shí)的尋優(yōu)結(jié)果如圖4所示。

圖4　局部搜索尋優(yōu)結(jié)果Fig.4 Local Search Optimization Curve

3.3結(jié)果

通過(guò)先后對(duì)解集進(jìn)行全局搜索及局部尋優(yōu)，最后得到以車輛行駛時(shí)間最短為目標(biāo)的前三組最優(yōu)解，如表2所示。

表2　路徑尋優(yōu)方案Tab.2 Route Optimization Scheme

從上表可以看出車輛行駛路徑方案耗時(shí)最少為9.067 h，則救援時(shí)間可接受范圍是［9.067，9.248］（由［Tmin,Tmin（1%+2%）］計(jì)算得出）。以上3個(gè)方案的車輛行駛時(shí)間值均在可接受范圍以內(nèi)，則選取其中所耗成本最低的方案作為最優(yōu)方案，即方案2：共派出3輛救援車進(jìn)行應(yīng)急物資配送，總路線長(zhǎng)度為72.8 km，共耗時(shí)9.153 h，車輛行駛所耗成本為364元。3輛救援車的具體路徑分別為：0-14-6-2-4-5-17-18-1-0；0-3-10-19-13-11-7-0；0-8-9-16-15-12-20-0，如圖5所示。

為進(jìn)一步證明提出的兩階段式混沌螢火蟲(chóng)算法在求解過(guò)程與求解結(jié)果中的優(yōu)越性，文中禁忌搜索算法對(duì)相同的案例進(jìn)行求解，2種算法求解結(jié)果對(duì)比見(jiàn)表3。由表3可看出，本文給出的混沌螢火蟲(chóng)算法尋優(yōu)能力強(qiáng)、車輛行駛耗時(shí)更短，費(fèi)用更少。

圖5　車輛行駛路徑最優(yōu)方案Fig.5 Vehicle Travel Path Optimal Plan

表3　兩種算法結(jié)果對(duì)比Tab.3 Comparison Of TwoAlgorithms

4　結(jié)　語(yǔ)

本文主要分析了城市上下班高峰期環(huán)境下道路車流量和道路通行容量對(duì)應(yīng)急物資配送車輛行駛速度的影響。在模型求解過(guò)程中，通過(guò)介入慣性權(quán)重和混沌算法有效地平衡了螢火蟲(chóng)算法的全局搜索能力和局部尋優(yōu)能力。算例結(jié)果表明，在求解突發(fā)事件情境下應(yīng)急救援車輛路徑優(yōu)化問(wèn)題時(shí)，新模型及算法相對(duì)于就算法的求解結(jié)果更優(yōu)，以耗時(shí)和費(fèi)用為目標(biāo)函數(shù)時(shí)，總耗時(shí)更少，總費(fèi)用更少，所提出的路徑優(yōu)化模型及算法對(duì)于應(yīng)急救援工作的順利開(kāi)展有一定的指導(dǎo)性意義。

不足之處在于選擇車輛路徑時(shí)假設(shè)所有節(jié)點(diǎn)之間均可以通行，并且直接取絕對(duì)值距離作為節(jié)點(diǎn)間距離，而城市實(shí)際路網(wǎng)錯(cuò)綜復(fù)雜、各節(jié)點(diǎn)間的道路方向多種多樣，因此模擬出城市實(shí)際路網(wǎng)作為路徑尋優(yōu)的依據(jù)、計(jì)算出精準(zhǔn)的節(jié)點(diǎn)間距離是應(yīng)急救援車輛路徑尋優(yōu)的下一步研究重點(diǎn)。

［1］陳則輝，劉誠(chéng)，呂品，等.不確定環(huán)境下應(yīng)急物資配送問(wèn)題研究［J］.鐵道科學(xué)與工程學(xué)報(bào)，2014（5）：82-89.

［2］李創(chuàng).國(guó)內(nèi)外應(yīng)急物流研究綜述［J］.華東經(jīng)濟(jì)管理，2013，27（6）：160-165.

［3］DANTIZIG G，RAMSER J.The truck dispatching pmblem［J］.Management Science，1959，6：80-91.

［4］BALCIKB，BEAMONBM，SMILOWITZK.Lastmiledis-tributioninhumanitarianrelief［J］.JournalofIntelligentTransportation System，2008，12（2）：51-63.

［5］ARAZ C，SELIM H，OZKARAHAN I.A fuzzy multi-objective covering-based vehicle location model for emergency services［J］. Computers&Operations Research，2007，34（3）：705-726.

［6］PRETOLANI D.A directed hypergraph model for random time-dependent shortest path［J］.European Journal of Operational Research，2000，123（8）：315-342.

［7］馬祖軍，代穎，李雙琳.帶限制期的震后應(yīng)急物資配送模糊多目標(biāo)開(kāi)放式定位-路徑問(wèn)題［J］.系統(tǒng)管理學(xué)報(bào)，2014，23（5）：658-667.

［8］代穎，馬祖軍.應(yīng)急物流系統(tǒng)中的隨機(jī)定位-路徑問(wèn)題［J］.系統(tǒng)管理學(xué)報(bào)，2012，21（2）：212-217.

［9］喬茹，章小兵，趙光興.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃［J］.安徽工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2009，26（1）：77-80.

［10］姜金貴，張鵬飛.基于改進(jìn)蟻群算法的城市內(nèi)澇救援路徑優(yōu)化［J］.計(jì)算機(jī)應(yīng)用，2014，34（7）：2103-2106.

［11］PUREZA V M，F(xiàn)RANCA P M.Vehicle routing problems via tabu search metaheuritic［R］.Centre De Recherche Sur Les Transports Publication，1991.

［12］TORKIA，SOMHON S，ENKAWAT.Acompetitive neural network algorithm for solving vehicle routing problem［J］.Computers &Industrial Engineering，1997，33（3）：473-476.

［13］宋曉宇，劉鋒，常春光.面向應(yīng)急物資調(diào)度的一種灰色規(guī)劃模型［J］.計(jì)算機(jī)應(yīng)用研究，2010，27（4）：1259-1262.

［14］管小俊，王喜富，王翠華，等.基于競(jìng)爭(zhēng)的物流中心選址雙層規(guī)劃模型及算法研究［J］.武漢理工大學(xué)學(xué)報(bào)（交通科學(xué)與工程版），2009，33（5）：956-959.

［15］陳榮，李超群.基于ABC法和自適應(yīng)混合遺傳算法的倉(cāng)儲(chǔ)區(qū)域布局優(yōu)化策略［J］.安徽工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2011，28（2）：183-187.

［16］劉長(zhǎng)平，葉春明.具有混沌搜索策略的螢火蟲(chóng)優(yōu)化算法［J］.系統(tǒng)管理學(xué)報(bào)，2013，22（4）：538-543.

［17］湯金春，王培珍.基于遺傳算法的鋼錠配切優(yōu)化［J］.安徽工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，29（1）：67-69.

［18］郜振華，梅莉，祝遠(yuǎn)鑒.復(fù)合策略慣性權(quán)重的粒子群優(yōu)化算法［J］.計(jì)算機(jī)應(yīng)用，2012，32（8）：2216-2218.

責(zé)任編輯：丁吉海

Route Optimization of Emergency Material Distribution under Urban Emergency Situations

WANG Fuyu1，2，YE Chunming2，WANG Tao1
（1.School of management science and Engineering，Anhui University of Technology，Ma'anshan 243032，China；2.School of management，University of Shanghai for Science and Technology，Shanghai 200093，China）

Aiming at the take of the vehicle routing optimization of emergency material distribution in the urban emergency environment，the influence of urban road congestion on the speed of the vehicle was analyzed.Take the least time and cost of the vehicle as object，a routing optimization model of bi-level programming is built.To improve the global search and local search capability，an improved two stage firefly algorithm was employed to solve the problem.The numerical example shows that the proposed model and algorithm can effectively solve the problem of emergency material distribution in urban emergency.

emergency rescue；route optimization；two-level theory；firefly algorithm

TP391

Adoi：10.3969/j.issn.1671-7872.2016.02.016

1671-7872（2016）02-0177-08

2015-11-13

國(guó)家自然科學(xué)基金項(xiàng)目（71271138）；教育部人文社會(huì)科學(xué)青年基金項(xiàng)目（14YJC630119）；住建部軟科學(xué)研究項(xiàng)目（2015-R2-057）；安徽省高校人文社科研究重大項(xiàng)目（SK2014ZD016）

王付宇（1977-），男，河南泌陽(yáng)人，副教授，主要研究方向?yàn)橹悄軆?yōu)化、工業(yè)工程。