基于混合遺傳算法的應急物資配送路徑優化

韓孟宜, 丁俊武， 陳夢覃, 霍珂珣

(揚州大學信息工程學院， 揚州 225127)

近年來，突發事件頻繁發生，對國家安定和人民幸福生活都造成了一定的威脅。例如，2003年非典事件，累計病例5 327例，死亡349人，當時造成了社會的高度恐慌；2008年汶川大地震造成69 227人遇難，374 643人受傷，17 923人失蹤，經濟損失高達8 451億元；2010年玉樹地震遇難約 2 700 人，失蹤 280 人，經濟損失8 000 多億元。突發事件發生后，需要采取及時有效的措施進行應急救援，否則將會造成更為嚴重的后果。應急物資配送作為應急救援中的重要環節之一，優化其配送路徑對實現應急物資的高效調配來說至關重要。因此，對應急物資的配送路徑進行優化研究具有十分重要的意義。

目前，對應急物資配送路徑優化的研究如下：劉娜等[1]研究了疫情期間社區商超的物資配送路徑問題，利用自組織映射(self-organizing map, SOM)算法與遺傳算法對車輛路徑規劃模型進行求解，最后得出的結論是遺傳算法的結果更優；Li等[2]構建了以配送時間最短、受災點滿意度最大為目標的應急物資配送路徑優化模型，采用快速非支配排序遺傳算法求解模型；康斌等[3]以最小化最晚車輛服務結束時間、最小化需求未滿足率為目標建立了多目標應急救援物資配送路徑優化模型，設計優先鄰點交叉算子改進遺傳算法對模型進行求解；艾云平[4]考慮了各需求客戶的硬時間窗要求,以所有配送車輛的路徑總距離最短作為優化目標建立了數學模型，設計了基于改進的智能蟻群算法進行求解；張洪福等[5]研究的是行蓄洪區的物資配送路徑，建立了以車輛運輸時間最短、受災點時間滿意度最大為目標的優化模型，利用改進節約算法進行模型求解；Jiang等[6]建立了以配送時間最短、配送成本最低、物資短缺最少為目標的應急物資調度模型，采用魯棒優化的方法進行求解。

眾多學者對應急物資配送路徑優化做了相關研究，但當前研究大多是以路程最短、時間最短、成本最低、需求點滿意度最大等為目標建立的數學模型，研究時間窗限制下的應急物資配送路徑優化不多；且在求解車輛路徑優化模型時用到的大多數啟發式算法為節約算法[5,7]、遺傳算法[1,3,8-10]、蟻群算法[4,11-12]、粒子群算法[13]等。就遺傳算法來說，雖然它具有全局搜索能力強、收斂速度快的優點，但是由于它是隨機生成初始解，在一定程度上增加了它的搜索難度，并且它的局部搜索能力不足，在優化較為復雜的問題時容易陷入局部最優。為彌補這些不足，在時間窗約束下，以配送車輛的固定成本、運輸成本、違反最大載重量以及受災點右時間窗的懲罰成本之和最小為目標建立了優化模型，設計混合遺傳算法求解，最后借助算例說明模型及算法的有效性。

1 應急物資配送路徑優化模型構建

1.1 問題描述

本文研究要解決的應急物資配送路徑優化問題有：單個調配中心，多個受災點，已知調配中心和各受災點的位置，以及各受災點的需求量、時間窗、卸貨時間等，要求每個受災點只能由一輛車進行配送，且完成配送任務后需重返配送中心。其目標是優化配送車輛的路徑，使得在時間窗約束下總成本最低，應急物資配送路線示意圖如圖1所示。

圖1 應急物資配送路線示意圖

受災點的時間窗為硬時間窗[e,l]，即配送車輛須在各受災點要求的時間窗內進行卸貨[14-16]。若配送車輛提前到達不會產生懲罰成本，不過要等到左時間窗e才能開始卸貨，但是不允許超過右時間窗l，一旦超過就會產生相應的懲罰成本Pt。硬時間窗下的懲罰函數圖像如圖2所示。

圖2 硬時間窗下的懲罰函數圖像

1.2 模型假設

(1)假設每個受災點的應急物資需求量不超過運輸車輛的最大載重量，且每個受災點僅能被一輛車服務。

(2)假設運輸車輛的初始位置為各調配中心，且完成配送任務后需重返調配中心。

(3)假設調配中心的應急生活物資數量足以滿足各受災點的需求。

(4)假設運輸車輛為同一類車型，具有相同的載重量。

1.3 符號說明

gi：受災點i的應急物資需求量；

dij：受災點i到受災點j的距離；

tij：車輛從受災點i到受災點j的運輸時間；

si：受災點i卸貨所用的時間；

v：車輛運輸的速度；

c1：車輛的固定使用費用；

c2：車輛每公里的運輸費用；

ti：車輛到達受災點i的時間；

ei：受災點i的左時間窗；

li：受災點i的右時間窗；

P1：配送車輛在路徑中超載的單位懲罰成本；

P2：配送車輛違反受災點右時間窗限制的單位懲罰成本；

f：應急物資配送過程中產生的總成本，由f1、f2、f3、f4四部分組成；

Q：車輛的最大載重量。

決策變量：

1.4 模型建立

配送車輛的固定成本：

(1)

配送車輛的運輸成本：

(2)

違反配送車輛最大載重量的懲罰成本：

(3)

違反受災點右時間窗的懲罰成本：

(4)

目標函數：

minf=f1+f2+f3+f4

(5)

約束條件：

(6)

(7)

(8)

(9)

(10)

(11)

(12)

ti≤li

(13)

(14)

(15)

xijk、yik∈{0,1}

(16)

式(5)是目標函數，表示配送車輛的固定成本、運輸成本以及違反最大載重量和受災點右時間窗的懲罰成本之和最少。

式(6)～(16)是約束條件，式(6)表示每輛車運輸的應急物資數量不能超過車的最大載重量；式(7)表示每個受災點i的應急物資只能由一輛車完成配送任務；式(8)、式(9)表示每個受災點i都只能在一條配送路徑中；式(10)表示所有受災點的應急物資都有車輛配送；式(11)表示每輛車從配送中心發出且完成任務返回配送中心；式(12)表示每一個受災點上下均只與一個節點相連；式(13)表示到達受災點i的時間不能超過受災點i的右時間窗；式(14)表示到達受災點j的時間；式(15)表示配送車輛從受災點i到受災點j的運輸時間；式(16)表示xijk、yik是0-1變量。

2 基于混合遺傳算法的模型求解

2.1 算法介紹

2.1.1 節約算法

節約算法(saving algorithm)，又稱C-W算法，其核心思想是將運輸問題中的兩個回路合并成一個回路，使得合并后的運輸距離有較大幅度的減小[7]。它的基本思想就是用節約運輸距離的方法去尋找最佳的配送路線，使得配送時間和配送成本有所降低，從而實現高效率的配送。利用節約算法求解應急物資配送路徑的初始解，在滿足各受災點需求量、時間窗以及車輛最大載重量的約束下，將距離最短的路徑作為問題的初始解。

2.1.2 遺傳算法

遺傳算法(genetic algorithm，GA)是由美國的John Holland教授在1975年首先提出來的，它是通過借鑒生物界的進化規律“適者生存，優勝劣汰”演化而來的一種基于種群的隨機化搜索方法[16]。它的基本思想是先將問題的初始解編碼到染色體中，然后根據適應度函數計算每個個體的適應度值，接著通過選擇操作將適應度高的個體保留到下一代中，通過交叉、變異操作得到多樣性的解，不斷進行迭代，達到終止條件后輸出所求問題的最優解。

2.1.3 大規模鄰域搜索算法

大規模領域搜索算法(large neighborhood search)是Shaw[17]提出來的，其算法主要包含破壞操作和修復操作兩部分。它的算法原理為：先使用破壞算子從當前解中移除若干點，然后再用修復算子對移除的解進行修復，重新安插到被破壞的解中。

2.2 混合遺傳算法設計

為能在一定程度上降低遺傳算法的搜索維度，用節約算法生成種群的初始解；針對遺傳算法局部搜索能力不足的情況，引入大規模鄰域搜索算法中的破壞算子和修復算子，以此增強算法的局部搜索能力。通過將節約算法、遺傳算法、大規模鄰域搜索算法3種算法的優點相結合，從而構造出了用于解決應急物資配送路徑優化的混合遺傳算法。混合遺傳算法的流程圖如圖3所示。

圖3 混合遺傳算法流程圖

(1)編碼。對染色體進行整數編碼，當受災點數目為N且調配中心最大車輛數為K時，可將染色體的長度記為N+K-1，染色體表示為(1,2,…，N+K-1)。

(2)種群初始化。首先構造問題的初始解。為能在一定程度上降低遺傳算法的搜索維度，采用節約算法構造問題的初始解，假設n是標記第幾大距離節約值的位置，具體步驟如下。

step1將每個受災點分配給一輛車，即每個受災點的應急物資都由單獨分配的車輛進行配送。

step2計算把兩條路徑融合后的距離節約值，將距離節約值由大到小降序排列。

step3按順序依次判斷要融合的兩條路徑是否滿足受災點的時間窗約束，若滿足則將第n大距離節約值的兩條路徑融合，進行step4；否則令n=n+1，重復step3。

step4更新距離節約值，將距離節約值最大的兩條路徑融合，判斷融合路徑上配送車輛運輸的應急物資數量是否超過最大載重量，若超過，令n=n+1，進行step5；否則重復step4。

step5將第n大距離節約值的兩條路徑融合，判斷在某條路徑上是否還存在只有一個受災點的情況，若存在則重復step4，否則輸出每輛車所經過的受災點序號。

通過節約算法得到初始配送方案后，開始進行種群的初始化。先將初始解按照編碼方式轉換為個體，然后再將種群內的所有個體全部賦值為初始解轉換的個體。

(3)適應度函數。本文所建模型中的目標函數f是由運輸車輛的固定成本、運輸成本以及違反最大載重量和受災點右時間窗的懲罰成本組成，根據題意可知目標函數越小則所得結果越好，為了能夠在選擇操作中把好的結果保留下來，故在此將適應度函數設置為目標函數的倒數，即令f(x)=1/f。

(4)選擇操作。采用輪盤賭選擇法進行選擇，其基本思想是各個體被選中的概率與適應度值的大小成正比，即將適應度值大的個體選擇出來[15]。具體操作過程為：先將群體中每個個體帶入適應度函數中，計算得到它們的適應度值f(xi)；然后根據式(17)計算每個個體被遺傳到下一代群體中的概率。

(17)

(5)交叉操作。選用順序交叉(order crossover，OX)的方式進行交叉操作，此交叉方法在面對兩個相同父代的情況下仍能產生一定變異效果，對維持群體多樣性有一定的作用[18]。先在兩個父代個體上隨機選擇兩個交叉位置；然后將交叉位置中間的兩個交叉片段提取出來，交叉放在不同父代個體的前面；最后將每個個體中第2 個重復的基因位刪掉，便可形成兩個子代個體。具體操作流程如圖4所示。

圖4 OX交叉操作流程

(6)變異操作。在父代個體的染色體上隨機選擇兩個變異位置，然后將兩個位置上的基因進行交換，得到子代個體，具體操作流程如圖5所示。

圖5 變異操作流程

(7)局部搜索操作。使用大規模鄰域搜索算法中的破壞算子根據相似性計算公式從當前解中移除一部分受災點，然后再使用修復算子在滿足車輛載重量和受災點右時間窗約束的情況下，盡可能地將移除的受災點安插到使目標函數值增加最少的位置。

Remove過程：用σ表示當前解，c表示將被移除的受災點，s表示被移除的受災點組成的集合，p表示移除的受災點數量，σ′表示從σ中移除p個受災點后剩余的解。先從σ中隨機移走一個受災點到s中，剩下的p-1個受災點按照下面方法選擇：從s中隨機選擇一個受災點z，將σ中剩下的受災點按照與z的相關性由小到大排序，選擇出相關性最大的受災點c，將其從σ中移到s中，重復p-1次，直至剩下的p-1個受災點都選好了。相關性公式[9]可表示為

(18)

(19)

式中：d′ij為dij標準化后的值，位于區間[0,1]；dij為i、j兩個受災點間的距離；vij表示i、j個受災點是否在同一條路徑中，若是則為0，否則為1。該相關性公式表明：兩個受災點若距離越近，則相關性越大；兩個受災點若在同一條路徑上，則相關性越大。

為防止因過度依賴相關性函數致使移出去的受災點存在不合理的情況，借鑒Shaw[17]的方法，加入隨機元素，即在由大到小排好的相關性序列中隨機選擇受災點。

index=[Random([0,1])]D×(σ中剩余的受災點)。

當D=1時，說明受災點是完全隨機選擇移除的；當D=+∞時，說明受災點是完全根據相關性大小選擇移除的。

Re-inserting過程：首先根據載重量約束和時間窗約束找到集合s中每個受災點在σ′中的最佳插入位置，最佳位置即插入后使目標函數值增加最小的那個位置。然后計算s中每個受災點插到最佳位置后的目標增加值，選擇目標增加值最大的受災點作為第一個插入的點，重復此操作，直至集合s中的元素被全部插入到σ′中。

(8)終止條件。將事先確定的進化代數作為終止條件，即達到最大進化迭代次數N時，停止進化，輸出問題的最優解。

3 算例仿真

3.1 算例說明

假設某地有一個調配中心(編號為0)，突發事件發生后，有15個地區(編號為1,2,…,15)受災情況比較嚴重，當地應急物資嚴重不足，急需得到合理的配送。調配中心和受災點的位置、受災點的需求量、時間窗以及卸貨時間已知，具體的數據如表1所示，混合遺傳算法中的參數設置如表2所示。

表1 數據集

表2 混合遺傳算法中的參數設置

3.2 算法比較

借助MATLAB R2014a編程軟件，結合算例數據，分別用遺傳算法和本文混合遺傳算法對所建的模型進行求解，求解結果如下所述。

用遺傳算法優化配送路徑時，優化過程如圖6所示，最優的配送方案路線如圖7所示。

圖6 遺傳算法的優化過程

圖7 基于遺傳算法的最優配送路線

用設計的混合遺傳算法優化配送路徑時，首先由節約算法求解得到的初始配送方案路線如圖8所示；隨后的優化過程如圖9所示；最終得到的最優配送方案路線如圖10所示。

圖8 基于節約算法的初始配送路線

圖9 混合遺傳算法的優化過程

圖10 基于混合遺傳算法的最優配送路線

遺傳算法和混合遺傳算法仿真結果對比如表3所示。

表3 仿真結果對比

3.3 結果分析

通過對比遺傳算法和混合遺傳算法優化的過程可知，用節約算法、遺傳算法、大規模鄰域搜索算法結合設計出的混合遺傳算法在進化到11代時即可達到最優解，而遺傳算法在進化到85代才達到最優解。通過對比遺傳算法與混合遺傳算法優化的結果可知，混合遺傳算法無論是在用車數量上、運輸距離上，還是耗費成本上都比遺傳算法優化的結果好。由此可見，本文中設計的混合遺傳算法在優化過程和優化結果上都具有一定的優越性。

4 結論

針對突發事件下應急物資配送路徑規劃問題進行研究，在滿足各受災點需求的前提下，以配送車輛的固定成本、運輸成本、違反最大載重量以及受災點右時間窗的懲罰成本之和最小為優化目標，構建了時間窗約束下的應急物資配送路徑規劃模型，并設計了混合遺傳算法對模型進行求解，最后進行了算例仿真。借助MATLAB軟件分別用遺傳算法和本文混合遺傳算法對模型進行求解，并對兩者的結果進行了對比。

(1)用節約算法、遺傳算法 、大規模鄰域搜索算法設計出來的混合遺傳算法不僅求解結果更優，而且在進化過程中能更早地達到最優解。

(2)構建的應急物資配送路徑規劃模型具有通用性且本文中設計的混合遺傳算法在求解模型時具有高效性，可為解決應急物資配送路徑規劃問題提供科學的決策依據。

在對應急物資的配送路徑進行規劃時，是在各受災點需求確定的情況下得出的配送路線。而在現實生活中，受災點的需求受突發事件種類的影響可能是不確定的、動態變化的，以及配送車輛在運輸過程中的交通條件也可能存在極大的不確定性，這些因素都將會影響應急物資配送路徑優化的結果。因此，考慮更多、更復雜影響因素的應急物資配送路徑優化問題將是一個拓展研究方向。