基于免疫—蟻群算法的應急物流配送網絡優化研究

曹慶奎， 吳向儒， 車美林 （河北工程大學 經濟管理學院，河北 邯鄲 056038）

近幾年來突發事件應急處理提升到一定的高度，應急物流系統開始得到學術界的重視。而配送問題是應急物流中的一個重要分支，所以應急物流配送網絡優化問題的研究很有必要，其對提高應對突發事件能力和災害應急管理水平有非常重要的意義。

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

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

1 模型的構建

1.1 模型的描述和符號說明

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

1.2 建立多目標函數

本文應用免疫結合蟻群的混合算法對應急物流的配送路徑進行安排。不僅從運輸時間方面，更融入了安全通過概率和運輸距離兩個目標，對應急物流運輸路線優化問題進行求解。

假設決策變量為：bjh=1，應急車輛經過；否則為0，應急車輛不經過。

（1） 時效性

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

（2） 安全性

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

推動校企合作辦學是此次課程考核評價改革的亮點之一。在實踐環節的考核階段，根據訓方案的確定、實驗操作和熟練程度等考核指標進行一一對照，嘗試將學生和企業一線員工納入考核評價團隊，提高評價的客觀性和公正性。

1

（3） 經濟性

設Di為所有應急服務設施中心i到其所提供服務的q個需求點運輸線路總距離，djh為車輛在任意路徑j,（）h 上的行駛距離。

根據上述目標，可確定多目標函數如下：

2 用免疫結合蟻群的混合算法求解

第一步，輸入問題確認編碼并設置啟發信息[5]。

假設需求點j到需求點h所要花費時間是tjh，需求點j與需求點h之間的距離為djh，車輛通過路徑j,（）h 的安全通過概率為lgpjh，則應急服務設施中心i對螞蟻k的啟發信息設置如下式所示。

第二步，采用評價指標計算親和力和排斥力。

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

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

第三步，抗體選擇，按照 “優勝略汰”的自然選擇機制，在新產生的若干抗體中，選擇與抗原匹配較好的抗體構成新的集合，轉第二步。

第四步，更新信息素。

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

上式中，Q為常量，表示信素強度，它在一定程度上影響算法的收斂速度，共有K只螞蟻，表示第k只螞蟻在本次搜索中所得到的最小偏差值。τi（t）為t時刻節點i的信息素，為第k只螞蟻在經搜索所得到的節點集合，ρ為信息素揮發因子。

應急資源運輸路線安排方案調整考慮到災害發生后各種隨機因素的影響,車輛在途中應根據實時交通信息隨時調整原始行駛路線。構造適當的免疫算子pi，處理獲得的當前時段路段行程目標預測值,若計算得到的車輛最優路徑比初始路線方案節省一定的程度 （如至少節省10%的行程目標值），那么新的行車路線可被接受，車輛按新路線行駛；否則，仍維持原路線不變。

第五步，進行迭代循環，知道滿足算法的停止條件為止。

3 模型檢驗與分析

設 9個應急點為1,2,3,4,5,6,7,8,9。它們之間的距離表示如下：

4 結束語

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

[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].西南石油學院學報，2003,25(1):80-83.

[4] 陳雷雷，王海燕.大規模突發事件中基于滿意度的應急物資優化調度模型[J].中國安全科學學報，2010(5):46-52.

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