于明亮, 劉 帥, 浦東平

（1.上海理工大學(xué) 公共實(shí)驗(yàn)中心，上海 200093；2.上海師范大學(xué) 信息與機(jī)電工程學(xué)院，上海 200234）

應(yīng)急物資作為突發(fā)事件防控的重要保障，其配送的合理性和送達(dá)的及時(shí)性不僅關(guān)系著民眾的生命安全和生活保障，而且影響著地區(qū)的經(jīng)濟(jì)發(fā)展和社會(huì)穩(wěn)定。而實(shí)現(xiàn)有效應(yīng)急物流配送的前提是需要準(zhǔn)確預(yù)測(cè)災(zāi)區(qū)的物資需求，且該需求數(shù)量與受影響人數(shù)密切相關(guān)。在當(dāng)前這個(gè)移動(dòng)互聯(lián)技術(shù)高速發(fā)展的時(shí)代，突發(fā)事件的影響范圍不再僅由自然因素、環(huán)境因素和經(jīng)濟(jì)因素等決定，個(gè)體間的信息傳播也在一定程度上影響著突發(fā)事件的發(fā)展態(tài)勢(shì)。因此，為了更加準(zhǔn)確地預(yù)測(cè)應(yīng)急物資需求且更加合理地設(shè)計(jì)車(chē)輛配送方案，在構(gòu)建應(yīng)急物流優(yōu)化模型時(shí)應(yīng)該加以考慮災(zāi)情傳播和信息傳播之間的關(guān)聯(lián)。

目前關(guān)于應(yīng)急物流的研究一方面集中在應(yīng)急物流網(wǎng)絡(luò)設(shè)計(jì)[1-3]，如劉明等[4]綜合考慮了人口流動(dòng)和密度特征，設(shè)計(jì)了基于服務(wù)水平的應(yīng)急物流網(wǎng)絡(luò)優(yōu)化模型，反映了物資需求和救援成本之間的偏好側(cè)重。蔣杰輝等[5]設(shè)計(jì)了基于Holling-II 函數(shù)的SIP（susceptible，infecteive，protester）疾病擴(kuò)散模型，結(jié)合智能水滴算法對(duì)以時(shí)間短和成本低為目標(biāo)的應(yīng)急物流問(wèn)題進(jìn)行研究。鄧燁等[6]針對(duì)可靠度、滿意度、經(jīng)濟(jì)度及魯棒度等多種要求解決了不確定環(huán)境下的應(yīng)急物資車(chē)輛的路徑優(yōu)化問(wèn)題。另一方面，國(guó)內(nèi)外學(xué)者也重點(diǎn)關(guān)注于應(yīng)急物資動(dòng)態(tài)分配[7-9]，如Büyüktahtakin 等[10]同時(shí)考慮了傳染病的空間傳播和后勤問(wèn)題，設(shè)計(jì)了一種物流混合整數(shù)規(guī)劃模型來(lái)確定物資分配的最佳數(shù)量、時(shí)間和位置。Dasaklis 等[11]基于反應(yīng)行動(dòng)延遲和反應(yīng)能力有限等現(xiàn)實(shí)情況采用線性規(guī)劃模型制定了大規(guī)模疫苗接種活動(dòng)所需的物資分配方案。王妍妍等[12]通過(guò)區(qū)間數(shù)、三角模糊數(shù)及延遲系數(shù)等反映應(yīng)急物資供給與需求關(guān)系之間的非確定性，并在最大程度上衡量延遲時(shí)間與系統(tǒng)損失來(lái)制定出多周期的應(yīng)急物資分配方案。通過(guò)對(duì)現(xiàn)有文獻(xiàn)進(jìn)行分析可以發(fā)現(xiàn)，絕大部分的研究都忽略了信息傳播對(duì)于應(yīng)急物資需求和分配的影響。

本文研究的應(yīng)急物流問(wèn)題本質(zhì)上可以轉(zhuǎn)化為多目標(biāo)下的路徑優(yōu)化問(wèn)題，與其他求解多目標(biāo)優(yōu)化問(wèn)題的智能算法所不同的是，人工蜂群算法（artificial bee colony algorithm，ABC）的設(shè)計(jì)思路是模仿蜂群尋蜜的過(guò)程[13]，這種通過(guò)劃分多種群進(jìn)行并行尋優(yōu)的方法更加貼近物資配送的車(chē)輛路徑優(yōu)化過(guò)程[14]。在人工蜂群算法被提出之初，其主要被應(yīng)用在解決具有連續(xù)性的優(yōu)化問(wèn)題中，而近年來(lái)也逐步被應(yīng)用于包括路徑規(guī)劃問(wèn)題在內(nèi)的離散問(wèn)題求解中[15]。如張架鵬等[16]運(yùn)用差分進(jìn)化算法和模擬退火算法的思想設(shè)計(jì)了一種改進(jìn)的離散型蜂群算法，并將其應(yīng)用在求解同類(lèi)機(jī)調(diào)度問(wèn)題中。Li 等[17]將改進(jìn)的離散人工蜂群算法應(yīng)用于具有維修活動(dòng)的多目標(biāo)柔性作業(yè)車(chē)間調(diào)度問(wèn)題中，與傳統(tǒng)人工蜂群算法所不同的是，其所提出的算法能夠生成具有多樣性的初始種群并能給出唯一解。

目前將人工蜂群算法與路徑優(yōu)化問(wèn)題相結(jié)合的研究仍處于初始階段。如Pamu?ar 等[18]將自適應(yīng)模糊神經(jīng)網(wǎng)絡(luò)與人工蜂群算法相結(jié)合來(lái)求解多目標(biāo)危險(xiǎn)品運(yùn)輸?shù)某鞘新肪€規(guī)劃問(wèn)題，從而有效降低了成本和風(fēng)險(xiǎn)。段淵等[19]提出了新的離散型蜂群算法來(lái)解決經(jīng)典的旅行商問(wèn)題，通過(guò)離散的交叉算子和單/多步2-opt 算子來(lái)確定新的蜜源。鄭健等[20]引入了精英保護(hù)策略和動(dòng)態(tài)偵察蜂機(jī)制對(duì)傳統(tǒng)人工蜂群算法進(jìn)行了優(yōu)化，并將該算法用于解決基于方向標(biāo)志的離散型路徑規(guī)劃問(wèn)題。

在已有研究的基礎(chǔ)上，本文首先建立了一個(gè)基于SIS-UAU 雙層擴(kuò)散網(wǎng)絡(luò)的預(yù)測(cè)模型用以得出各個(gè)災(zāi)區(qū)的應(yīng)急物資需求量。其次針對(duì)多目標(biāo)下的應(yīng)急物流問(wèn)題設(shè)計(jì)了一種新的離散人工蜂群算法（進(jìn)化蜂群算法）。該算法通過(guò)有效利用適應(yīng)度值、歷史進(jìn)化程度、交叉算子及變異算子等操作來(lái)保障迭代效率和避免陷入局部最優(yōu)。最后通過(guò)一個(gè)應(yīng)急物資配送算例，表明了本文所提出的需求預(yù)測(cè)模型和改進(jìn)離散算法的有效性，并在綜合考慮時(shí)間短和成本低的前提下得到了最佳應(yīng)急物資配送路線。本文相較于其他應(yīng)急物流和蜂群算法的研究主要有以下3 個(gè)方面的不同：第一，結(jié)合雙層擴(kuò)散網(wǎng)絡(luò)著重考慮了實(shí)際中信息傳播和個(gè)人行為的影響因素，從而能更加準(zhǔn)確預(yù)測(cè)災(zāi)區(qū)應(yīng)急物資的需求量。第二，進(jìn)化蜂群算法加入了交叉算子和變異算子，實(shí)現(xiàn)了對(duì)優(yōu)秀信息的保留和傳遞，加速了蜜源向最優(yōu)解的進(jìn)化。第三，進(jìn)化蜂群算法綜合考慮了蜜源的適應(yīng)度值和歷史進(jìn)化程度，并基于此將蜂群進(jìn)行重新劃分，從而充分挖掘了蜂群價(jià)值并顯著優(yōu)化了計(jì)算效果。

1 應(yīng)急物流問(wèn)題的描述和模型

1.1 基于雙層擴(kuò)散網(wǎng)絡(luò)的需求預(yù)測(cè)模型

在分析災(zāi)情擴(kuò)散時(shí)不僅考慮了突發(fā)事件對(duì)于個(gè)體的影響程度，而且考慮了通過(guò)預(yù)警信息傳播能夠使人們獲取災(zāi)情相關(guān)信息并降低影響程度，從而建立了基于信息傳播和個(gè)體行為的雙層擴(kuò)散網(wǎng)絡(luò)。

雙層擴(kuò)散網(wǎng)絡(luò)中的上層為事件層，采用susceptible-infected-susceptible（SIS）傳染病模型來(lái)表示[21]。在SIS 模型中，個(gè)體分別處于易感染（susceptible，簡(jiǎn)稱(chēng)S）和感染（infected，簡(jiǎn)稱(chēng)I）兩種狀態(tài)。針對(duì)本文的突發(fā)事件情況，在災(zāi)情發(fā)生前所有個(gè)體都處于不受影響的狀態(tài)，則無(wú)影響者可用SIS 模型中的S 表示；而在災(zāi)情發(fā)生后部分個(gè)體受到了影響，則受影響者可用SIS 模型中的I 表示。隨著災(zāi)情的恢復(fù)，受影響者會(huì)重新變?yōu)闊o(wú)影響者。

雙層擴(kuò)散網(wǎng)絡(luò)中的下層為信息層，采用unawareaware-unaware（UAU）信息傳播模型來(lái)表示[22]。在UAU 模型中，個(gè)體分別處于沒(méi)有信息（unaware，簡(jiǎn)稱(chēng)U）和有信息（aware，簡(jiǎn)稱(chēng)A）兩種狀態(tài)。針對(duì)本文的突發(fā)事件情況，在災(zāi)情發(fā)生前所有個(gè)體都處于無(wú)信息狀態(tài)，則無(wú)信息者可用UAU 模型中的U 表示；在災(zāi)情擴(kuò)散時(shí)有部分個(gè)體獲得了信息且另一部分個(gè)體依然沒(méi)有獲得信息，則有信息者可用UAU 模型中的A 表示。同時(shí)，由于信息會(huì)隨著災(zāi)情的發(fā)展而不斷更迭，所以，災(zāi)情前期的有信息者在災(zāi)情后期也可能變?yōu)闊o(wú)信息者。

通過(guò)雙層擴(kuò)散網(wǎng)絡(luò)可以預(yù)測(cè)出各個(gè)災(zāi)區(qū)某一時(shí)間段的受影響者數(shù)量，從而計(jì)算出不同災(zāi)區(qū)在該時(shí)間段所需要配送的物資量。將處于SIS-UAU雙層網(wǎng)絡(luò)中的個(gè)體分成SU（沒(méi)有信息的無(wú)影響者）、SA（有信息的無(wú)影響者）、IA（有信息的受影響者）3 種狀態(tài)，且個(gè)體一旦被影響則其肯定會(huì)獲得信息，所以，不存在沒(méi)有信息的無(wú)影響者。圖1為雙層擴(kuò)散網(wǎng)絡(luò)示意圖。雖然事件層和信息層的個(gè)體總數(shù)相同，但是，各層內(nèi)個(gè)體之間的聯(lián)系卻不同。每個(gè)個(gè)體都有各自的行為狀態(tài)，分別由活躍狀態(tài)和不活躍狀態(tài)表示。白色圓圈表示活躍狀態(tài)，黑色圓圈表示不活躍狀態(tài)。

圖1 雙層擴(kuò)散網(wǎng)絡(luò)Fig.1 Two-layer spread network

在雙層擴(kuò)散網(wǎng)絡(luò)中，事件層度為l且信息層度為k的個(gè)體數(shù)量表示為Nlk。3 種狀態(tài)在t時(shí)段按照度分類(lèi)的個(gè)體數(shù)量分別表示為S Ulk(t)，S Alk(t)和IAlk(t)。 同時(shí)，令分別表示該時(shí)段3 種狀態(tài)占個(gè)體總數(shù)的密度值，并且成立。

因此，3 種狀態(tài)SU，SA 和IA 的個(gè)體狀態(tài)改變概率可以分別表示為

式中： α為個(gè)體處于活躍狀態(tài)的概率； λ為無(wú)影響者處于活躍狀態(tài)時(shí)獲取信息的概率； σ為接觸到信息的無(wú)影響者忽視信息的概率； μ為接觸到信息的受影響者轉(zhuǎn)變成有信息的無(wú)影響者的概率； βU為沒(méi)有獲取到信息的個(gè)體受到影響的概率； βA為獲取到信息的個(gè)體受到影響的概率， βA=(1-φ)βU；φ為獲取信息的概率； θ1(t)為 個(gè)體i任意一條連邊連接到具有信息個(gè)體的概率； θ2(t)為 個(gè)體i任意一條連邊連接到已受影響個(gè)體的概率。

然后，基于雙層擴(kuò)散網(wǎng)絡(luò)來(lái)預(yù)測(cè)各個(gè)災(zāi)區(qū)在t時(shí)段的受影響者總數(shù)IAlk(t)，從而計(jì)算該災(zāi)區(qū)所需的物資量Pr如式（2）所示。

式中： ω0為每位受影響者在一個(gè)時(shí)間段內(nèi)所需的物資量； ε為物資量不足的置信水平；為第i個(gè)區(qū)域在t時(shí)段經(jīng)過(guò)物資配送延遲時(shí)間tj后的受影響者總數(shù)；qi為 在t+tj時(shí) 刻第i個(gè)災(zāi)區(qū)對(duì)物資的需求預(yù)測(cè)總量。

1.2 多目標(biāo)應(yīng)急物流模型

多目標(biāo)應(yīng)急物流所要解決的問(wèn)題是如何合理安排若干輛相同型號(hào)的車(chē)輛分別從配送中心出發(fā)對(duì)各個(gè)災(zāi)區(qū)進(jìn)行物資配送。本文的目標(biāo)是找到一條最優(yōu)的路線規(guī)劃，在滿足各個(gè)災(zāi)區(qū)物資量的基礎(chǔ)上使車(chē)輛的行駛路程最短且所需的配送時(shí)間最少。利用基于雙層擴(kuò)散網(wǎng)絡(luò)的需求預(yù)測(cè)模型得出各個(gè)災(zāi)區(qū)在t時(shí)段的物資需求量qi，并在此基礎(chǔ)上對(duì)模型集合、參數(shù)和決策變量進(jìn)行設(shè)置。

在對(duì)模型集合的設(shè)置中，V′為災(zāi)區(qū)i,j的集合，V′={1,2,···,N},i,j∈V′。V為頂點(diǎn)集，V={0,1,2,···,N}，其中，0 代表應(yīng)急物資的配送中心。Q為應(yīng)急物資需求量qi的集合，qi∈Q。M為車(chē)型m的集合，m∈M。T為時(shí)間t的集合，t∈T。E為災(zāi)區(qū)之間距離d的集合，di j∈E。

在對(duì)模型參數(shù)的設(shè)置中，di j表示災(zāi)區(qū)i到災(zāi)區(qū)j之間的距離，dmax表 示災(zāi)區(qū)i到災(zāi)區(qū)j距離的閾值，即距離若超過(guò)dmax， 則不安排物資配送。Vm為配送車(chē)輛m的行駛速度，tm為 車(chē)輛m在單位距離內(nèi)所需的運(yùn)輸時(shí)間，tij為 災(zāi)區(qū)i到災(zāi)區(qū)j所需的運(yùn)輸時(shí)間，gm為 車(chē)輛m單位距離的可變成本，cmj為車(chē)輛m出配送中心的單位增加成本，F(xiàn)m為 車(chē)輛m的最大裝載量，u為應(yīng)急物資的單位質(zhì)量，qi(t)為在t時(shí)段災(zāi)區(qū)i對(duì)應(yīng)的應(yīng)急物資的需求量。

在對(duì)決策變量的設(shè)置中，xmij(t) 為 0-1 決策變量，表示在t時(shí)段是否安排車(chē)輛m從災(zāi)區(qū)i運(yùn)送應(yīng)急物資到災(zāi)區(qū)j。ym j(t)為 0-1 決策變量，表示在t時(shí)段災(zāi)區(qū)j是否由車(chē)輛m來(lái)運(yùn)送應(yīng)急物資。

建立多目標(biāo)應(yīng)急物流模型。式（5）的目標(biāo)為所需配送的時(shí)間T最短，式（6）的目標(biāo)為車(chē)輛運(yùn)輸成本C最低。

對(duì)于以上目標(biāo)函數(shù)，為應(yīng)急物資運(yùn)輸時(shí)間設(shè)定一個(gè)閾值tmin，若應(yīng)急物資能夠在規(guī)定的時(shí)間內(nèi)運(yùn)送到災(zāi)區(qū)，則時(shí)間成本為零，否則時(shí)間成本增加。同時(shí)，引入時(shí)間成本系數(shù) β來(lái)表示超過(guò)閾值tmin的延期罰函數(shù)系數(shù)，其測(cè)算方式為未滿足物資需求量延續(xù)一個(gè)單位時(shí)段對(duì)目標(biāo)函數(shù)的增加量。時(shí)間成本系數(shù) β 可根據(jù)實(shí)際車(chē)輛路徑問(wèn)題的緊急程度人為確定，通常情況下該系數(shù)的單位為元/h。將時(shí)間看作成本的一部分，把時(shí)間成本和運(yùn)輸成本相加獲得總成本，從而將多目標(biāo)函數(shù)轉(zhuǎn)換為單目標(biāo)函數(shù)。最終的應(yīng)急物流配送模型為

式（7）的約束條件為

上述約束條件中，式（8）中，tj表 示車(chē)輛m到達(dá)災(zāi)區(qū)j的時(shí)刻，tc表示車(chē)輛m到達(dá)災(zāi)區(qū)c的時(shí)刻。式（9）表示配送車(chē)輛所能覆蓋的最大范圍約束，若有效距離超過(guò)了閾值，則災(zāi)區(qū)i到災(zāi)區(qū)j不安排車(chē)輛配送。式（10）表示每條配送路線上各災(zāi)區(qū)的需求總量不能大于所分配車(chē)輛的最大負(fù)載Fm。式（11）表示共有M輛車(chē)來(lái)完成應(yīng)急物資配送任務(wù)，且每個(gè)災(zāi)區(qū)僅分配一輛車(chē)進(jìn)行運(yùn)送。式（12）～（14）保證了車(chē)輛路徑規(guī)劃能夠形成可行回路，其中，S表示頂點(diǎn)集的任一子集合，VS為 集合S的頂點(diǎn)個(gè)數(shù)。

2 進(jìn)化蜂群算法

2.1 人工蜂群算法

人工蜂群算法是一種仿照群體智能的全局優(yōu)化算法，通過(guò)模仿現(xiàn)實(shí)中蜜蜂采蜜的過(guò)程，該算法將人工蜂群分為了引領(lǐng)蜂（employed bees）、跟隨蜂（onlookers）和探索蜂（scouts），從而使得3 類(lèi)蜜蜂能夠在尋找最優(yōu)蜜源的過(guò)程中各司其職。在人工蜂群算法求解過(guò)程中，首先引領(lǐng)蜂基于已有信息來(lái)尋找蜜源，并將找到的蜜源信息告訴跟隨蜂；然后跟隨蜂依照獲得的信息按照一定概率來(lái)挑選候選蜜源，將該候選蜜源與之前的蜜源進(jìn)行比較，保留更優(yōu)的蜜源；最后當(dāng)某個(gè)蜜源經(jīng)過(guò)有限次循環(huán)后沒(méi)有更新時(shí)，則與該蜜源相關(guān)的蜜蜂轉(zhuǎn)變?yōu)樘剿鞣鋪?lái)繼續(xù)找尋潛在的新蜜源。

當(dāng)采用人工蜂群算法來(lái)解決優(yōu)化問(wèn)題時(shí)，每個(gè)蜜源都意味著優(yōu)化問(wèn)題中的一個(gè)解，且蜜源的花蜜數(shù)量意味著解的適應(yīng)度值，而在反復(fù)迭代過(guò)程中發(fā)現(xiàn)的最佳蜜源就是該問(wèn)題的最優(yōu)解。設(shè)定解的搜索空間為D維空間。由于在人工蜂群算法中引領(lǐng)蜂或跟隨蜂的數(shù)量與蜜源的數(shù)量相同，因此，引領(lǐng)蜂、跟隨蜂和蜜源的數(shù)量均為SN，且引領(lǐng)蜂和蜜源存在對(duì)應(yīng)關(guān)系。引領(lǐng)蜂和跟隨蜂根據(jù)式（15）在搜索空間中生成候選蜜源。

式中：表示新發(fā)現(xiàn)的候選蜜源，i和j是隨機(jī)產(chǎn)生，i∈{1,2,···,S N},j∈{1,2,···,D}；ri j為均勻分布在[-1，1]上的隨機(jī)數(shù)，用來(lái)規(guī)范候選蜜源的選擇范圍。

跟隨蜂依據(jù)概率pi來(lái)選擇蜜源，如式（16）所示，以適應(yīng)度值來(lái)表示各蜜源的花蜜數(shù)量，且適應(yīng)度值越大的蜜源，越有機(jī)會(huì)被選中。

式中，fiti表示第i個(gè)蜜源xi的適應(yīng)度值。

若引領(lǐng)蜂和跟隨蜂經(jīng)過(guò)有限次循環(huán)后沒(méi)有再次更新某個(gè)之前被選中的蜜源，那么，該蜜源將會(huì)被放棄，與該蜜源相關(guān)的蜜蜂將會(huì)變?yōu)樘剿鞣?，并根?jù)式（17）尋找新的蜜源。

式中： rand(0,1)是 區(qū)間[0,1]上的隨機(jī)數(shù)；為第j維的最小值和最大值。

2.2 進(jìn)化蜂群算法

本文所設(shè)計(jì)的進(jìn)化蜂群算法主要用于解決離散優(yōu)化問(wèn)題，如多目標(biāo)應(yīng)急物流問(wèn)題。傳統(tǒng)的人工蜂群算法是采用實(shí)數(shù)編碼，進(jìn)化蜂群算法通過(guò)自然數(shù)編碼來(lái)解決路徑規(guī)劃等離散問(wèn)題。本文算法有效融合了適應(yīng)度值和迭代進(jìn)化程度來(lái)判斷蜜源的好壞，同時(shí)利用交叉算子和變異算子組成的進(jìn)化操作來(lái)合理選擇候選蜜源。

現(xiàn)有文獻(xiàn)中對(duì)于人工蜂群的改進(jìn)方法主要以當(dāng)前迭代過(guò)程中的適應(yīng)度值來(lái)作為判斷蜜源優(yōu)劣程度的標(biāo)準(zhǔn)，而直接放棄了適應(yīng)度值暫時(shí)排名靠后的蜜源，造成了已知優(yōu)秀蜜源搜索次數(shù)過(guò)多而候選蜜源附近難以被充分挖掘，從而忽視了蜜源的潛在價(jià)值并降低了蜂群的搜尋活力。為了能夠充分利用蜜源信息，應(yīng)該給搜索空間中進(jìn)化程度較大的蜜源更多的搜索機(jī)會(huì)。同時(shí)，為了避免計(jì)算量的驟增，本文僅考慮進(jìn)化程度較大的蜜源且限制了搜索次數(shù)，從而增加了發(fā)現(xiàn)最優(yōu)蜜源的可能性。

對(duì)于蜜源優(yōu)秀度的衡量，不能僅考慮某次迭代過(guò)程中的適應(yīng)度值，而是應(yīng)該綜合考慮近期蜜源的平均歷史進(jìn)化程度，蜜源的迭代進(jìn)化程度定義為

在式（18）中，各個(gè)蜜源的編號(hào)由i表示，整個(gè)蜂群的迭代次數(shù)由t表示，此次蜜源進(jìn)化結(jié)束時(shí)刻由Nd表示。用來(lái)衡量蜜源進(jìn)化程度的時(shí)間間隔由Nb表示，在算法運(yùn)算過(guò)程中需要保留各蜜源的每次迭代進(jìn)化程度。

同時(shí)，將交叉算子和變異算子進(jìn)行融合，從而生成候選蜜源，通過(guò)交換蜜源之間優(yōu)秀的位置信息以突破蜂群內(nèi)的固定狀態(tài)并脫離局部最優(yōu)，實(shí)現(xiàn)蜜源的進(jìn)化以達(dá)到更高水平的平衡狀態(tài)。在進(jìn)化蜂群算法的運(yùn)算迭代中，保留各蜜源的適應(yīng)度值與蜜源進(jìn)化程度，將進(jìn)化程度排名靠前的蜜源運(yùn)用交叉算子和變異算子來(lái)進(jìn)化生成子代蜜源。將得到的子代蜜源與原來(lái)的蜜源的適應(yīng)度值進(jìn)行對(duì)比，若比原來(lái)的蜜源優(yōu)秀，則進(jìn)行替換。

交叉算子：按照交叉概率pc， 采用PMX（部分匹配交叉）法則進(jìn)行交叉操作。在2 個(gè)父代蜜源中隨機(jī)截取一段，并在這2 個(gè)父代蜜源所選段內(nèi)進(jìn)行連續(xù)交換，通過(guò)這些交換從而得到子代蜜源。例如，首先選取一個(gè)優(yōu)秀蜜源段為[5,2,6,7,4,0,1,3,8,9] 和一個(gè)鄰近蜜源段 [5,0,6,3,8,4,7,2,9,1]。其次隨機(jī)產(chǎn)生2 個(gè)隨機(jī)數(shù)滿足 0 ≤k1≤k2≤k，k為蜜源的長(zhǎng)度，如k1=3 和k2=7 作為截取蜜源段的起始位置和結(jié)束位置，得到 [5,2,6|7,4,0,1|3,8,9] 和[5,0,6|3,8,4,7|2,9,1]。接著再將截取到的2 個(gè)片段進(jìn)行位置交換，得到 [5,2,6|3,8,4,7|3,8,9] 和[5,0,6|7,4,0,1|2,9,1]。最后解決編碼重復(fù)的沖突問(wèn)題，對(duì)于[5,2,6|3,8,4,7|3,8,9]中原蜜源的3 和8 剛好與交叉過(guò)來(lái)的片段 |3,8,4,7|出現(xiàn)了重復(fù)，根據(jù)父代蜜源的 初 始 映 射 關(guān) 系 7 ?3、 4 ?8、 0 ?4、 1 ?7可 以得到子代蜜源段為 [ 5,2,6|3,8,4,7|1,0,9]。

變異算子：根據(jù)變異概率pm隨機(jī)生成一個(gè)變異點(diǎn)jm(m=1,2,···,h+m)，將子代蜜源循環(huán)左移jm個(gè)位置。例如，經(jīng)過(guò)交叉操作后的子代蜜源段為[5,2,6,3,8,4,7,1,0,9]，jm=3，經(jīng)變異操作后生成的最終蜜源段為 [ 3,8,4,7,1,0,9,5,2,6]。

2.3 進(jìn)化蜂群算法求解過(guò)程

通過(guò)構(gòu)建的基于雙層擴(kuò)散網(wǎng)絡(luò)的需求預(yù)測(cè)模型并利用Python 軟件得到每個(gè)災(zāi)區(qū)對(duì)應(yīng)的物資需求。通過(guò)無(wú)向圖G=(V,E,q)來(lái)描述多個(gè)災(zāi)區(qū)的配送車(chē)輛規(guī)劃問(wèn)題。V={0,1,2,···,N}表示頂點(diǎn)集，0 指代應(yīng)急物資的配送中心，其余數(shù)值指代各個(gè)等待配送的災(zāi)區(qū)。為邊集，各個(gè)災(zāi)區(qū)之間的距離為di j。qi∈Q,i={1,2,···,N}代表各災(zāi)區(qū)所對(duì)應(yīng)的物資需求。將應(yīng)急物流優(yōu)化問(wèn)題下的多目標(biāo)模型轉(zhuǎn)變成單目標(biāo)模型，并通過(guò)進(jìn)化蜂群算法進(jìn)行求解。

解決應(yīng)急車(chē)輛路徑問(wèn)題等同于要找出一條長(zhǎng)為h+m的最佳蜜源，每一個(gè)蜜源被編碼成一個(gè)解{0,x11,x12,···,x1n,0,x21,x22,···,x2v,···,0,xm1,xm2,···,xmw}，表示第一輛車(chē)從物資配送中心出發(fā)，途徑災(zāi)區(qū)點(diǎn)x11,x12,···,x1n返回到始發(fā)地。以此類(lèi)推，第m輛車(chē)從物資配送中心出發(fā)，途徑災(zāi)區(qū)點(diǎn)xm1,xm2,···,xmw返回到始發(fā)地。本文采用的自然數(shù)編碼方式相較于傳統(tǒng)的實(shí)數(shù)編碼方式，不僅減小了運(yùn)算搜索范圍，而且加快了迭代收斂速度。

進(jìn)化蜂群算法求解多目標(biāo)應(yīng)急物流優(yōu)化問(wèn)題的步驟如下：

步驟1初始化變量，包括通過(guò)雙層擴(kuò)散網(wǎng)絡(luò)下的需求預(yù)測(cè)模型來(lái)得到災(zāi)區(qū)數(shù)量N和每個(gè)災(zāi)區(qū)所需要的物資量qi∈Q,i={1,2,···,N}，配送中心和各災(zāi)區(qū)之間的距離di， 車(chē)輛m單位距離的可變成本gm，車(chē)輛m出配送中心的單位增加成本cmj，車(chē)輛m的行駛速度Vm，車(chē)輛m最大載重量Fm。蜂群的規(guī)模S，放棄條件L，最大迭代次數(shù)Mc。

步驟2初始化進(jìn)化蜂群，整個(gè)蜂群包含相等數(shù)量的引領(lǐng)蜂和跟隨蜂，且每個(gè)引領(lǐng)蜂與一個(gè)蜜源相關(guān)，所以，蜂群大小S的一半等同于初始蜜源個(gè)數(shù)FN，即FN=S/2。且所有蜜源初始化進(jìn)化程度為0，搜索次數(shù)為0，用于衡量蜜源進(jìn)化程度的時(shí)間間隔Nb=1。

步驟3計(jì)算所有蜜源的適應(yīng)度值fiti。根據(jù)式（7）得到目標(biāo)函數(shù)值Zi，則適應(yīng)度值函數(shù)為fiti=1/Zi。 若Zi對(duì)應(yīng)的解不可行，則賦予該解一個(gè)很大的整數(shù)R，從而在算法迭代中能夠被淘汰。計(jì)算所有蜜源的進(jìn)化程度（第一次迭代時(shí)的進(jìn)化程度等于適應(yīng)度值），選出進(jìn)化程度排名前FN/3的優(yōu)秀蜜源GS并記錄下最優(yōu)蜜源BS。

步驟4引領(lǐng)蜂帶領(lǐng)跟隨蜂到優(yōu)秀蜜源GSi附近隨機(jī)搜索另外的蜜源NSi，且依據(jù)輪盤(pán)賭原則分配探索蜂的數(shù)量。然后采用交叉算子和變異算子來(lái)完成進(jìn)化操作，產(chǎn)生GSi和NSi的 一個(gè)子代蜜源SSi。

步驟5在完成進(jìn)化后，更新所有優(yōu)秀蜜源GS的搜索次數(shù)hi,t=hi,t-1+Ni,t，其中，hi,t表示在編號(hào)為i的優(yōu)秀蜜源GSi在 第t代對(duì)應(yīng)的歷史搜索總次數(shù)，Ni,t表 示編號(hào)為i的優(yōu)秀蜜源GSi在 第t代對(duì)應(yīng)的搜索次數(shù)。每一次進(jìn)化操作后將產(chǎn)生FN/3個(gè)子代蜜源SS，并將這些子代蜜源的搜索次數(shù)賦值為0。

步驟6計(jì)算所有優(yōu)秀蜜源、剩余蜜源和子代蜜源的適應(yīng)度值和迭代進(jìn)化程度，此時(shí)共有4FN/3個(gè)蜜源。根據(jù)進(jìn)化程度對(duì)所有蜜源進(jìn)行排名，選擇排名前的蜜源成為新一代的優(yōu)秀蜜源進(jìn)行進(jìn)化操作。刪除排名最后FN/3個(gè)的蜜源，同時(shí)更新最優(yōu)蜜源BS。

步驟7若hi,t>L，即第i個(gè)蜜源的搜索次數(shù)已經(jīng)大于限制次數(shù)，則刪除第i個(gè)蜜源。那么，這個(gè)蜜源所對(duì)應(yīng)的引領(lǐng)蜂變?yōu)樘剿鞣?，并在下一次迭代中，按照排名次序增加一個(gè)優(yōu)秀蜜源的數(shù)量，使探索蜂對(duì)這個(gè)新增加的優(yōu)秀蜜源進(jìn)行進(jìn)化操作。

步驟8迭代總次數(shù)n=n+1， 判斷n>Mc是否成立，或者判斷是否達(dá)到了對(duì)應(yīng)的精度要求，若成立則可以結(jié)束運(yùn)算，輸出所有迭代過(guò)程中的最優(yōu)蜜源；否則返回步驟3 繼續(xù)迭代。

3 算例分析

假定最初在某地區(qū)發(fā)生了突發(fā)事件，從而產(chǎn)生了部分受影響者。經(jīng)過(guò)一段時(shí)間后，與該地區(qū)相鄰的其他區(qū)域的個(gè)體也受到了一定程度的影響?；陔p層擴(kuò)散網(wǎng)絡(luò)的需求預(yù)測(cè)模型的基本參數(shù)如表1 所示[5,22]?？梢詫r(shí)間段分為無(wú)影響階段、影響擴(kuò)散階段、影響控制階段和影響消亡階段。

根據(jù)這些參數(shù)可以計(jì)算得到4 個(gè)階段中有信息的無(wú)影響者（SA）、有信息的受影響者（IA）和沒(méi)有信息的無(wú)影響者（SU）數(shù)量的變化趨勢(shì)，如圖2所示?？梢钥闯觯绊懗潭葟淖畛醢l(fā)生突發(fā)事件至到達(dá)頂峰總共經(jīng)歷了10 天，從影響擴(kuò)散階段的第3 天出現(xiàn)有信息的受影響者，且該人數(shù)在影響控制階段的第4 天到達(dá)峰值。

圖2 影響變化趨勢(shì)Fig.2 Influence change trend

設(shè)定一共有30 個(gè)災(zāi)區(qū)，每個(gè)災(zāi)區(qū)的位置坐標(biāo)如表2 所示，數(shù)據(jù)來(lái)源于VRP 國(guó)際標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)庫(kù)（類(lèi)型：A，節(jié)點(diǎn)：31，車(chē)輛數(shù)：3）。已知每個(gè)災(zāi)區(qū)已經(jīng)受到影響的時(shí)間和物資配送延遲時(shí)間，可根據(jù)式（1）和式（2）分別得到各個(gè)災(zāi)區(qū)對(duì)于物資的需求量。其中，第3 個(gè)災(zāi)區(qū)和第10 個(gè)災(zāi)區(qū)的物資需求量最大均為159，且物資需求量在100 以上的災(zāi)區(qū)達(dá)到了14 個(gè)，可見(jiàn)突發(fā)事件正處于緊急狀態(tài)。

表2 災(zāi)區(qū)基本參數(shù)Tab.2 Basic parameters of emergency areas

設(shè)物資配送中的坐標(biāo)（X,Y）為（61, 59），其編號(hào)為第14，該中心總共有3 輛額定載重量為1 200 kg的汽車(chē)，配送車(chē)輛平均行駛速度為60 km/h，車(chē)輛出行一次的固定成本g=200 元，單位運(yùn)輸成本c=2 元/km，時(shí)間成本系數(shù) β=100 元/h。

進(jìn)化蜂群算法求解多目標(biāo)應(yīng)急物流問(wèn)題的參數(shù)設(shè)置為跟隨蜂50、探索蜂10 和引領(lǐng)蜂3，測(cè)試函數(shù)的維數(shù)為1 000，迭代次數(shù)為1 600 次。車(chē)輛運(yùn)輸總路徑長(zhǎng)度的收斂情況如圖3 所示，從圖3 中可以發(fā)現(xiàn)，進(jìn)化蜂群算法在前期收斂過(guò)程中的穩(wěn)定性要優(yōu)于人工蜂群算法，且后期的收斂效果要好于人工蜂群算法。這是因?yàn)檫M(jìn)化蜂群算法在求解多目標(biāo)物資配送路徑的過(guò)程中對(duì)部分進(jìn)化程度較大的蜜源給予了更多的選擇機(jī)會(huì)，且在蜜源進(jìn)化過(guò)程中能夠使優(yōu)秀的蜜源信息得以保留，從而在求解末期可以有效地避免局部最優(yōu)并提高求解效率。

圖3 算法收斂效果Fig.3 Algorithm convergence effect

當(dāng)累計(jì)迭代次數(shù)達(dá)到671 次時(shí)，可得多目標(biāo)應(yīng)急物流的最優(yōu)路徑里程為596.129 km。此時(shí)，3 輛汽車(chē)的行駛路徑和物資配送方案分別如圖4 和表3 所示，可以看出，3 輛汽車(chē)將原本分散且雜亂無(wú)章的災(zāi)區(qū)劃分為3 個(gè)部分。其中，A3 路線所經(jīng)過(guò)的災(zāi)區(qū)數(shù)量最多且行駛距離最長(zhǎng)，A2 路線所經(jīng)過(guò)的物資需求量超過(guò)100 的災(zāi)區(qū)最多但行駛距離最短，A1 路線所經(jīng)過(guò)災(zāi)區(qū)的物資需求量最少，但是，行駛距離則接近于A3 路線。綜上，3 條線路在載重量、行駛距離和運(yùn)輸成本方面均實(shí)現(xiàn)了合理分配，使得應(yīng)急物資能夠在最短的時(shí)間內(nèi)以最高效的方法送達(dá)各個(gè)災(zāi)區(qū)。

圖4 車(chē)輛行駛路徑Fig.4 Vehicle paths

表3 應(yīng)急物資調(diào)配方案Tab.3 Emergency material distribution plan

4 結(jié)束語(yǔ)

應(yīng)急物資的合理分配和及時(shí)送達(dá)對(duì)于突發(fā)事件的防控而言至關(guān)重要，本文以準(zhǔn)確性、合理性、時(shí)間短和成本低為目標(biāo)研究了多個(gè)災(zāi)區(qū)的物資需求和車(chē)輛配送問(wèn)題。首先，考慮到移動(dòng)互聯(lián)時(shí)代下信息傳播和個(gè)體行為對(duì)于災(zāi)情擴(kuò)散的影響，構(gòu)建了基于SIS-UAU 雙層擴(kuò)散網(wǎng)絡(luò)的需求預(yù)測(cè)模型，以保證應(yīng)急物資分配的合理性和準(zhǔn)確性。其次，設(shè)計(jì)了一種改進(jìn)的離散蜂群算法來(lái)有效優(yōu)化車(chē)輛的運(yùn)輸路徑，不僅利用交叉算子和變異算子使蜜源在進(jìn)化過(guò)程中的優(yōu)秀信息得以保留，而且依據(jù)適應(yīng)度值和歷史進(jìn)化程度為優(yōu)秀蜜源提供了更多的搜索機(jī)會(huì)，從而充分挖掘了蜂群價(jià)值并有效提升了迭代效率。最后，通過(guò)算例表明了進(jìn)化蜂群算法在解決離散路徑選擇問(wèn)題時(shí)要優(yōu)于傳統(tǒng)的人工蜂群算法，且在車(chē)輛載重量和行駛距離等方面均實(shí)現(xiàn)了合理分配，能夠在最短時(shí)間內(nèi)以最低成本完成應(yīng)急物資運(yùn)送。由于現(xiàn)實(shí)中的物資配送是一個(gè)重要且復(fù)雜的問(wèn)題，因此，未來(lái)將從以下兩個(gè)方面繼續(xù)進(jìn)行研究：一方面是研究多層多維度的應(yīng)急物資配送問(wèn)題；另一方面是研究多配送中心、多種運(yùn)輸方式下的應(yīng)急物資配送問(wèn)題。