基于改進(jìn)ABC算法的城市內(nèi)澇應(yīng)急車(chē)輛路徑優(yōu)化

吳 凡, 許冰清, 楊 冰

(安徽工業(yè)大學(xué) 管理科學(xué)與工程學(xué)院，安徽 馬鞍山 243032)

隨著全球氣候變化和城市快速擴(kuò)張，近年來(lái)我國(guó)城市極端暴雨事件頻繁發(fā)生，據(jù)《中國(guó)水旱災(zāi)害公報(bào)》統(tǒng)計(jì)資料顯示，2006～2013年我國(guó)每年都有百座以上城市遭受內(nèi)澇災(zāi)害，造成了巨大的經(jīng)濟(jì)損失，已成為威脅城市安全運(yùn)行的主要問(wèn)題[1-2].短期大雨或暴雨超過(guò)城市排水系統(tǒng)承受能力，造成的城市內(nèi)澇災(zāi)害，已成為世界范圍內(nèi)城市地區(qū)的嚴(yán)重問(wèn)題[3-4]，相對(duì)于中小城市，特大型城市由于經(jīng)濟(jì)活動(dòng)比較集中，具有城市水文效應(yīng)明顯等特點(diǎn)，所以一旦發(fā)生突發(fā)暴雨事件，內(nèi)澇災(zāi)害應(yīng)對(duì)更加復(fù)雜、要求更高[5-6].當(dāng)前我國(guó)總體仍處于快速城市化、城市內(nèi)澇風(fēng)險(xiǎn)上升階段，亟須有效的應(yīng)急措施以提高應(yīng)對(duì)災(zāi)害的能力.

在城市內(nèi)澇災(zāi)害發(fā)生后，城市應(yīng)急管理機(jī)構(gòu)需要制定應(yīng)急救援工作將應(yīng)急物資第一時(shí)間送達(dá)災(zāi)區(qū)，而根據(jù)城市內(nèi)澇災(zāi)害特點(diǎn)，制定相應(yīng)的應(yīng)急物資調(diào)度計(jì)劃，科學(xué)合理地調(diào)配各種應(yīng)急車(chē)輛是應(yīng)急救援的重中之重[7-8].國(guó)內(nèi)外學(xué)者對(duì)應(yīng)急車(chē)輛調(diào)度已有大量的研究，其研究重點(diǎn)各有側(cè)重，宋英華等[9]在地震應(yīng)急救援中考慮了駕駛員心理成本，并采用加權(quán)遺傳算法求解最小時(shí)間懲罰成本和駕駛員心理成本的雙目標(biāo)應(yīng)急物資車(chē)輛路徑規(guī)劃模型.梅超等[10]以事件為中心建立洪澇預(yù)警調(diào)度系統(tǒng)，以對(duì)汛情監(jiān)視、風(fēng)險(xiǎn)分析，實(shí)現(xiàn)對(duì)城市洪澇過(guò)程的調(diào)度模擬，為預(yù)警調(diào)度決策提供支撐.Chen等[11]建立了多層隨機(jī)網(wǎng)絡(luò)對(duì)城市內(nèi)澇風(fēng)險(xiǎn)要素之間的耦合關(guān)系進(jìn)行數(shù)學(xué)描述，并利用系統(tǒng)動(dòng)力學(xué)分析了城市內(nèi)澇災(zāi)害的成因.He等[12]基于疫情的擴(kuò)散特性，對(duì)每個(gè)區(qū)域的醫(yī)療需求進(jìn)行預(yù)測(cè)，然后應(yīng)用線性規(guī)劃方法來(lái)促進(jìn)分配決策，但其研究?jī)H針對(duì)單品種醫(yī)療物資分配問(wèn)題.叢雯婧等[13]針對(duì)應(yīng)急物資儲(chǔ)備庫(kù)選址問(wèn)題，考慮了設(shè)施的應(yīng)急效率、風(fēng)險(xiǎn)以及經(jīng)濟(jì)性，建立了選址多目標(biāo)優(yōu)化模型，利用多目標(biāo)遺傳算法進(jìn)行求解，其研究方法與結(jié)論對(duì)臺(tái)風(fēng)災(zāi)害下的應(yīng)急設(shè)施選址有一定啟示.黃茹月等[8]采用非線性整數(shù)規(guī)劃模型構(gòu)建了城市內(nèi)澇災(zāi)害應(yīng)急調(diào)度模型進(jìn)行應(yīng)急調(diào)度，實(shí)現(xiàn)城市內(nèi)澇災(zāi)害應(yīng)急調(diào)度的優(yōu)化，但在模型中未考慮道路通行能力問(wèn)題.Garza-Reyes等[14]基于精益思想和約束理論，以提高緊急醫(yī)療服務(wù)效率，但該研究沒(méi)有考慮突發(fā)事件的情景.陳湉等[15]假設(shè)受災(zāi)點(diǎn)物資需求量服從正態(tài)分布，考慮到災(zāi)區(qū)對(duì)服務(wù)時(shí)間的要求和車(chē)輛承載能力的限制等條件，以物資分配不足或過(guò)量所帶來(lái)的損失及車(chē)輛調(diào)度成本最小化為目標(biāo)，構(gòu)建了緊急需求條件下調(diào)度問(wèn)題的優(yōu)化模型，并采用離散蜂群算法求解調(diào)度問(wèn)題的優(yōu)化模型.

綜上所述，目前突發(fā)事件應(yīng)急調(diào)度研究普遍以地震、疫情等突發(fā)事件為研究對(duì)象，較少對(duì)頻繁發(fā)生的城市內(nèi)澇突發(fā)事件研究，且對(duì)城市內(nèi)澇的研究多從內(nèi)澇成因、風(fēng)險(xiǎn)評(píng)估、預(yù)警監(jiān)測(cè)和政策管理等方面探討，對(duì)于在城市暴雨和內(nèi)澇后的被淹道路上開(kāi)展救災(zāi)物資運(yùn)送的研究卻很少.由于內(nèi)澇應(yīng)急調(diào)度問(wèn)題是一種典型的NP-hard問(wèn)題，目前多采用群智能優(yōu)化算法進(jìn)行求解優(yōu)化.相較于其他群智能優(yōu)化算法參數(shù)多、結(jié)構(gòu)復(fù)雜的缺點(diǎn)，人工蜂群算法具有參數(shù)少、編碼簡(jiǎn)單、尋優(yōu)能力強(qiáng)等優(yōu)點(diǎn).因此，本文針對(duì)災(zāi)后應(yīng)急物資配送問(wèn)題，考慮道路暢通性、危險(xiǎn)系數(shù)及車(chē)輛載重等約束，建立了一類(lèi)帶軟時(shí)間窗約束的多目標(biāo)優(yōu)化模型，利用改進(jìn)的人工蜂群算法對(duì)隨機(jī)生成的算例進(jìn)行求解，并通過(guò)與基本人工蜂群算法的對(duì)比，驗(yàn)證了改進(jìn)策略的有效性.本文研究具有一定的理論和現(xiàn)實(shí)意義，可以為城市內(nèi)澇應(yīng)急決策方案提供依據(jù).

1 應(yīng)急車(chē)輛路徑問(wèn)題建模

1.1 問(wèn)題描述與假設(shè)

當(dāng)城市內(nèi)澇災(zāi)害發(fā)生后，為減小突發(fā)事件帶來(lái)的傷害，應(yīng)盡快將應(yīng)急物資運(yùn)送到受災(zāi)地區(qū).因此，如何合理規(guī)劃配送車(chē)輛運(yùn)輸路線，使應(yīng)急物資能夠高效、安全地運(yùn)輸?shù)绞転?zāi)地區(qū)，保證物資及時(shí)合理的分配，已成為城市內(nèi)澇災(zāi)害應(yīng)急救援工作亟待解決的關(guān)鍵問(wèn)題.問(wèn)題描述如下：有一個(gè)位置已知且應(yīng)急物資配送車(chē)輛充足的應(yīng)急救援中心，在城市內(nèi)澇發(fā)生之后，需要盡快向?yàn)?zāi)區(qū)提供所需的兩類(lèi)應(yīng)急物資(①食品物資：如礦泉水和面包等；②防汛物資：如救生船、救生圈、救生衣等.)從應(yīng)急物流配送中心送達(dá)到位置與需求量己知的各個(gè)應(yīng)急需求點(diǎn)，每一個(gè)應(yīng)急需求點(diǎn)都只能由一輛車(chē)服務(wù)一次，且各物資需求點(diǎn)有相應(yīng)的軟時(shí)間窗約束，以保證災(zāi)民能夠得到及時(shí)的救援.為便于分析和研究，做出以下假設(shè)：

1) 配送中心為位置己知的單一配送中心，且有兩種運(yùn)輸方式；

2)每個(gè)需求點(diǎn)的需求量不會(huì)大于配送車(chē)輛的最大載重量；

3) 配送車(chē)輛在完成各自任務(wù)后均返回配送中心；

4) 配送中心的應(yīng)急物資儲(chǔ)備量能夠滿(mǎn)足所有應(yīng)急點(diǎn)的需求；

5)車(chē)輛行駛速度與車(chē)輛進(jìn)入路段的暢通系數(shù)相關(guān).

1.2 模型構(gòu)建

對(duì)所建模型的變量、集合以及決策變量的定義如下：

N：客戶(hù)集合，N={0,1,2,…,n}，0為配送中心，其余節(jié)點(diǎn)表示客戶(hù)

Km：車(chē)型m的數(shù)量，m={1,2,…,M}

Qm：車(chē)型m的載重量，m={1,2,…,M}

dij：從節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離，i,j∈N

eij：從節(jié)點(diǎn)i到節(jié)點(diǎn)j的危險(xiǎn)系數(shù)，i,j∈N

LTi：節(jié)點(diǎn)i最晚服務(wù)時(shí)間，i∈N

Pi：節(jié)點(diǎn)i的需求緊迫度，i∈N

wh：h類(lèi)物資的需求等級(jí)，h={1,2,…,H}

Vm：車(chē)型m的行駛速度，m={1,2,…,M}

aij：節(jié)點(diǎn)i與j的線路連通性，i,j∈N

bij：節(jié)點(diǎn)間線路暢通性受內(nèi)澇積水影響程度，i,j∈N

本文建立的多目標(biāo)應(yīng)急物資調(diào)度模型描述如下：

(1)

(2)

(3)

約束條件：

(4)

(5)

(6)

(7)

(8)

(9)

(10)

其中：式(1)、(2)和(3)為目標(biāo)函數(shù)：式(1)為行駛總距離最短；式(2)為懲罰成本最小(與節(jié)點(diǎn)i的需求緊迫度和對(duì)物資的需求等級(jí)有關(guān))；式(3)為風(fēng)險(xiǎn)成本最低(車(chē)輛在行駛過(guò)程中出現(xiàn)事故的成本).式(4)～(6)表示每個(gè)客戶(hù)都被訪問(wèn)且僅被一輛車(chē)訪問(wèn)；式(7)表示每輛車(chē)的裝載容量限制，式(8)配送車(chē)到達(dá)需求點(diǎn)i與j的關(guān)系，式(9)配送車(chē)經(jīng)過(guò)路段ij的時(shí)間等于該路段的距離除以速度與暢通系數(shù)的乘積，式(10)為決策變量.

本文研究的問(wèn)題是調(diào)度總距離、懲罰成本和危險(xiǎn)成本同時(shí)最小化的多目標(biāo)優(yōu)化問(wèn)題，一般多目標(biāo)問(wèn)題常采用線性加權(quán)法轉(zhuǎn)化為單目標(biāo)問(wèn)題，故本文通過(guò)線性加權(quán)法對(duì)每個(gè)目標(biāo)進(jìn)行合理分配權(quán)重將其轉(zhuǎn)化為單目標(biāo)問(wèn)題，轉(zhuǎn)化后的單目標(biāo)函數(shù)為：

minC=ω1β1C1+ω2β2C2+ω3β3C3

(11)

其中：ω1、ω2和ω3為對(duì)應(yīng)目標(biāo)權(quán)重，由于各目標(biāo)之間的量綱不同，因此引入系數(shù)β1、β2和β3使三者統(tǒng)一量綱.

2 改進(jìn)人工蜂群算法

人工蜂群算法具有良好的求極值能力、魯棒性強(qiáng)、易實(shí)現(xiàn)等優(yōu)點(diǎn)，但在面對(duì)復(fù)雜且規(guī)模較大的實(shí)際工程問(wèn)題優(yōu)化時(shí)，由于蜂群的聚集性，蜂群算法的優(yōu)化性能則隨之降低，出現(xiàn)陷入局部極值過(guò)早收斂等問(wèn)題.本文針對(duì)該算法的局部搜索和全局搜索能力的不足，提出一種改進(jìn)方案，即利用自適應(yīng)維度更新策略改進(jìn)采蜜蜂和觀察蜂搜索方式，并對(duì)其引入全局搜索策略，而針對(duì)偵察蜂的生成方式利用混沌序列對(duì)其個(gè)體進(jìn)行混沌擾動(dòng).

2.1 初始化種群

隨機(jī)產(chǎn)生一個(gè)種群規(guī)模為D的初始種群，具體過(guò)程如下：首先隨機(jī)打亂一組為{1,2,…,N}序列的順序生成1×n維矩陣，矩陣中的元素即為受災(zāi)點(diǎn)的序號(hào).然后將序列中的第一個(gè)編號(hào)試分配給配送車(chē)輛，并判斷車(chē)輛容量約束條件.若不超載，則將此受災(zāi)點(diǎn)的需求任務(wù)分配給這輛車(chē)；若超載，則在該位置插入0點(diǎn)(供應(yīng)點(diǎn)序號(hào)).以此類(lèi)推，直至所有受災(zāi)點(diǎn)需求任務(wù)分配完成，最后生成一條滿(mǎn)足約束條件的路徑.例如，生成一組為：{6,4,8,2,9,5,1,10,3,7}的序號(hào)；其對(duì)應(yīng)點(diǎn)需求量為20，35，15，40，55，30，25，20，30，45；車(chē)輛的最大荷載為100.根據(jù)容量約束條件，則生成一條為：{0,6,4,8,0,2,9,0,5,10,0,3,7,0}的完整路徑.

2.2 自適應(yīng)維度更新策略

在基本的人工蜂群算法中，采蜜蜂和觀察蜂的鄰域搜索是隨機(jī)選擇蜜源位置其中一個(gè)維度，并通過(guò)單一的搜索方程改變?cè)摼S度的值來(lái)實(shí)現(xiàn)的.但這種每次隨機(jī)選取一個(gè)維度進(jìn)行鄰域搜索的更新方式，在面對(duì)高維問(wèn)題時(shí)會(huì)使算法求解效率顯著下降，出現(xiàn)收斂速度降低及陷入局部最優(yōu)解等不足.因此，本文在基本的人工蜂群算法基礎(chǔ)上設(shè)計(jì)了自適應(yīng)維度更新策略進(jìn)行改進(jìn)，以提高收斂速度，找到問(wèn)題更優(yōu)解.其改進(jìn)后的更新公式如下：

newXi,m=Xi,m+rand()(Xi,m-Xk,m)

(12)

(13)

其中：m為更新的維度數(shù)，dim為解向量的維度，t為當(dāng)前迭代次數(shù)，Tmax為最大迭代次數(shù).

利用式(12)在搜索過(guò)程中可自適應(yīng)選擇更新維度，以避免在迭代過(guò)程中所選更新維度過(guò)多，導(dǎo)致算法局部搜索能力不足；或所選更新維度數(shù)過(guò)少，使算法探索能力下降.即在算法前期，賦予m較大的值，采取多維更新，這樣可以增加算法的全局搜索能力，在全局范圍內(nèi)探索到較好的區(qū)域；隨著搜索的進(jìn)行，m呈逐漸遞減的趨勢(shì)，在算法后期，以較小的m值選取更新維度數(shù)，則可以保證蜂群在蜜源極值點(diǎn)進(jìn)行精細(xì)搜索，從而使算法向全局最優(yōu)解的位置收斂，以提高算法收斂精度.

2.3 全局搜索策略

無(wú)論是基本人工蜂群算法還是改進(jìn)后的ABC算法，在進(jìn)行迭代搜索過(guò)程中，依舊是采用比較單一的搜索方式對(duì)食物源進(jìn)行更新.為避免算法單一搜索模式的局限性，通過(guò)增加種群多樣性，以增強(qiáng)算法的全局搜索能力.因此，本文開(kāi)發(fā)了一種全局異維交叉搜索策略，并以一定概率執(zhí)行.搜索方式如下：

(14)

其中：xGlobal為全局最優(yōu)解向量，β∈[-1,1]，r1≠r2且r1，r2∈[1,2,…,N]，cr為進(jìn)行全局搜索策略的概率.

其步驟為：在采蜜蜂或偵察蜂更新之后，首先利用rand生成一個(gè)隨機(jī)值，若rand

2.4 混沌搜索策略

基本人工蜂群算法中，若采蜜蜂或觀察蜂經(jīng)過(guò)有限次搜索仍得不到改善，則轉(zhuǎn)化為偵察蜂.偵察蜂采用隨機(jī)初始化的方式，產(chǎn)生一個(gè)新的蜜源位置.為改進(jìn)這種搜索方式的盲目性、隨機(jī)性，難以使其在更新迭代中搜索到更優(yōu)解的缺點(diǎn)，提出一種混沌搜索策略.

混沌是自然界非線性系統(tǒng)中普遍存在的一種運(yùn)動(dòng)現(xiàn)象，是一種看似混亂，但實(shí)際是具有一定規(guī)律的運(yùn)動(dòng)，具有很好的遍歷性.利用混沌變量的遍歷性，進(jìn)行優(yōu)化搜索會(huì)比盲目無(wú)序的隨機(jī)搜索更具有優(yōu)越性，是一種幫助算法跳出局部最優(yōu)解效果很好的搜索機(jī)制.產(chǎn)成混沌序列的映射模型很多，其中Tent混沌序列具有偽隨機(jī)特性、遍歷性和非周期性等特點(diǎn)，能保證算法解的均勻性和多樣性，故本文采用Tent混沌序列對(duì)偵察蜂進(jìn)行初始化，Tent映射的數(shù)學(xué)表達(dá)式為：

(15)

其中：Xn是混沌序列X的第n維變量，xn是一個(gè)服從均勻分布的隨機(jī)數(shù)，xn∈[0,1].

混沌搜索的步驟如下：

1)隨機(jī)產(chǎn)生一組混沌變量xn，按照式(15)進(jìn)行映射.

2)將映射后產(chǎn)生的新變量Xn，按照式(16)映射回原問(wèn)題的解空間

newXn=Xmin+(Xmax-Xmin)Xnn=1,2,…,N

(16)

其中：Xmax和Xmin分別為原問(wèn)題解變量的最大值和最小值.

3)按照式(17)對(duì)解向量進(jìn)行混沌擾動(dòng)

newX′=(X′+newX)/2

(17)

其中：X′為原問(wèn)題需要進(jìn)行混沌擾動(dòng)的解向量，newX為新產(chǎn)生的混沌序列，newX′為混沌擾動(dòng)后新的解向量.

改進(jìn)后算法的流程如圖1.

圖1 IABC流程圖Figure 1 IABC flow chart

3 算例分析

3.1 模型參數(shù)

為驗(yàn)證所構(gòu)建模型和提出的算法的有效性，本文設(shè)計(jì)一組算例描述如下：某城市突發(fā)內(nèi)澇災(zāi)害，共有45個(gè)受災(zāi)點(diǎn)，該地區(qū)擁有1個(gè)救援中心.各節(jié)點(diǎn)之間的暢通系數(shù)為[0,1]之間的實(shí)數(shù)，受災(zāi)點(diǎn)與救援中心的連通系數(shù)為aij(∈{0,1}).由于洪澇災(zāi)害的特殊性，配送方式根據(jù)道路連通性選擇，若受災(zāi)點(diǎn)與救援中心點(diǎn)連通系數(shù)為0，則采用救援艇進(jìn)行配送；否則采用汽車(chē)進(jìn)行物資配送.其中汽車(chē)平均行駛速度為50 km/h，最大荷載量為1 100 kg；救援艇平均行駛速度30 km/h，最大荷載量為900 kg，實(shí)際行駛速度受節(jié)點(diǎn)間的暢通系數(shù)影響；車(chē)輛延遲到達(dá)服務(wù)點(diǎn)的懲罰單價(jià)為1 500 元/h；各類(lèi)物資延誤成本分別為w1=10 元/kg，w2=8 元/kg.

3.2 算例結(jié)果分析

使用Matlab對(duì)算例進(jìn)行仿真實(shí)驗(yàn)，算法參數(shù)如下：最大迭代次數(shù)iterate=1 000，蜜蜂總數(shù)N=200，最大限制搜索次數(shù)limit=20，全局搜索概率cr=0.6.由于城市內(nèi)澇災(zāi)害應(yīng)急車(chē)輛調(diào)度問(wèn)題的特殊性，本文將各子目標(biāo)權(quán)重系數(shù)設(shè)置為ω1=0.2,ω2=0.4,ω3=0.4.兩種算法同時(shí)運(yùn)行的迭代曲線如圖2所示.對(duì)比圖2中算法的收斂結(jié)果可以看出，改進(jìn)的ABC算法最終結(jié)果明顯優(yōu)于ABC算法.從迭代曲線的變化趨勢(shì)對(duì)比分析，在迭代初期ABC算法出現(xiàn)陷入局部最優(yōu)解的情況，并在迭代后期仍有小范圍的波動(dòng)；而改進(jìn)的ABC算法在200次左右便收斂，收斂速度較快且收斂結(jié)果更好.

圖2 兩種算法迭代曲線Figure 2 Iterative curves of two algorithms

本次仿真結(jié)果中兩種算法的調(diào)度方案及總成本如表1所示.其中ABC算法和IABC算法的總成本分別為12 553.40元、11 535.28元.對(duì)比結(jié)果可以看出，改進(jìn)ABC算法調(diào)度總成本較于ABC算法節(jié)省1 018.12元，降低了8%.

表1 兩種算法運(yùn)行結(jié)果

由于算法仿真結(jié)果具有一定的隨機(jī)性，為進(jìn)一步驗(yàn)證算法的性能，分別將兩種算法各運(yùn)行10次，其調(diào)度總成本結(jié)果如表2.

表2 兩種算法運(yùn)行10次結(jié)果

將兩種算法10次運(yùn)行結(jié)果如圖3所示.

對(duì)比表2中的結(jié)果可以看出，改進(jìn)ABC算法的調(diào)度方案均優(yōu)于ABC算法.通過(guò)圖3可以看出ABC算法的結(jié)果變化幅度較大，IABC算法的結(jié)果變化幅度比較平緩；對(duì)比兩種算法結(jié)果的極值可以看出，ABC算法的極差為1 719.32，IABC算法的極差為6 14.49，二者相差1 104.83，占總成本的9.6%.基于這些數(shù)值，可以看出改進(jìn)后的人工蜂群算法具有較強(qiáng)且穩(wěn)定的全局尋優(yōu)能力.

圖3 兩種算法運(yùn)行10次結(jié)果對(duì)比圖Figure 3 Comparison of the results of the two algorithms running for 10 times

綜上所述，本文提出的自適應(yīng)維度更新策略，前期更新維度較大，擴(kuò)大搜索范圍，提高了全局尋優(yōu)能力，在迭代后期更新維度漸小，以快速收斂于最優(yōu)解.

4 結(jié) 語(yǔ)

本文首先對(duì)城市應(yīng)急調(diào)度進(jìn)行分析，然后根據(jù)城市內(nèi)澇的特殊性與路面積水程度，引入連通系數(shù)和暢通系數(shù)，對(duì)配送方式進(jìn)行分類(lèi)及道路通行速度修正，構(gòu)建了車(chē)輛調(diào)度成本和風(fēng)險(xiǎn)及時(shí)間窗引起的懲罰最小化的一種多目標(biāo)規(guī)劃模型，最后提出一種自適應(yīng)維度更新人工蜂群算法對(duì)模型進(jìn)行優(yōu)化求解，并與改進(jìn)前的人工蜂群算法進(jìn)行對(duì)比，得到更優(yōu)的調(diào)度方案，在一定程度上克服了基本人工蜂群算法在解決高維問(wèn)題時(shí)尋優(yōu)能力差，易陷入局部最優(yōu)等問(wèn)題，驗(yàn)證了改進(jìn)算法的有效性.

突發(fā)事件發(fā)生后，單一的配送中心可能無(wú)法滿(mǎn)足物資需求對(duì)于時(shí)間的緊迫性，未來(lái)研究可以進(jìn)一步考慮建立多應(yīng)急資源配送中心的車(chē)輛調(diào)度模型，并采用更加合理有效的方法求解多目標(biāo)優(yōu)化問(wèn)題.