基于免疫—蟻群算法的應(yīng)急物流配送網(wǎng)絡(luò)優(yōu)化研究

曹慶奎， 吳向儒， 車美林 （河北工程大學(xué) 經(jīng)濟(jì)管理學(xué)院，河北 邯鄲 056038）

近幾年來突發(fā)事件應(yīng)急處理提升到一定的高度，應(yīng)急物流系統(tǒng)開始得到學(xué)術(shù)界的重視。而配送問題是應(yīng)急物流中的一個重要分支，所以應(yīng)急物流配送網(wǎng)絡(luò)優(yōu)化問題的研究很有必要，其對提高應(yīng)對突發(fā)事件能力和災(zāi)害應(yīng)急管理水平有非常重要的意義。

對應(yīng)急物流配送網(wǎng)絡(luò)的優(yōu)化問題，包括節(jié)點(diǎn)的優(yōu)化及節(jié)點(diǎn)之間線路的優(yōu)化，本文重點(diǎn)介紹應(yīng)急物流配送路線的選擇，實(shí)際上，將配送車輛的路徑優(yōu)化問題和應(yīng)急物流結(jié)合起來研究有一定的難度，然而將二者統(tǒng)一的具體研究，更貼近目前物流系統(tǒng)復(fù)雜的實(shí)際特征，所以對它的研究很有價值。目前對于配送車輛路徑優(yōu)化的研究，多是以一般物流為基礎(chǔ)，但是，應(yīng)急物流與一般物流卻存在著很多區(qū)別，例如：自然災(zāi)害等突發(fā)事件可能造成部分道路毀壞、信息不暢通、物資需求變動等，導(dǎo)致運(yùn)輸網(wǎng)絡(luò)容量具有很大的不確定性；應(yīng)急物流的配送車輛的路徑優(yōu)化問題主要是以時間效益最大化和損失最小化，而不是僅以成本最小化為目標(biāo)，因此，應(yīng)急物流配送車輛路徑優(yōu)化模型的目標(biāo)、參數(shù)及約束條件與一般物流還是存在著一定區(qū)別的。國內(nèi)外的相關(guān)文獻(xiàn)大多分為關(guān)于運(yùn)輸時間最小化為目標(biāo)的研究和關(guān)于運(yùn)輸成本最小化為目標(biāo)的研究：Ae Young Choi研究了在路網(wǎng)情況不確定情況下如何分配有限的資源 （如救護(hù)車和其它應(yīng)急救災(zāi)車輛）將受傷人員運(yùn)輸?shù)结t(yī)院，目標(biāo)是使受傷人員存活數(shù)最大[1]。Gulay提出了一種分層多標(biāo)準(zhǔn)方法解決直升機(jī)在救災(zāi)中的調(diào)度問題，使派遣的直升機(jī)和飛行員數(shù)目在滿足需求下成本最低[2]。國內(nèi)的研究有計雷，池宏等研究員提出在突發(fā)事件中，物資運(yùn)輸?shù)氖滓獑栴}是研究盡快將物資運(yùn)送到指定的災(zāi)害發(fā)生地，此時的運(yùn)輸問題變成了帶時間約束的運(yùn)輸問題，目標(biāo)函數(shù)不僅僅是成本最小化，更重要的是運(yùn)送時間最小化。盧安文等人于2003研究了緊急情況下的物流配送的必要性，建立了考慮公路運(yùn)輸?shù)木o急情況下的物流配送模型，并考慮多種運(yùn)輸方式，以時間、費(fèi)用為目標(biāo)建立了0-1整數(shù)規(guī)劃模型及目標(biāo)規(guī)劃模型[3]。

目前研究中存在的問題：首先，以往研究較少涉及災(zāi)后沿街建筑倒塌、避難人群疏散及道路受損引起車輛運(yùn)行時間的隨機(jī)性等因素；多數(shù)文獻(xiàn)中的模型參數(shù)大都是固定不變的，很少考慮到實(shí)際中車輛數(shù)、車場等這些隨時變化的參數(shù)[4]；對應(yīng)急物流配送網(wǎng)絡(luò)的研究通常以一般物流為基礎(chǔ)，這明顯不符合實(shí)際：首先，在應(yīng)急突發(fā)事件發(fā)生的情況下，配送中的車輛路線選擇所考慮的影響因素明顯不同于一般物流；其次，一般物流配送車輛的路徑優(yōu)化模型都是以成本最小化為單一目標(biāo)，在重大突發(fā)事件發(fā)生的情況下，應(yīng)急物流配送的目標(biāo)是以較快的速度安全地將有限的物資送達(dá)需求地，是多目標(biāo)問題。

1 模型的構(gòu)建

1.1 模型的描述和符號說明

設(shè)有m個應(yīng)急需求點(diǎn)集合，其在計劃期內(nèi)發(fā)生突發(fā)事故的概率為需求點(diǎn)j所要求的服務(wù)數(shù)量為Mj；n個備選的應(yīng)急服務(wù)設(shè)施中心集合，其建設(shè)容量為從應(yīng)急服務(wù)設(shè)施中心i到需求點(diǎn)j的應(yīng)急時間為tij，由應(yīng)急服務(wù)設(shè)施中心i到需求點(diǎn)j運(yùn)送應(yīng)急資源的單位運(yùn)輸費(fèi)用為cij，應(yīng)急服務(wù)設(shè)施中心i到需求點(diǎn)j應(yīng)急資源的運(yùn)輸量為xij；需求點(diǎn)j一般要求的應(yīng)急服務(wù)必須在時間ETj內(nèi)到達(dá)；q為應(yīng)急服務(wù)設(shè)施中心i所提供救援服務(wù)的需求點(diǎn)的數(shù)量；pjh為車輛在路徑j(luò),（）h 上的安全通過概率。已知應(yīng)急服務(wù)中心i的開設(shè)費(fèi)用為Si，災(zāi)害損失函數(shù)為dj（t），救援函數(shù)為時刻表示救援車輛到達(dá)需求點(diǎn)j的時間；為第c種物資每單位物資的重量；為第m種運(yùn)輸方式下，v種類型運(yùn)輸車輛的載重量；為第m種運(yùn)輸方式下，直接相鄰的n1點(diǎn)，n2點(diǎn)關(guān)于v種類型運(yùn)輸車輛的道路容量；為t時段在第m種運(yùn)輸方式下，通過弧 （n1,n2）點(diǎn)n2接收到的c種物資的數(shù)量；為t時段在第m種運(yùn)輸方式下，經(jīng)過弧 （n1,n2）到達(dá)點(diǎn)n2的v種類型運(yùn)輸車輛的數(shù)量。

1.2 建立多目標(biāo)函數(shù)

本文應(yīng)用免疫結(jié)合蟻群的混合算法對應(yīng)急物流的配送路徑進(jìn)行安排。不僅從運(yùn)輸時間方面，更融入了安全通過概率和運(yùn)輸距離兩個目標(biāo)，對應(yīng)急物流運(yùn)輸路線優(yōu)化問題進(jìn)行求解。

假設(shè)決策變量為：bjh=1，應(yīng)急車輛經(jīng)過；否則為0，應(yīng)急車輛不經(jīng)過。

（1） 時效性

設(shè)Ti為所有應(yīng)急服務(wù)設(shè)施中心i到其提供救援服務(wù)的所有需求點(diǎn)的運(yùn)輸總時間，tjh為應(yīng)急服務(wù)設(shè)施中心i的救援車輛在應(yīng)急服務(wù)設(shè)施中心i所提供服務(wù)的需求點(diǎn)子類中的任意需求點(diǎn)j需求點(diǎn)h路徑（j,h ）上的行駛時間 （1■j≠h■q ）。目標(biāo)是對于應(yīng)急服務(wù)設(shè)施中心i，其到所提供服務(wù)的所有需求點(diǎn)的運(yùn)輸時間為Ti，即，時效性的目標(biāo)是讓Ti最小。則對于應(yīng)急服務(wù)設(shè)施中心i，基于時效屬性的目標(biāo)函數(shù)為：

（2） 安全性

pjh為車輛在路徑上的安全通過概率，車輛安全通過有q個需求點(diǎn)的整條路L的概率為：即，

推動校企合作辦學(xué)是此次課程考核評價改革的亮點(diǎn)之一。在實(shí)踐環(huán)節(jié)的考核階段，根據(jù)訓(xùn)方案的確定、實(shí)驗(yàn)操作和熟練程度等考核指標(biāo)進(jìn)行一一對照，嘗試將學(xué)生和企業(yè)一線員工納入考核評價團(tuán)隊(duì)，提高評價的客觀性和公正性。

1

（3） 經(jīng)濟(jì)性

設(shè)Di為所有應(yīng)急服務(wù)設(shè)施中心i到其所提供服務(wù)的q個需求點(diǎn)運(yùn)輸線路總距離，djh為車輛在任意路徑j(luò),（）h 上的行駛距離。

根據(jù)上述目標(biāo)，可確定多目標(biāo)函數(shù)如下：

2 用免疫結(jié)合蟻群的混合算法求解

第一步，輸入問題確認(rèn)編碼并設(shè)置啟發(fā)信息[5]。

假設(shè)需求點(diǎn)j到需求點(diǎn)h所要花費(fèi)時間是tjh，需求點(diǎn)j與需求點(diǎn)h之間的距離為djh，車輛通過路徑j(luò),（）h 的安全通過概率為lgpjh，則應(yīng)急服務(wù)設(shè)施中心i對螞蟻k的啟發(fā)信息設(shè)置如下式所示。

第二步，采用評價指標(biāo)計算親和力和排斥力。

考慮應(yīng)急時間最早、通過路徑的危險程度最小及運(yùn)輸距離最短三種優(yōu)化目標(biāo)時,螞蟻k所取得的較優(yōu)解與理想解的偏差ukr。尋找抗體和抗原的匹配程度，計算方法如下式。

tk為螞蟻k搜索到的最早應(yīng)急時間，t*為在只考慮應(yīng)急時間最早的情況下所取得的最早應(yīng)急時間；-lgPk為螞蟻k搜索到的通過路徑的最小危險程度，-lgP*為在只考慮危險程度最小的情況下取得的最小危險程度；dk為螞蟻k搜索到的最小運(yùn)輸距離，d*為在只考慮運(yùn)輸距離最短情況下取得的最小運(yùn)輸距離。

第三步，抗體選擇，按照 “優(yōu)勝略汰”的自然選擇機(jī)制，在新產(chǎn)生的若干抗體中，選擇與抗原匹配較好的抗體構(gòu)成新的集合，轉(zhuǎn)第二步。

第四步，更新信息素。

為更好地利用全局信息，同時避免算法陷入局部最優(yōu)，本論文采用免疫算法，將各個物資供應(yīng)點(diǎn)的信息素限定在之間。

上式中，Q為常量，表示信素強(qiáng)度，它在一定程度上影響算法的收斂速度，共有K只螞蟻，表示第k只螞蟻在本次搜索中所得到的最小偏差值。τi（t）為t時刻節(jié)點(diǎn)i的信息素，為第k只螞蟻在經(jīng)搜索所得到的節(jié)點(diǎn)集合，ρ為信息素?fù)]發(fā)因子。

應(yīng)急資源運(yùn)輸路線安排方案調(diào)整考慮到災(zāi)害發(fā)生后各種隨機(jī)因素的影響,車輛在途中應(yīng)根據(jù)實(shí)時交通信息隨時調(diào)整原始行駛路線。構(gòu)造適當(dāng)?shù)拿庖咚阕觩i，處理獲得的當(dāng)前時段路段行程目標(biāo)預(yù)測值,若計算得到的車輛最優(yōu)路徑比初始路線方案節(jié)省一定的程度 （如至少節(jié)省10%的行程目標(biāo)值），那么新的行車路線可被接受，車輛按新路線行駛；否則，仍維持原路線不變。

第五步，進(jìn)行迭代循環(huán)，知道滿足算法的停止條件為止。

3 模型檢驗(yàn)與分析

設(shè) 9個應(yīng)急點(diǎn)為1,2,3,4,5,6,7,8,9。它們之間的距離表示如下：

4 結(jié)束語

本文綜合考慮了應(yīng)急救援物資調(diào)度在運(yùn)輸時效性、經(jīng)濟(jì)性和安全可靠性等要求，而不是把應(yīng)急物資的調(diào)度的研究目的僅僅局限在運(yùn)輸成本最小或是應(yīng)急時間最短；考慮多物資運(yùn)輸，多類型車輛，和道路受損引起車輛運(yùn)行時間的隨機(jī)性等因素；在求解模型時，運(yùn)用人工免疫算法和蟻群算法的混合算法，快速求解實(shí)時應(yīng)急求援物資運(yùn)輸問題，有效提高尋優(yōu)精度和響應(yīng)速度。并對其進(jìn)行實(shí)證研究，通過不同算法的比較，驗(yàn)證本文模型和算法的可行性和有效性，為應(yīng)急管理部門提供有效的輔助建議。

[1] Jae Young choi.Stochastic Scheduling Problems for Minimizing Tardy Jobs with Application to Emergency Vehicle Dispatchingon Unreliable Road Network[D].Unpublished Doctors Thesis,University of New York,2003:61-68.

[2] Gulay Barbarosoglu,Linet Ozdamar,Ahmet Cevik.An Interactive Approach for Hierarchical Analysis of Helicopter Logistics in Disaster Relief Operations[J].European Journal of Operational Research,2002,140(1):118-133.

[3] 盧安文.緊急情況下的物流配送模型[J].西南石油學(xué)院學(xué)報，2003,25(1):80-83.

[4] 陳雷雷，王海燕.大規(guī)模突發(fā)事件中基于滿意度的應(yīng)急物資優(yōu)化調(diào)度模型[J].中國安全科學(xué)學(xué)報，2010(5):46-52.

[5] 馬建華，房勇，袁杰.多車場多車型最快完成車輛路徑問題的變異蟻群算法[J].系統(tǒng)工程理論與實(shí)踐，2011,31(8):1508-1516.