基于變長基因型遺傳算法的多供應點應急物資調度優化

摘要：如何及時、高效地調度應急物資以減小突發事件帶來的傷害成為社會關注的焦點問題。在綜合考慮新冠肺炎疫情這類特殊突發事件特點的前提下，構建了一類多供應點多式聯運應急物資調度網絡，并以運輸成本最低、時間懲罰最少、配送員被感染風險最小為優化目標建立了一類多目標調度優化模型。考慮到基于聚類思想的優化算法在解決多供應點，尤其是多目標調度優化問題中縮減可行域方法科學性存疑的局限性，提出了一類考慮完全可行域思想的變長基因型混合小生境遺傳算法，并借助23個基準測試實例驗證了這一算法的有效性，更新了部分實例的現有最優解。在此基礎上，通過比較多供應點應急物資多式聯運算例中四類遺傳算法的仿真結果進一步驗證了混合小生境等改進策略的優越性。

關鍵詞：變長基因型混合小生境遺傳算法；應急物資調度；多供應點；多式聯運；完全可行域

中圖分類號：TP18文獻標志碼：A

文章編號：1001-3695（2022）04-032-1148-07

doi：10.19734/j.issn.1001-3695.2021.09.0419

Scheduling optimization of emergency supplies with multi-supply points based on

variable length genotype genetic algorithm

Wu Fan1，Yang Bing1，2，Hong Si1

（1.School of Management Science amp; Engineering，Anhui University of Technology，Ma’anshan Anhui 243032，China；2.Anhui Taier Heavy Industry Co.，Ltd.，Ma’anshan Anhui 243000，China）

Abstract：How to dispatch emergency supplies timely and efficiently and reduce the damage caused by emergencies has become the focus of social attention.On the premise of considering the characteristics of special emergencies such as the epidemic situation of COVID-19，this paper constructed a kind of emergency supplies scheduling network of multi-supply points and multimodal transportation.Taking the lowest transportation cost，the least time penalty and the minimum risk of infection of dispatchers as the optimization objectives，it established a kind of multi-objective optimal scheduling model.In view of the limitation of the optimization algorithm based on clustering in solving multi-supply points，especially multi-objective scheduling optimization problems，the paper proposed a kind of hybrid niche genetic algorithm for variable length genotypes considering the idea of full feasible regions，which could avoid the problem above by restoring the search range of the solution to the fully feasible regions.The experiment results of 23 benchmark instances show that the optimization performance of the algorithm is stronger and it can search better solutions than best-known solutions of some examples.On this basis，the simulation results of four kinds of genetic algorithms in emergency supplies scheduling examples of multi-supply points and multimodal transportation come to a conclusion that the improved strategies such as hybrid niche are superior.

Key words：hybrid niche genetic algorithm for variable length genotypes；emergency supplies scheduling；multi-supply points；multimodal transportation；full feasible regions

0引言

近年來，各種自然災害、公共衛生事件時有發生，嚴重威脅著人類的生命安全。尤其2019年12月以來，新冠病毒COVID-19疫情［1］的爆發，更是給全世界帶來了巨大的挑戰。面對突發事件，如何實現及時、高效的應急物資調度，保證物資的合理分配已成為全人類愈加關注且亟待解決的問題。

突發事件中，單個供應點的應急物資往往不能滿足復雜背景下的應急需求，為此，應考慮到多供應點調度優化問題的重要性。Cassidy等人［2］于1972年首先提出了多車場車輛路徑問題（multi-depot vehicle routing problem，MDVRP），由于該問題中多車場概念的提出可為運輸管理、應急物資調度等領域內多供應點問題的研究提供思路，所以大量學者進行了相關研究。鄒彤等人［3］針對MDVRP提出了一種基于客戶的編碼方式并設計了遺傳算法，針對一個具體算例給出了問題的滿意解，該研究作為國內針對MDVRP最早的系統性研究，給出了MDVRP詳細的數學模型，但存在具體算法介紹與算例求解步驟介紹不夠詳盡等不足。張立峰等人［4］根據需求點的地理空間信息，將各需求點基于聚類的思想分配給各供應點，在此基礎上提出了一種遺傳算法，利用仿真結果證明了該算法的可行性及有效性。

通過以上文獻可知，目前用于解決MDVRP的方法大多是兩階段法，即第一階段通過一定的規則（如需求點與各供應點的距離長短等）進行聚類，將各需求點確定性地分配給各供應點進行服務（這決定了模型的解為定長基因型）；第二階段針對各個供應點進行需求點服務順序安排。這類處理手段是通過將MDVRP簡化成多個VRP子問題求解，使得求解空間縮減為原問題的部分可行域，減小搜索空間、降低復雜度。但是當MDVRP中加入了一些其他必要的現實約束，如在解決需求點有特定的服務時間窗或求解問題不僅僅考慮單一經濟性成本時，怎樣科學、準確地制定聚類規則抑或尋找其他更加有效的求解方法成為了解決該類問題的關鍵。

針對以上所提MDVRP的擴展問題也有學者進行了研究。 王旭坪等人［5］針對考慮碳排放與時空距離的多車場冷鏈配送問題，基于時空距離對需求點進行聚類，并根據聚類結果采用改進模擬退火算法得到優化路徑； 周鮮成等人［6］考慮時變速度和實時載重對車輛油耗和碳排放的影響，構建了多車場綠色車輛路徑模型（multi-depot green vehicle routing problem，MDGVRP），針對該模型，第一階段基于距離采用了K-means方法將顧客分配給不同的車場，第二階段設計了一種改進的蟻群算法進行問題求解；Bae等人［7］針對考慮時間窗的MDVRP（multi-depot vehicle routing problem with time windows，MDVRPTW）將每個需求點按照距離各供應點路程長短分配到每個供應點，在此前提之下再考慮時間窗約束，并提出一種遺傳算法來尋找問題的近似最優解；Zhen等人［8］針對考慮發貨期的MDVRPTW提出了一種混合粒子群算法和混合遺傳算法求解，通過大量的數值實驗驗證了所提模型和求解方法的有效性。

通過以上學者對MDVRP各類擴展問題的求解分析不難得出，即使在求解問題不僅僅包含單一運輸成本時，類似標準MDVRP，一些學者依然試圖尋找更加高效的聚類方法將需求點分配至各供應點以達到簡化問題的目的。但實際上，當問題的求解目標不止一個且不具備一致性時，不能繼續根據某一個目標將需求點進行聚類。例如，對于少有研究但又具有較強現實意義的多供應點應急物資調度問題［9，10］，與運輸成本相比，往往更加注重物資的及時到達。在多供應點情形下解決這類不僅僅考慮運輸成本的弱經濟性問題時，如何科學、精確地找到泛化能力較強的求解方法是具有挑戰性的。另外，多式聯運已經在各類經濟活動中由于其高效、靈活、經濟等特點被廣泛應用，但將其運用在應急物資調度這類弱經濟性問題中的研究還較少，隨著突發事件愈加頻繁，單一的運輸方式往往不能滿足復雜應急情況下的實際需求，多式聯運可以通過有效利用物資、改善交通結構來提高應急物資調度效率。

綜合以上文獻，研究人員針對應急背景下的多供應點調度研究較少，且現有研究方法缺乏泛化性、高效性；此外，將多式聯運應用在應急調度中的研究也較少。基于此，本文建立了一類應急背景下的多供應點多式聯運調度模型，考慮到現有解決多供應點弱經濟性調度類問題的方法缺乏一定泛化能力的局限性，提出了一種泛化能力更強的變長基因型混合小生境遺傳算法，并通過考慮車輛最大載重的MDVRP基準測試實例（經濟類問題）驗證了該算法的有效性。在此基礎之上以多供應點應急物資多式聯運問題（弱經濟類問題）為例，進一步驗證了混合小生境技術在尋優過程中的優越性。

1模型構建

1.1問題描述與假設

本文研究新冠肺炎疫情背景下的多供應點多式聯運應急物資調度問題，該問題可歸結為一類特殊的MDVRP，它與傳統MDVRP的主要區別是：a）決策者不再以經濟性成本作為主要目標，更加注重應急物資的及時到達以及配送人員的生命安全；b）考慮到高效、靈活等優點，采取多式聯運模式，進一步提高應急響應效率；c）在抗擊新冠肺炎的物資調度過程中，需求點應急物資的極度匱乏使得調度模型的時間約束呈現出特殊性；d）考慮到配送員存在被感染新冠肺炎的風險，其生命安全也成為必須考慮的重要因素。

綜上所述，問題描述如下：由多個物資儲備充足且具備多種運輸方式的供應點向多個需求點配送醫療物資；每個需求點均有一個已知且固定的非負需求；各需求點希望盡可能快地接收物資，且存在一定的卸貨時間；若物資未按時到達，各需求點的單位時間損失不同；裝載物資的各運輸工具從各供應點同時出發，完成任務回到出發點，不循環配送；配送員存在被感染的風險。在此基礎上找出配送路徑短、時間懲罰少、配送員被感染風險低的應急物資調度方案。顯然，應急背景下的多供應點多式聯運問題具有弱經濟性。該問題考慮如下假設：

a）配送應急物資的運輸工具有容量限制。其中，對于同一個供應點，不同類型的運輸工具最大載荷不同，同種類型的運輸工具最大載荷相同；對于不同供應點，同種類型與不同類型的運輸工具、最大載荷均不同。

b）不同運輸工具在各路段以不同的速度保持勻速行駛。

c）配送員在配送過程中存在被感染的風險。

1.2模型參數

模型參數如表1所示。

令ETi=0（i=1，2，…，N），即到達需求點i的時間在LTi之前一律認為符合需求點需求，否則接受懲罰（該部分不同于一般調度類問題，決策者希望應急物資盡快到達需求點，因此不考慮提前到達產生等待成本的情況）；此外，設emlij是供應點m、運輸工具l、i點人口密度μi、j點人口密度μj以及i點現階段感染人數λi、j點現階段感染人數λj的函數emlij（m，l，μi，μj，λi，λj），且同時滿足以下條件：

（emlij）（μi），（emlij）（μj），（emlij）（λi），（emlij）（λj）≥0

具體eij的函數形式可根據世界衛生組織2009年修訂的流行病警告分級標準以及ISO 31000：2018，Risk management-Guidelines國際標準，考慮新冠肺炎疫情的特性加以制定。令

Klm=［∑Ni=1gi/qlm］+1，m，l，［］表示Gauss mark（1）

Cmlklmij=clm×dij×caplklmm，i，j∈{1，2，…，N+M}，m，l，klm（2）

Emlij=e×emlij，i，j∈{1，2，…，N+M}，m，l（3）

Ti=Ti-1+wi-1+d（i-1）ivlm，i∈{2，3，…，N}，m，l（4）

wi=giui，i∈{1，2，…，N}（5）

tmlij=dijvlm，i，j∈{1，2，…，N+M}，m，l（6）

Pi（Ti）=max{bi（Ti-LTi），0}，i∈{1，2，…，N}（7）

xmlklmij為決策變量，表達式如下：

xmlklmij=1m點第l種運輸工具中的第k個從i點配送物資至j點0否則 （8）

1.3模型建立

基于以上問題描述與模型參數，建立如下模型：

min Z1=∑N+Mi=1∑N+Mj=1∑Mm=1∑Lml=1∑Klmklm=1Cmlklmijxmlklmij（9）

min Z2=∑N+Mi=1∑N+Mj=1∑Mm=1∑Lml=1∑Klmklm=1Emlijxmlklmij（10）

min Z3=∑Ni=1Pi（Ti）（11）

∑Nj=1∑Klmklm=1xmlklmij≤Klm，i∈{N+1，N+2，…，N+M}，m，l（12）

∑Nj=1xmlklmij≤1，i∈{N+1，N+2，…，N+M}，m，l，klm（13）

∑N+Mi=N+1xmlklmij≤1，j∈{1，2，…，N}，m，l，klm（14）

∑N+Mj=1∑Mm=1∑Ll=1∑Klmklm=1xmlklmij=1，i∈{1，2，…，N}（15）

∑N+Mi=1∑Mm=1∑Ll=1∑Klmklm=1xmlklmij=1，j∈{1，2，…，N}（16）

∑N+Mi=1∑Mm=1∑Lml=1∑Klmklm=1xmlklmij（Ti+wi+tmlij）=Tj，j∈{1，2，…，N}（17）

gi≤qlm，i∈{1，2，…，N}，m，l（18）

∑Nr=1∑N+Mi=1∑N+Mj=1grxmlklmij≤qlm，m，klm（19）

∑N+Mj=N+1xmlklmij=0，i∈{N+1，N+2，…，N+M}，m，l，klm（20）

∑N+Mj=N+1xmlklmji=0，i∈{N+1，N+2，…，N+M}，m，l，klm（21）

其中：目標函數式（9）表示運輸成本最低；目標函數式（10）表示因感染風險造成的應急成本最低；目標函數式（11）表示因延遲到達需求點造成的懲罰成本最低；約束條件式（12）表示任意供應點派出的任意類型運輸工具的數量不超過該供應點該類型運輸工具的擁有量；約束條件式（13）（14）表示對于任一種運輸工具的任一個而言，其狀態為出動或不出動；約束條件式（15）表示以需求點為中轉出發點的運輸工具有且只能有一個到達下一個需求點或原供應點；約束條件式（16）表示以需求點為到達點的運輸工具，有且只能有一個來源于原供應點或上一個需求點；約束條件式（17）表示從i點到達j點，到達j點的時間為到達i點的時間與在i點的卸貨時間以及i點到j點的行駛時間之和；約束式（18）表示任意需求點的需求量不超過任意運輸工具的最大載荷；約束式（19）表示任意運輸工具服務的需求點總需求不大于該運輸工具最大載荷；約束式（20）（21）表示運輸工具不能從供應點出發直接到達另一供應點，即每個運輸工具一旦派出，必須服務需求點。

2變長基因型混合小生境遺傳算法

2.1基于需求點隨機分配的變長初始解生成

研究人員通常采取基于聚類的思想解決MDVRP及其擴展問題。然而，由于聚類規則在很大程度上縮小了原問題的可行域，但縮小可行域方法的科學性有待商榷，使得在部分可行域內尋優結果的精度存疑。尤其是在MDVRP的弱經濟性擴展問題（如多供應點應急物資調度問題）中，基于聚類的思想不能很好地體現問題目標的弱經濟性特點，這類方法的尋優結果是否合理有待進一步論證。基于此，針對多供應點調度優化類問題，本文提出一類“需求點先隨機分配給供應點，再隨機分配給各運輸工具”的變長初始解生成策略，保證了初始解在完全可行域內生成。

2.2混合小生境遺傳算法

第一階段基于需求點的隨機分配使得模型的解成為變長基因型，這在一定程度上提升了模型求解的難度，因此針對這類問題需要有針對性地設計可行且高效的新的求解算法。

求解該類NP-hard問題的方法多為精確算法［11～15］和啟發式算法。精確算法能有效求得應急調度模型的最優解，但由于其計算量一般隨著問題規模的增大呈指數增長，即存在維度爆炸的現象，應用范圍有限，所以學者們將尋找解決問題方法的主要精力用在構造高質量解的元啟發式算法上。

遺傳算法（genetic algorithm，GA）是模擬生物在自然環境中的遺傳和進化過程而形成的智能優化算法，GA因能有效解決NP-hard問題而被廣泛應用于調度優化類問題的求解。研究表明，GA由于其高效的內在并行性與可擴展性在解決定長基因型問題中表現良好，但尚未發現GA在解決變長基因型問題中的研究；此外，傳統GA在進行選擇操作時，可能存在個體適應度遠高于種群平均適應度的染色體被大量復制的現象，這在一定程度上破壞了種群的多樣性，產生近親繁殖現象，造成算法早熟；另外，傳統GA具有較強的全局尋優能力，但存在局部搜索能力較弱的缺陷。基于以上分析，本文提出了一種變長基因型混合小生境遺傳算法（hybrid niche genetic algorithm for variable length genotypes，VHNGA），首先針對變長基因型問題提出改進的交叉與變異算子以保證遺傳算法的可行性和高效性；其次，針對傳統遺傳算法易陷入早熟的特點提出了一種基于排擠機制的小生境技術，以雙種群并行搜索來提升種群多樣性，在一定程度上避免了算法早熟現象；另外，針對傳統GA局部搜索能力較弱的現象，在小生境技術中引入模擬退火思想中的Metropolis準則形成混合小生境技術，使得種群多樣性得以增加的同時又進一步加強了算法的局部搜索能力。

2.2.1改進交叉算子

如何根據變長初始解設置可行且高效的鄰域結構決定了算法的尋優能力，而GA產生新解的過程在很大程度上依賴于交叉算子。對于一般定長基因型問題的交叉方式有單點交叉、多點交叉以及部分匹配交叉等。顯然傳統的定長基因型交叉方式無法作為有效的鄰域結構更新變長可行解，更無法保證算法的收斂性。

基于此，本文以多供應點調度優化問題為例提出一種針對變長（或定長）基因型問題的改進交叉算子（定長基因型是變長基因型的一種特殊情況，以下偽碼部分已作標注），該交叉算子首先保證了變長可行解的有效更新，其次使得產生的新解在充分保證搜索空間的基礎上保留了雙親的部分優良特征，加快了算法的收斂速度。交叉操作完成后種群記為cross_ pop，偽碼如算法1所示。

算法1變長基因型改進交叉算子

輸入：父代1pop1，父代2pop2，供應點數量M，需求點數量N等。

輸出：子代1cross_ pop1，子代2cross_ pop2。

1cross_ pop1←pop2；

2x←選定pop1的一個供應點；

3updatecross_ pop1；

4for k=1：（M-1）//遍歷剩余供應點

5update cross_ pop1； //刪除與第x個供應點服務序列相同的序號

6end for

7if cross_pop1中各供應點服務的需求點數量N1=N

8if不滿足遍歷約束

9update cross_ pop1；//此時退化成定長基因型問題

10else

11if cross_ pop1運輸工具個數u滿足約束

12update cross_pop1；/*保證第x個供應點中每個運輸工具都至少服務一個需求點的前提下，選取一些需求點提供給cross_ pop1中狀態為sts的運輸工具服務以保證不存在狀態為sts的運輸工具*/

13else

14update u amp; return line 12；

15end if

16end if

17else if N1＜N//此時子代1存在某些需求點未被服務

18ifu==0

19update cross_ pop1；/*將缺乏服務的需求點序號隨機排列，并逐次隨機插入N-1個（除x點之外）供應點中任意類型運輸工具的任意一個讓其服務*/

20else if u≠0

21if u==N-N1

22update cross_pop1；/*將缺乏服務的需求點序號隨機排列，依次插入N-1個（除x點之外）*/

23else if u＜N-N1

24update cross_ pop1；/*先執行行22，然后將剩下缺乏服務的需求點執行行19*/

25 else if u＞N-N1

26update cross_ pop1；/*將u減小至u=N-N1，并執行行22*/

27end if

28end if

29end if

30交換父代1與2，執行行1～29，形成子代2cross_ pop2。

此外，交叉算子中交叉概率Pc的取值很大程度上影響著算法的尋優性能。Pc設置過大，會導致個體適應度波動較大；Pc設置過小，則導致搜索緩慢甚至早熟收斂。因此，本文基于自適應思想對Pc進行改進，公式如下：

Pc=Pcmax-（Pcmax-Pcmin）×（f′-favg）fmax-favgf′≥favgPcmaxf′＜favg （22）

其中：Pcmax表示預設最大交叉概率；Pcmin表示預設最小交叉概率；f′表示兩個父代染色體適應度較大的適應度值；fmax表示種群最大適應度值；favg表示種群平均適應度值。

2.2.2改進變異算子

變異和交叉算子相互配合、相互競爭可以加強算法的尋優能力。顯然，針對定長基因型問題的傳統變異算子已不能適用于變長基因型問題的研究；另外，傳統的變異算子形式單一，使得當前解的尋優方向單一，尋優效果欠佳。本文以多供應點調度優化問題為例，提出一種解決變長（定長）基因型問題的隨機鄰域搜索變異算子。多種鄰域變異算子的提出可為算法提供更加多元化的尋優方向，也為算法收斂到更優解提供了更大的可能。具體鄰域結構如下：

變換1將某一需求點序號（該需求點所在運輸工具服務且不僅僅服務該需求點）插入該需求點所在供應點的任一運輸工具路徑中。

變換2將某一需求點序號（該需求點所在運輸工具服務且不僅僅服務該需求點）插入除該需求點所在供應點之外任一供應點的任一運輸工具路徑中。

變換3將某一需求點序號與該需求點所在供應點服務的另一任意需求點序號交換位置。

變換4將某一需求點序號與除該需求點所在供應點之外任一供應點服務的另一任意序號交換位置。

變換5在滿足服務需求點個數大于1的任一供應點任一運輸工具中，任意選擇兩個不同節點位置a與b，（bgt;a+1），保持a之前與b之后需求點順序不變，將a與b之間的序號翻轉，得到新的服務序列。

當滿足變異操作發生的條件時，隨機選擇五種鄰域中的一種進行變異操作，完成變異操作的種群記為mutation_pop。

此外，類似交叉概率Pc，設置自適應變異概率Pm如下：

Pm=Pmmax-（Pmmax-Pmmin）×（f-favg）fmax-favgf≥favg

Pmmaxf＜favg （23）

其中：Pmmax表示預設最大變異概率；Pmmin表示預設最小變異概率；f表示某個體適應度值。

2.2.3混合小生境技術

為進一步避免算法的早熟現象，提出一種基于模擬退火思想和雙種群并行搜索的混合小生境技術，具體如下：隨機選取種群規模為popsize的初始種群pop中n個（n≤popsize）適應度較優的個體記為種群1Niche；將后續進行選擇、交叉、變異、約束檢測并按適應度優劣排序之后的新種群記為種群2n_ pop。將n_ pop中適應度最優的個體視為排擠成員，并引入模擬退火思想中的Metropolis準則，根據該種群中其他個體與該排擠成員之間的相似性（可用個體編碼串之間的海明距離來度量，注：當編碼為變長基因型時，可將各供應點的服務順序從編碼串中取出并計算海明距離），以概率Pj來排擠一些與排擠成員相似的個體。Pj公式如下：

Pj=e-Hmj-HmcTj（24）

其中：Hmc表示預設的最佳海明距離；Hmj表示n_ pop中第j個個體（j=2，3，…，popsize）與排擠成員之間的海明距離；Tj為第j次迭代的動態溫度；令初溫Tmax=100，終溫Tmin=0.01，則Tj按以下方式自適應變化：

Tj=Tmax-Tmax-Tminpopsize×j（25）

以上基于Metropolis準則的排擠操作可使得與最優個體較為相似但適應度較優的個體以一定概率保留，該類個體優良的解的結構可能在鄰域更新方式下產生更好的可行解；針對與最優個體較為相似但適應度較差的個體，被替換概率隨著適應度降低而逐漸增大，最終收斂于1。根據以上操作將確定被排擠的個體替換成Niche種群相應位置的個體，形成種群f_ pop，并將f_ pop更新為下一次迭代的初始種群pop，完成混合小生境處理。

以上改進過程利用了不同種群之間的個體信息，在保證種群整體適應度的基礎上減少了該次迭代更新后種群內相似個體的數量，增加了種群多樣性，在一定程度上避免了算法早熟。偽碼如算法2所示。

算法2混合小生境技術

輸入：初始化種群Niche、種群n_ pop、最佳海明距離Hmc等。

輸出：優化種群f_ pop。

1f_ pop←確定n_ pop的排擠對象；

2for j=2：popsize

3計算第j個個體與第1個個體之間的海明距離Hmj；

4if Hmj≤Hmc

5Tj=Tmax-Tmax-Tminpopsize×j；

6if rand≤e-Hmj-HmcTj；

7更新n_ pop（j）←Niche（［jpopsize×n］+1），并更新f_ pop（j）；

8else

9更新f_ pop（j）←n_ pop（j）；

10end if

11end if

12end for

2.2.4算法流程

VHNGA流程如圖1所示。

3實驗仿真及分析

3.1VHNGA在MDVRP中的應用

由于本文所提模型在MDVRP的基礎上擴展而來，為了驗證本文算法的有效性，首先討論其在解決MDVRP（經濟類問題）中的應用。從已有文獻中提取了23個MDVRP基準測試實例，所有實例與對應的已知最知名解均可在以下網站獲取：http：//neo.lcc.uma.es/vrp/vrp-instances/multiple-depot-vrp-instances/。將VHNGA的仿真結果與CoES ［16］、ILS ［17］以及HAC［18］算法進行比較，表2給出了不同算法對應的仿真結果和相對分析誤差（relative percent deviation，RPD）。如文獻［19］所指出的，程序的運行時間不僅依賴于計算機的CPU，而且還依賴于操作系統和采用精度等因素，因此不包括運行時間的比較。RPD公式如下：

RPDij=Bestij-BKSjBKSj×100%（26）

其中：Bestij表示使用第i個算法對第j個實例得到的計算結果；BKSj表示第j個實例的已知最知名解；RPDij表示使用第i個算法對第j個實例得到的計算結果與第j個實例已知最知名解的相對分析誤差。

由表2整體分析可知，從平均PRD指標來看，VHNGA表現最好（0.37%），其次分別是HAC（0.72%）、ILS（1.20%）、 CoES（1.96%）；從匹配到已知最知名解的個數來看，VHNGA尋優性能最好，有13個實例可以匹配到已知最知名解（且更新了實例7的最知名解），其次分別是HAC（8個）、ILS（6個）和CoES（4個）。

另外在解決MDVRP時，多數學者為了驗證算法的有效性給出了類似表2的數據結果，還有少數學者給出了尋優結果對應的路徑方案，以上做法均在一定程度上驗證了研究的有效性。但研究發現，針對具體算例，還設有學者給出仿真迭代過程，這樣重視結果忽略尋優過程的做法，使得對算法的評價結果具有一定的片面性。

基于以上分析，本文以實例1（4個供應點，50個需求點）與實例7（4個供應點，100個需求點）為例，采用VHNGA分別給出了兩實例的迭代曲線與尋優路徑。圖2為本文算法針對算例1的仿真結果，其中（a）為算法迭代曲線，（b）為尋優所得路徑方案，且實心矩形表示供應點，空心圓表示需求點；圖3為本文算法尋優所得算例7已知最知名解的仿真結果，（b）中的路徑方案由于需求點數量較多且分布較集中，各點序號未標出。另外，由于本文算法更新了算例7的已知最知名解，所以在圖4中給出了相應的仿真結果，其中（b）給出了優化后的路徑方案，且該方案與已知最知名方案的路徑區別部分用虛線標出。

針對算例1，由于算例規模適中，設置種群規模為200，迭代次數為1 000。從圖2（a）中可以看出，算法前期尋優效果較優，目標函數值降幅較大，后期不斷跳出局部最優，最終收斂到已知最知名解。

針對算例7，由于算例規模相對較大，圖3及4尋優過程中均設置種群規模為200，迭代次數為2 000。從圖3（a）和圖4（a）來看，在個體極值方面，算法全局尋優性能較優，圖3最終收斂到已知最知名解885.80，但圖4收斂到了更優值884.66；在群平均值方面，兩曲線的群平均值靠近但不貼近個體極值，說明在保證一定種群多樣性的基礎上，種群整體水平較優。從圖3（b）和圖4（b）來看，與已知最知名路徑相比，優化后的路徑方案由于采用了高效的改進交叉算子與隨機鄰域搜索變異算子（尤其是后者），在已知最知名路徑的基礎上調整了其中一個供應點一輛運輸工具的服務順序，達到了更優的路徑方案，已知最知名路徑中該部分路徑順序為：101-60-99-37-98-85-93-84-101，本文更新路徑中該部分路徑順序為：101-60-99-93-98-37-85-84-101（注：整數1～100表示需求點，101表示供應點）。

3.2VHNGA在多供應點應急物資多式聯運中的應用

3.2.1目標函數處理

本文研究的多供應點應急物資多式聯運問題是一類實現多個目標函數最小化的問題，解決這類多目標問題的思路，可以通過線性加權法首先確定目標函數的權重，進而將其轉換為單目標問題來處理。例如，可將以上問題轉換為單目標問題：

min Z=ω1Z1+ω2Z2+ω3Z3（27）

其中：ω1、ω2、ω3滿足非負性與歸一性。考慮到新冠肺炎疫情背景下多供應點應急物資多式聯運問題的特殊性，本文將權重設置為ω1=0.2、ω2=0.3、ω3=0.5。

3.2.2參數信息

存在25個需求點（N=25）需要從兩個供應點（M=2）緊急配送口罩。各供應點運輸工具從早上6點同時出發，其中，供應點1可提供的運輸工具有兩種（L1=2），即飛機運輸以及貨車運輸；供應點2由于不具備飛行條件僅能提供貨車運輸（L2=1）。由于部分地區疫情更加嚴重，存在四個需求點（分別為1、11、15、16需求點）距離供應點距離較遠、需求量較大且需求更加緊急。各節點的坐標、需求量及時間窗等信息如表3所示。各供應點運輸工具信息如表4所示。

3.2.3仿真實驗

為了進一步體現VHNGA改進策略的有效性，本文針對以上多供應點應急物資多式聯運問題給出了四種變長基因型遺傳算法，分別為變長基因型傳統遺傳算法（genetic algorithm for variable length genotypes，VGA）、變長基因型自適應遺傳算法（adaptive genetic algorithm for variable length genotypes，VAGA）、變長基因型小生境遺傳算法（niche genetic algorithm for variable length genotypes，VNGA）以及VHNGA，各變長基因型遺傳算法種群規模均為200，迭代次數均為500，其他參數如表5所示。

以上四種算法迭代曲線如圖5所示，目標函數單位為元。從圖5可以看出，VGA、VAGA、VNGA、VHNGA尋優所得應急調度總成本分別為428 505.61元、369 065.44元、325 131.18元以及295 815.51元。造成這些尋優結果差異的原因在于表5中不同算法的參數設置。對比VAGA與VGA曲線可知，VAGA較VGA迭代前期目標函數值減小幅度更大；VGA大約在300次迭代陷入局部最優直至結束，VAGA在大約400次迭代仍然具備跳出局部最優的能力，由此驗證了前文所述交叉和變異概率自適應處理使算法前期尋優能力與后期跳出局部最優的能力得到加強。對比VNGA與VAGA曲線可知，加入小生境技術，增加了種群多樣性，使得算法前期尋優能力更強，且收斂速度更快。在VNGA的基礎上引入模擬退火思想中的Metropolis準則形成VHNGA，相比VNGA，VHNGA對于與排擠成員相似但適應度較優的個體以一定概率保留，這使得在增加種群多樣性的基礎上又保留了部分精英個體，算法迭代前期尋優能力更強，且隨著迭代進程不斷跳出局部最優，直至大約450次迭代收斂。

綜上所述，本文提出的VHNGA較其他三種變長基因型遺傳算法在保證全局尋優的基礎上，增強了局部尋優能力，迭代前期具備更好的尋優能力，且迭代后期跳出局部最優的能力更強，這為決策者在考慮多供應點應急物資多式聯運問題時提供了更優的策略選擇。

4結束語

近年來，突發事件頻發，如何實現更加及時、高效的應急物資調度受到各界專家的廣泛關注。本文提出了一類以運輸成本最低、時間懲罰最少、配送員被感染風險最小為目標的多供應點應急物資多式聯運調度模型，并基于該模型，提出了一種求解多供應點調度類問題泛化能力更強的變長基因型思想，給出了VHNGA的算法架構，以MDVRP基準測試實例與多供應點應急物資多式聯運問題為例驗證了算法的有效性。在求解標準MDVRP基準測試實例時，將VHNGA運用到23個基準測試實例中，實驗結果表明，所提算法可以匹配到13個（且更新了1個）實例的現有最知名解，且RPD指標在所列算法中最低，所提算法在解決方案質量與穩定性方面均具有良好的整體性能。在求解多供應點應急物資多式聯運問題時，多個求解目標屬性的不一致導致無法采取某一確定的聚類規則簡化多供應點調度問題，變長基因型在需求點的隨機分配、運輸工具的種類與數量的使用等方面得以體現。針對一個具體算例，分別運用VGA、VAGA、VNGA、VHNGA求解，實驗結果進一步驗證了本文所提改進交叉、變異算子以及混合小生境處理技術的有效性。

未來研究可從以下方面進一步開展：一方面，變長基因型思想的提出為解決多供應點調度優化類問題提供了一種新的思路；另一方面，本文所提針對變長基因型可行解的改進交叉、變異算子可作為其他元啟發式算法的鄰域生成算子形成考慮完全可行域的其他元啟發式算法。在未來，所提出的想法可能被用于測試解決物流和供應鏈管理中其他組合優化問題的性能［20］，此外，隨著人們對社會安全可持續發展的日益關注，多式聯運將被更加廣泛地應用于現實生活中。

參考文獻：

［1］Guan Weijie，Ni Zhengyi，Hu Yu，et al.Clinical characteristics of coronavirus disease 2019 in China［J］.New England Journal of Medicine，2020，382（2）：1268-1280.

［2］Cassidy P J，Bennett H S.TRAMP：a multi-depot vehicle scheduling system［J］.Journal of the Operational Research Society，1972，23（2）：151-163.

［3］鄒彤，李寧，孫德寶，等.多車場車輛路徑問題的遺傳算法［J］.計算機工程與應用，2004，40（21）：82-83.（Zou Tong，Li Ning，Sun Debao，et al.Genetic algorithm for multiple-depot vehicle routing problem［J］.Computer Engineering and Applications，2004，40（21）：82-83.）

［4］張立峰，易萬里，劉曉蘭.基于兩階段算法的大規模成品油二次配送優化［J］.系統工程理論與實踐，2016，36（11）：2951-2963.（Zhang Lifeng，Yi Wanli，Liu Xiaolan.Two-stage optimization algorithm for large scale secondary petroleum product delivery planning［J］.Systems Engineering-Theory amp; Practice，2016，36（11）：2951-2963.）

［5］王旭坪，董杰，韓濤，等.考慮碳排放與時空距離的冷鏈配送路徑優化研究［J］.系統工程學報，2019，34（4）：555-565.（Wang Xuping，Dong Jie，Han Tao，et al.Optimization of cold chain delivery routes considering carbon emission and temporal-spatial distance［J］.Journal of Systems Engineering，2019，34（4）：555-565.）

［6］周鮮成，呂陽，賀彩虹，等.考慮時變速度的多車場綠色車輛路徑模型及優化算法研究［J］.控制與決策，2022，37（2）：473-482.（Zhou Xiancheng，Lyu Yang，He Caihong，et al.Research on multi-depot green vehicle routing model and its optimization algorithm with time-varying speed［J］.Control and Decision，2022，37（2）：473-482.）

［7］Bae H，Moon I.Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles［J］.Applied Mathematical Modelling，2016，40（13-14）：6536-6549.

［8］Zhen Lu，Ma Chengle，Wang Kai，et al.Multi-depot multi-trip vehicle routing problem with time windows and release dates［J］.Transportation Research，Part E：Logistics and Transportation Review，2020，135（3）：articleID 101866.

［9］劉明，李穎祖，曹杰，等.突發疫情環境下基于服務水平的應急物流網絡優化設計［J］.中國管理科學，2020，28（3）：11-20.（Liu Ming，Li Yingzu，Cao Jie，et al.An optimal design of emergency logistics network for epidemic controlling based on service level［J］.Chinese Journal of Management Science，2020，28（3）：11-20.）

［10］鄭斌，馬祖軍，李雙琳.基于雙層規劃的震后初期應急物流系統優化［J］.系統工程學報，2014，29（1）：113-125.（Zheng Bin，Ma Zujun，Li Shuanglin.Integrated optimization of emergency logistics systems for post-earthquake initial stage based on bi-level programming［J］.Journal of Systems Engineering，2014，29（1）：113-125.）

［11］Jiang Dongqing，Zhu Qunxiong.Grain emergency vehicle scheduling problem with time and demand uncertainty［J］.Mathematical Problems in Engineering，2014，2014：articleID 971861.

［12］Chai Gan，Cao Jinde，Huang Wei，et al.Optimized traffic emergency resource scheduling using time varying rescue route travel time［J］.Neurocomputing，2018，275（1）：1567-1575.

［13］Liuzzi G，Locatelli M，Piccialli V.A new branch-and-bound algorithm for standard quadratic programming problems［J］.Optimization Methods and Software，2017，34（1）：79-97.

［14］Chandrasekaran K，Végh L A，Vempala S S.The cutting plane method is polynomial for perfect matchings［J］.Mathematics of Operations Research，2016，41（1）：23-48.

［15］De Santis M，Grani G，Palagi L.Branching with hyperplanes in the criterion space：the frontier partitioner algorithm for biobjective integer programming［J］.European Journal of Operational Research，2020，283（1）：57-69.

［16］De Oliveira F B，Enayatifar R，Sadaei H J，et al.A cooperative coevolutionary algorithm for the multi-depot vehicle routing problem，CIRRELT-2016-08［R/OL］.（2016-02）.https：//www.cirrelt.ca/documentstravail/cirrelt-2016-08.pdf.

［17］Galindres-Guancha L F，Toro-Ocampo E M，Gallego-Rendón R A.Multi-objective MDVRP solution considering route balance and cost using the ILS metaheuristic［J］.International Journal of Industrial Engineering Computations，2018，9（1）：33-46.

［18］Stodola P.Hybrid ant colony optimization algorithm applied to the multi-depot vehicle routing problem［J］.Natural Computing，2020，19（2）：463-475.

［19］Yu B，Yang Z Zhongzhen，Xie J X.A parallel improved ant colony optimization for multi-depot vehicle routing problem［J］.Journal of the Operational Research Society，2011，62（1）：183-188.

［20］Zhou Rui，Liao Yi，Shen Wenjing，et al.Channel selection and fulfillment service contracts in the presence of asymmetric service information［J］.International Journal of Production Economics，2020，222（4）：article ID 107504.

收稿日期：2021-09-29；修回日期：2021-11-23基金項目：國家自然科學基金資助項目（61702006）

作者簡介：吳凡（1988-），男，安徽馬鞍山人，碩導，博士，主要研究方向為應急管理與應急決策；楊冰（1997-），男（通信作者），安徽馬鞍山人，碩士，主要研究方向為應急物流及智能優化算法（goforityangbing@126.com）；洪思（1995-），男，江蘇蘇州人，碩士，主要研究方向為智能算法及機器學習.