考慮道路約束的應急物資調度優化模型與算法

王付宇，張 康

(安徽工業大學 a.管理科學與工程學院;b.復雜系統多學科管理與控制安徽普通高校重點實驗室，安徽 馬鞍山 243002)

0 引言

近年來，災害時常發生，如2008年汶川大地震、2020年新冠疫情和2020年南方特大洪澇災害等，這些災害對人們的生命財產和安全帶來了巨大的威脅。因此，在重大災害發生后開展及時、有效的救援工作十分重要，而應急物資和車輛調度對災后救援和恢復有著重要意義。

針對災后應急物資和車輛調度問題，國內外學者進行了大量的研究。1998年，List等[1]首次在放射性危險物品運輸優化模型中引入了應急問題，為應急資源調度問題的研究奠定了基礎；王海軍等[2]考慮到不同應急響應階段和目標重要程度不同，通過決策者對總運輸時間和應急成本的動態賦權，實現了應急調度的動態決策；段曉紅等[3]針對城市路網下多事故應急救援工作的特點，構建雙層規劃模型，對應急車輛調度和交通疏散進行協同決策；王付宇等[4]等針對災害初期存在道路受損和救援物資不足的情況，以救援的公平性作為調度目標，使用步長遞減的天牛須算法進行求解；Yi W等[5]針對人員疏散問題和應急物資調度的運輸問題，設計了集成分布模型；Moreno A等[6]針對災害救援中車輛運力的可重復利用問題，設計了混合整數規劃啟發式方法。

上述研究大部分是基于單種配送工具的應急資源調度問題，但是在道路發生損毀的情況下，單種配送工具很難滿足現實需求。2010年，Hu Z H[7]使用改進免疫算法，求解基于救援網絡的集裝箱多式聯運問題；Fikar C等[8]針對選取陸運和空運協調運輸中轉點選擇問題，設計了一種決策支持系統，打通了應急救援工作的最后一公里；陳雷雷[9]建立了大規模突發事件下以受災點滿意度為目標的多車輛和多物資的物資優化調度模型；阮俊虎等[10]對應急響應中的“直升飛機+車輛”醫療物資聯合運送問題進行研究；Ruan J H等[11]為解決大型自然災害中的車輛和直升機聯運問題，構建了平衡的車輛-直升機聯運網絡；Erdemir E T等[12]為解決突發事件下陸-空聯合救援問題，提出了一種位置覆蓋模型和貪婪啟發式算法。

以上文獻大多未考慮災害初期運力不足和道路通行受約束等情況。而在現實情景下，由于災害的突發性，導致災害發生初期救援工具很難在短時間內集結。2013年，王旭平等[13]針對運力受限情況下的救援車輛路徑選擇和應急物資分配問題，構建了混合整數模型，使用遺傳算法求解模型。2020年，薛星群等[14]針對震后應急資源調度的特點，考慮道路通行受約束和運力受限等條件，構建多目標規劃模型，并使用改進的NSGA-II算法求解模型。但是該研究并未考慮物資的裝卸時間或者準備時間，在特殊情況下，救援物資準備時間以及裝載時間對于整個救援過程來講不可忽視，該問題仍有改進的空間。因此本文在考慮道路通行受約束和運輸能力不足的條件下，將救援物資的裝卸或者救援工具的準備時間嵌入模型中，建立了考慮道路約束和多式聯運的應急物資調度模型。

對于多目標問題，求解方法大多使用NSGA-II算法，但NSGA-II算法存在收斂速度慢、種群多樣性差等[15-16]缺點。多年來，學者對NSGA-II算法進行了大量的研究。張國富等[17]提出一種NSGA-II與蟻群優化的混合智能搜索算法，并應用到多受災點、多需求點的應急物資調度問題中；李燕等[18]利用改進的NSGA-II對交叉口車輛延誤及機動車碳排放兩方面進行優化；王付宇等[19]提出了多目標蜂群算法，并將其應用到重大疫情事件下的應急資源調度問題中。從現有文獻分析可知，對NSGA-II算法仍有改進的空間，例如，如何根據研究問題的特殊性，設計相應算子以增加算法搜索空間等。

從檢索到的文獻可知，很少有使用自適應的NSGA-II算法求解多式聯運問題。為求解多目標應急調度模型，本文使用帶有自適應機制的NSGA-II算法對模型進行求解，所提算法對NSGA-II算法做出如下改進：1)設計自適應機制，綜合種群進化的橫向信息和縱向信息引導種群進化；2)針對聯合調度中多車輛配送的特點，設計隨機變鄰域搜索算子，對解空間充分搜索；3)將貪婪思想嵌入鄰域探索過程。

1 模型構建

1.1 假設條件

本文針對所建立的應急資源調度模型，作出如下假設：

1)受災點的位置和兩兩受災點之間的距離已知；

2)物資集散中心的物資量充足而且種類單一；

3)受災點的種類以及需求已知，并且各受災點僅能被訪問一次；

4)配送工具平均速度不變，運行時長不受限制。

1.2 模型構建

物資救援體系使用完全有向圖構建G=(V，A)，V表示所有節點的集合，V={0,1，…,n},其中v=0表示集散中心。V′=V/{0}表示所有受災點的集合。A={(i,j)|i,j∈V,且i≠j}表示救援物資網絡的弧集；K=K1∪K2表示所有運輸工具的集合，K1表示直升機集合，K2表示汽車運輸工具集合；Vc表示受交通約束的受災點的集合。

因此，救援物資調度模型為

(1)

F2=min(W+U+V)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

2 改進的NSGA-II算法原理

NSGA-II算法是解決多目標優化問題常用的算法之一，但經典算法搜索能力較弱并且收斂性較差，為了提高算法的收斂性和搜索范圍，提出了基于種群熵的自適應機制，充分利用進化的橫向和縱向信息。種群進化的橫向信息指種群層級的個體水平，某一階段種群進化的橫向信息包含所有個體目標函數值、Pareto層級數和不同Pareto層級中個體的數量。種群進化的縱向信息指以種群進化的代數為縱向時間軸，種群中非支配解集的分布狀況。

2.1 自適應機制

2.1.1 自適應交叉概率

遺傳算法中交叉概率和變異概率對算法收斂性和路經求解質量起著至關重要的作用[20]，而固定的交叉概率對種群進化很不利，眾多學者對交叉概率做了大量研究[21-22]。本文借鑒文獻[23-25]的設計思想，設計了自適應交叉概率公式。

pc=mean(pci)

(11)

(12)

其中，pc1為最大交叉概率；pc2為最小交叉概率；f′i為待交叉染色體中第i個目標函數值較大的個體；pc為個體的交叉概率，具體表示為所有目標函數適應度值的平均值；favgi，fmini，fmaxi為當前種群中第i個目標的平均值、最小值和最大值。

2.1.2 基于種群熵的變異概率

變異概率的大小一定程度上影響了種群進化的速度，因此本文借鑒文獻[26]中種群熵的概念，設計了自適應的變異概率，變異概率如式(16)所示。

(13)

(14)

(15)

pm=P0G(i)

(16)

當種群中所有個體都分布在某個子空間中時，由式(15)可知：Gimax最大值為ε。一般來說pmmax最大不超過0.2，因此本文取pmmax=0.2。因此ε=pmmax/p0max=0.33。不同方差下的變異概率如圖1所示。

圖1 不同方差下變異概率對比圖Fig.1 Comparison of variance probabilities under different variances

從圖1中任一曲線可以看出，變異概率在算法的前期處于較小的值，在算法的后期，變異概率的值穩定維持在0.08左右。通過變異概率對比圖可以看出，當δ=0.1時，變異概率在進化中期有著較大的探索空間，因此本文δ=0.1。

2.2 改進的交叉和變異算子

2.2.1 變異算子

設計合理的變異算子同樣是遺傳算法中的難點，本文結合配送工具資源可重復利用和多式聯運等特點，設計了隨機變異算子。隨機變異算子的描述如下：

第1種變異(random_v)：隨機從染色體中選擇一個未受到通行約束的受災點，隨機插入到該染色體中，判斷插入之后染色體路徑長度是否優化，若未優化，則重復選擇插入點，直到產生一個較優的解。

第2種變異(diff_v)：從兩個不同配送工具中選擇兩個受災點交換位置，若受災點是受到通行約束的，則在直升機配送路徑中選擇一個不受約束的受災點，然后進行交換位置。

第3種變異(road_v)：隨機選擇一個配送工具，對該配送工具的不同配送路徑中的兩個受災點進行交換，若交換之后路徑未得到優化，則重新選擇，直到路徑得到優化為止。

2.2.2 交叉算子

本文在順序交叉算子基礎上進行了改進，改進的順序交叉算子如下所示。

2.3 混合選擇策略

遺傳算法中如何從交配池中選擇合適的父代,以及如何選擇算子是值得關注的問題，本文使用式(17)和式(18)選擇父代個體。

(17)

(18)

其中，poprank為種群經過排序后第rank層級群體；T為最大迭代次數，即T=tmax；T1=β*T；T2=(1-β)T，通常β=0.382或者β=0.258；random_v、diff_v和road_v為設計的3種變異算子。

2.4 改進算法流程

改進算法的流程如下：

步驟1：初始化參數，最大迭代次數T_max、最大最小交叉概率pc1和pc2以及最大貪婪搜索次數t_max，產生初始種群；

步驟2：計算個體適應度值；

步驟3：非支配排序，并選擇精英個體，形成父代種群；

步驟4：根據式(17)選擇交配個體，并進行交配，形成子代種群；

步驟5：根據式(16)計算變異概率；

步驟6：通過式(18)從子代種群中選擇變異個體，并使用隨機變異算子形成新個體；

步驟7：選出較優的個體，判斷貪婪搜索次數是否大于t_max，若滿足，則保存較優個體到新子代種群中，并轉到步驟8；否則，返回步驟6；

步驟8：合并父代和子代種群，并判斷進化次數是否大于T_max，若不滿足，返回步驟3；

步驟9：進行非支配排序，輸出非支配解集。

具體算法流程圖如圖2所示。

圖2 改進非支配快速排序算法流程圖Fig.2 flow chart of the improved non dominated quick sort algorithm

3 算例分析

3.1 算例數據和算法參數

本文采用的數據[14]如下，應急物資集散中心坐標(50,50)，20個受災點的坐標如表1所示，加黑字體為受約束的受災點。隨機指定3個受約束的受災點，兩架直升飛機，3輛貨車，配送工具的相關參數如表2所示。由于文獻[14]未考慮物資的裝卸時間和成本，因此本文對相關數據進行修改，在文獻[14]數據的基礎上增加了裝卸時間和成本。算法的測試環境為windows 10操作系統，4 G運行內存，intel四核2.5 Ghz，測試軟件選擇python 3.7版本。

表1 受災點位置數據Tab.1 Disaster location data

表2 配送工具參數Tab.2 Distribution tool parameters

本文種群中染色體的個數為100，演化的代數定為500，最大貪婪搜索次數設為100，pc1=0.9，pc2=0.7，pc3=0.5。獨立運行程序15次，任取其中一次的實驗結果，Pareto前沿如圖3所示，平均等待時間最小為50.37 min，總成本最小為2 142.67萬元。從圖3中的變化趨勢可以看出，當平均等待時間減少時，總成本將會增加。并且當平均時間變化很小時，總成本會大幅度攀升。

圖3 改進NSGA-II算法Pareto前沿Fig.3 Pareto frontier of improved NSGA-II

3.2 實驗結果與分析

針對決策人的不同偏好和模型的兩個目標，時間偏好型下的時間最小調度結果如表3，經濟成本型下的調度結果如表4所示，從表3和表4可以看出，當平均等待時間最小時，總的調度成本高達4 472.96萬元；當總成本最小時，平均等待時間為145.38 min。

表3 平均等待時間最小下的調度計劃Tab.3 Schedule with minimum average total waiting time

表4 總成本最小下的調度計劃Tab.4 Schedule with minimum cost

為檢驗所提算法的有效性，通過與文獻算法和NSGA-II算法進行對比，將3個算法的種群數量和迭代次數均設為500，NSGA-II和文獻算法的變異和交叉概率分別設為0.1和0.8。對比結果如圖4所示。

圖4 算法的對比圖Fig.4 Comparison of different algorithms

為避免求解的偶然性，進行15組重復測試，表5中F1的單位為min，F2的單位為萬元，由表5的數據可知：所提算法得到的平均等待時間的均值為44 min，比文獻[14]和NSGA-II分別優化了6.3%和8.4%；總成本方面，比文獻[14]和NSGA分別優化了1.6%和18.21%；穩定性方面，本文所提算法都要優于另外兩種算法。

表5 不同算法的對比結果Tab.5 Comparison results of different algorithms

3.3 算法的性能分析

為測試改進算法相關性能[27]，本文采用分布性指標(SP)和覆蓋范圍(MS)來衡量算法的性能。

多樣性SP指標是衡量種群多樣性的一個指標。種群分布越均勻，則SP指標越小。SP指標如式(19)所示。

(19)

非支配解集覆蓋范圍MS指標，衡量Pareto前沿的覆蓋范圍，如式(20)所示。

(20)

為了說明本文算法在多樣性和分布性能的效果，重復運行每個算法30次，得到MS和SP指標的均值和方差，具體數據如表6所示。

表6 SP和MS指標比較Tab.6 Comparison of SP and MS indexes

表6中SP和MS指標數據表明，所提算法結果比傳統算法更優，與文獻[14]算法相比，結果不比其差。

圖5a為文獻[14]和所提算法中非被占優解集的對比圖，圖5b為所提算法與文獻[14]中非被占優解集真實占比對比圖。由圖5a和圖5b分析可知，文獻[14]的種群含有大量的重復解。從圖5中非被占優解集占比收斂點可以看出，所提算法在進化后期有著較強的擾動能力。證明了所設計的交叉算子和消除重復解策略取得了效果。

圖5 非被占優解變化趨勢Fig.5 trend of non-dominant solutions

圖6顯示所提算法得到的MS指標值大于文獻[14]數據，表明在種群進化過程中，改進NSGA-II算法所得種群覆蓋范圍更大，搜索范圍更大。種群覆蓋范圍更大是因為設計的變異和交叉算子大大增強了算法的搜索能力。圖7表明，與文獻[14]相比，所提算法所得SP值更小、一致性更高。

圖6 不同算法MS值對比圖Fig.6 Comparison of MS values of different algorithms

圖7 SP值對比圖Fig.7 Comparison of SP values

4 總結

本文主要研究在重大突發事件時，運輸能力受限制和道路通行受到約束的情境下的應急調度問題。在求解模型時，本文結合多式聯運的特征，通過自適應機制引導種群進化。根據種群進化的橫向信息和縱向信息設計了自適應交叉和變異公式，以加速種群進化，提高算法效率。本文結合配送工具可重復利用以及多車輛調度的特點，設計了多種變異算子以增加算法的鄰域搜索能力。最后通過算例和相關指標表明，與其他算法相比較，所提算法在改進種群多樣性和分布性方面有著較好的結果。

在重大突發事件下，需求的不確定性、受災點群眾的服務滿意度和公平性等問題同樣是決策者考慮的重要因素，因此，在突發事件下，考慮受災點的社會公平性、滿意度以及綠色調度等可能是未來的研究重點。算法方面，未來調度問題往往是大規模、高維的，因此，使用多目標算法與AI的混合算法解決大規模高維問題，將是未來研究的熱點。