基于模糊需求的應急物資中心選址—路徑問題的算法研究

收稿日期：2022-06-08；修回日期：2022-07-13" 基金項目：國家自然科學基金資助項目（71840003）；上海市科學技術委員會“科技創新行動計劃”軟科學重點項目（20692104300）

作者簡介：彭大江（1995-），男，四川成都人，博士，主要研究方向為應急管理、運籌優化；葉春明（1964-），男（通信作者），安徽宣城人，教授，博導，主要研究方向為生產調度、工業工程（yechm6464@163.com）；萬孟然（1992-），女，河南濮陽人，博士研究生，主要研究方向為工業工程、應急管理.

摘 要：

突發事件爆發后，應急決策通常面臨信息不對稱的情形，由此獲得合理的解決方案非常困難。研究需求量不確定的場景下，同時決策應急物資中心選址方案和配送路徑的問題。首先引入三角模糊數刻畫模糊需求，提出模糊需求下的應急物資中心選址—路徑模型；然后定義Q-學習中的狀態、動作和獎勵，形成超啟發式算法的上層策略；最后以一種新架構封裝低層算子，提出一種基于Q-學習的超啟發式算法。通過數值實驗驗證了算法的有效性，同時通過案例分析體現了模型和算法在實際應用中的可行性。

關鍵詞：應急物資中心；選址路徑問題；模糊需求；Q-學習；超啟發式算法

中圖分類號：TP301.6"" 文獻標志碼：A""" 文章編號：1001-3695（2022）12-016-3631-08

doi："" 10.19734/j.issn.1001-3695.2022.06.0238

Research on algorithm for emergency resource center location-routing problem based on fuzzy demand

Peng Dajiang， Ye Chunming， Wan Mengran

（Business School， University of Shanghai for Science amp; Technology， Shanghai 200093， China）

Abstract：

After an emergency outbreak， it is extremely hard to obtain reasonable solutions for emergency decisions facing information asymmetries. This paper aimed at the problem of simultaneous deciding locations of emergency resource centers and the delivery paths in a scenario with uncertain demand. Firstly， the paper introduced the triangular fuzzy number to depict the fuzzy demand and proposed an emergency resource center location-routing model based on the fuzzy demand. Then the algorithm formed the high-level strategy by defining the states， actions， and rewards in Q-learning. Finally， the paper presented a Q-learning based hyper-heuristic by encapsulating the low-level heuristic operators with a new architecture. The numerical experiments verify the effectiveness of the algorithm， meanwhile showing the feasibility of the model and algorithm in practical applications by a case study.

Key words：emergency resource center; location-routing problem（LRP）; fuzzy demand; Q-learning; hyper-heuristic

0 引言

近年來，災害疫情等突發事件在世界各地頻發，嚴重影響了人民的正常生活。由于突發事件的高度不確定性、難預見性和極強的破壞性，其造成的人員傷亡與經濟損失難以估量。突發事件爆發后，急需建立臨時的應急物資中心并轉運物資，由此有效保障群眾的基本生活要求。然而，在突發事件爆發前夕，由于信息不對稱等原因，可能面臨應急需求點的需求量不確定的情況［1］，導致只能依靠歷史經驗數據來粗略估計需求量的范圍，進而在該情況下進行決策。此外，由于防疫等原因規定各需求點群眾足不出戶，可能會要求配送物資到各需求點，所以還需在選址方案基礎上決策配送路徑，而這正是應急管理中一項巨大的挑戰。

關于同時決策選址方案和路徑規劃的研究主要基于選址—路徑問題（LRP），該問題可描述為從候選設施中選擇一部分進行開設，而后用一批不超過最大載重的車輛對所有需求點進行配送服務。LRP中每個需求點的服務成本不僅與為其提供服務的設施有關，同時還與配送車輛有關，而兩種子問題均具備NP-hard特性，所以LRP的求解困難程度不言而喻。該問題的一種常見的求解方式是將設施選址與路徑規劃分離，形成兩階段的模型再進行求解，然而這種處理模式極易獲得局部最優解或次優解［2］，因此近年來的研究更加傾向于同時決策這兩個子問題。陳業華等人［3］在LRP基礎上考慮救援物資多次運達且持續配送，對此設計一種均衡協作啟發式算法求解。Liu［4］針對地震發生后的傷員運送問題，考慮醫療中心的建立成本和加權距離建立三階段模型。孫華麗等人［5］針對需求量和運輸時間的不確定性，考慮同時使用車輛和直升機聯合運輸應急物資，建立一個魯棒優化模型，并使用CPLEX求解。郭鵬輝等人［6］以救援時效性、綜合滿意度和物資供給的公平性為目標，考慮多種物資的聯合運輸，建立雙層的選址—路徑配送模型，并使用差分進化算法分解目標進行求解。Wei等人［7］在LRP基礎上添加軟時間窗，建立災后應急物資中心選址—路徑的多目標優化模型，并設計混合蟻群算法進行求解。鄭夏等人［8］考慮受災地區分級，建立多目標的應急物資儲備中心選址—路徑模型，并改進差分進化算法進行求解。

可以看到，現有研究針對不同情境下應急設施選址—路徑問題，在經典模型的基礎上提出了很多優秀的模型，然而僅有少數研究考慮到應急情景下的不確定性，且其中的模型多為隨機優化和魯棒優化。考慮到實際應用時隨機優化的概率和魯棒優化的場景難以設定，引入三角模糊數［9］用于刻畫需求量，建立更加易用的模型。針對問題特性，考慮引入Q-學習（Q-learning）［10］，設計基于Q-學習的超啟發式算法（Q-learning based hyper-heuristic， QLHH）。Q-學習是強化學習領域中一種重要的算法，因其近年來在控制領域和深度學習領域取得的重要成果［11］而被重視。現已有一些基于Q-學習設計的優秀超啟發式算法用于求解組合優化問題，并獲得較好的結果［12，13］，然而此類算法架構在求解研究的問題時存在一定的局限性。因此，本文使用一種封裝低層算子的新模式［14］設計QLHH。

基于上述分析，本文首先定義數學符號，并用三角模糊數刻畫需求量，在LRP模型的基礎上提出基于模糊需求的應急物資中心選址—路徑模型（emergency resource center location-routing model based on fuzzy demand，ERCLRM/FD）；針對該模型，設計解的編碼并提出隨機初始化的操作，同時處理模型中的容量約束；其次定義Q-學習中的核心要素，形成超啟發式算法的高層策略（high level strategy，HLS），構建可直接操作解編碼的低層策略（LLH）；最后提出QLHH的算法流程。通過在30個數據集上驗證QLHH的求解性能，并輔以一個實際案例來直觀展示不同模糊度下獲得的解決方案。

1 問題建模

1.1 模型假設與數學符號

為不失問題的一般性，同時突出研究問題的重點，建立的ERCLRM/FD基于以下六項假設：

a）每個應急需求點必須正好由一個應急物資中心提供服務，且只能安排一輛汽車途經該需求點為其服務；

b）每輛汽車可認為是相同的，若啟用某車輛，其只有一條行駛路線，而多次使用同一輛車可認為多次啟用車輛；

c）車輛的行駛路徑必須由某應急物資中心出發，經過沿途的應急需求點，最后回到該物資中心，且裝載的應急物資不得超過其容量限制；

d）每個應急物資中心所服務的應急需求點的需求量之和不得超過該物資中心的服務容量上限；

e）由于突發事件爆發后的信息不對稱和信息滯后性，暫時無法獲取每個應急需求點的具體需求量，只可由歷史數據大致評估該需求點的需求量上下界以及一個可能性最大的值；

f）突發事件爆發后人手緊張且資源稀缺，因此目標函數為開設應急物資中心的資源消耗量，車輛使用的固定資源消耗量，以及運輸過程中的資源消耗量之和。

基于以上假設，形成模型中的數學符號及解釋如表1所示。

1.2 基于模糊需求的應急物資中心選址—路徑模型

對于建立的ERCLRM/FD，其考慮當各需求點的需求量為模糊的背景下，同時決策物資中心的選址、需求點的分配以及配送車輛路徑的規劃。由于建立物資中心和啟用車輛配送會造成固定資源消耗，而車輛行駛路線越長，反應出配送效率越低，配送車輛的在行駛中消耗的資源量也越多。以總體資源消耗量最小為目標，同時決策選址方案和配送路徑的ERCLRM/FD中目標函數如下：

min z=∑i∈I fixi+∑k∈K ∑e∈δ+（I）Tuek+∑k∈K ∑e∈Edeuek（1）

模型的約束條件如下：

∑k∈K ∑e∈δ－（j）uek=1" j∈J（2）

∑e∈δ+（i）uek=∑e∈δ－（i）uek" k∈K，i∈V（3）

∑e∈δ+（I）uek ≤ 1" k∈K（4）

∑e∈L（S）uek ≤ |S|－1" SJ，k∈K（5）

∑e∈δ－（j）uek+∑e∈δ+（i）∩δ－（J）uek ≤ 1+yij" i∈I，j∈J，k∈K（6）

∑j∈J ∑e∈δ－（j）juek ≤ C" k∈K（7）

∑j∈Jjyij ≤ qixi" i∈I（8）

xi∈{0，1}" i∈I（9）

yij∈{0，1}" i∈I，j∈J（10）

uek∈{0，1}" e∈E，k∈K（11）

其中：目標函數式（1）表示最小化以下三部分資源的總和，應急物資中心的開設資源消耗，車輛使用的固定資源消耗，以及車輛在資源配送過程中行駛路程的資源消耗；約束式（2）表示對任一需求點，有且僅有一輛車并只通過一條路徑到達該點；約束式（3）限制由需求點或物資中心點出發和返回該點的車輛路徑數相等；約束式（4）確保每輛車至多從某個物資中心出發一次；約束式（5）用于限制每輛車在需求點間行駛時沒有子回路；約束式（6）表示某個需求點被某個物資中心服務的前提是存在一條開設的路線由該物資中心出發且中途到達該需求點；約束式（7）（8）分別代表車輛容量限制和物資中心容量限制；約束式（9）～（11）定義了模型中的決策變量。

1.3 模糊需求分析

由于ERCLRM/FD中考慮需求量的不確定性并用模糊數刻畫，所以無法直接對模型進行求解。為使其可解，引入模糊集合理論，借助其中最為廣泛使用的三角模糊數［9］來對模型分析。記=（al，am，au）為一個三角模糊數，其中al和au表示該模糊數的下界和上界，am為其可能性最大的值，則的成員隸屬度函數μ（x）∈［0，1］可記為如下：

μ（x）=0""""""" xlt;al

fa（x）=x-alam-alal≤x≤am

ga（x）=x-amau-amam≤x≤au

0xgt;au（12）

其次，使用模糊理論中r-切割技術衡量參數的不確定性［15］。模糊數在某個r-切割下的定義為ar={x|μ（x）≥ r}，其中r∈［0，1］，且r越高，表示該參數下的確定性越高，因此可將ar記為ar=［f－1a（r），g－1a（r）］。如圖1展示了各r水平下模糊數的成員隸屬度函數的不確定性程度，下方的支撐面越寬，則表示不確定性程度越高。

對于模糊數，定義r-切割下的期望區間EI（）為

EI（）=［Ea1，Ea2］=［∫10f－1a（r）dr，∫10g－1a（r）dr］（13）

進而推導出的期望值EV（）為期望區間的中點［16］，如式（14）所示。

EV（）=［12（al+am），12（am+au）］（14）

此外，若給定的一對模糊數和，記大于的度如下：

μM（，）=0""""""""" Ea2－Eb1lt;0

Ea2－Eb1Ea2－Eb1－（Ea1－Eb2） 0∈［Ea1－Eb2，Ea2－Eb1］

1 Ea1－Eb2gt;0（15）

其中：［Ea1，Ea2］和［Eb1，Eb2］分別為和的期望區間，若滿足μM（，）≥ λ，即可說明在度為λ下大于或等于，記之為≥λ 。

基于上述知識，當考慮其中參數為三角模糊數的數學模型，其中決策變量記為x∈Euclid ExtraaBpn，某條不等式約束為ix≤ i，其中i=1，2，…，m。由式（15）可知，要使該模型在度為λ下可行，約束ix≤ i等價于式（16）。

Eaix2－Ebi1Eaix2－Eaix1+Ebi2－Ebi1 ≤ λ" i=1，2，…，m（16）

基于式（16），將ERCLRM/FD中包含模糊需求量的約束式（7）和（8）進行轉換，即可形成如下可求解的數學模型：

min" 式（1）

s.t." 式（2）～（6），（9）～（11）

∑j∈J（1－λ）wmj+wuj2+λwlj+wmj2∑e∈δ－（j）uek≤C" k∈K（17）

∑j∈Jyij（1－λ）wmj+wuj2+λwlj+wmj2≤qixi" i∈I（18）

2 基于Q-學習的超啟發式算法

2.1 解的編碼方式

算法采用物資中心編號和需求點編號混合的方式對解進行編碼，解碼時各物資中心編號后緊跟的需求點編號即為該物資中心按順序服務的需求點。如圖2所示是在一個m=5，n=10算例中的編碼示意圖，其中物資中心1服務需求點8、10、6，物資中心3服務需求點9、12、15、14，物資中心4服務需求點13、7、11，而物資中心2和5因編號后無緊跟需求點編號所以不開設。需要注意的是，為盡量不錯過問題的最優解，引入一種隔斷標示（dummy flag）［17］用于強制隔斷當前路徑，由此在不違反容量約束的前提下分割車輛配送路徑，圖2中用0來表示，而緊跟在物資中心編號后或處于解編碼末位的隔斷標示可忽略。

隔斷標示的數量l與車輛容量C和以及需求點的需求量j=（wlj，wmj，wuj）有關，本文中按式（19）進行計算，即經過轉換后的三角模糊需求量之和與車輛容量的商并向上取整，表示最少需要l輛車來滿足所有需求點。由此可確定解的編碼長度為m+n+l。

l=「1C∑j∈J（1－λ）wmj+wuj2+λwlj+wmj2（19）

此外，對于物資中心的容量約束，按式（20）將其轉換為懲罰。

M∑i∈Imax0，∑j∈Jyij（1－λ）wmj+wuj2+λwlj+wmj2－qixi（20）

其中：M（Mgt;0）是一個懲罰因子，表示對所有物資中心，將超出容量的服務量之和乘M，然后將其與目標函數式（1）相加，即可用于評價某個解的適應度，進而可忽略模型中關于物資中心的容量約束式（18）。值得注意的是，M被初始化為M=∑i∈Ifi/∑i∈Iqi，然后在算法迭代過程中不斷增大直至+∞，以此鼓勵算法在前期跳出局部最優解，去尋找全局最優解，并在中后期逐漸穩定，保證最終求得的解不會違反模型中的容量約束。

2.2 解的初始化操作

基于上述解的編碼方式，設計如算法1所示的隨機初始化操作，以保證算法產生可行的初始解。

算法1 解的初始化

輸入：包含所有需求點編號的向量B1×n=［bj］1×n ；隔斷標示數量l；經過三角模糊轉換后的需求量wj。

輸出：初始解x。

初始化開設的應急物資中心集合I′←{}，各物資中心服務的需求點集合gi←{}

初始化需求總量W←∑j∈Jwj，總服務量Q′←0。

while Q′lt;W do //最少需要開設的物資中心

隨機選擇應急物資中心i∈I＼I′

I′←I′∪{i}，Q′←Q′+qi

end while

初始化每個物資中心的剩余需求量θi←qi

隨機打亂向量B中的次序

for j=1→n do

初始化d*←+∞，i*←0

for each i∈I′ do

if θigt;wj and dibjlt;d* then

d*←dibj，i*←i

end if

end for

if i*=0 then //物資中心容量不足

隨機選擇應急物資中心i∈I＼I′

I′←I′∪{i}，j←j－1

else

θi*←θi*－wj，gi*←gi*∪{bj}

end if

end for

按各物資中心的服務情況gi記錄到初始解x中的編碼

在x首位之后的l個隨機位置添加隔斷標示

return x

2.3 Q-學習中的要素定義

定義一系列可能的狀態S=（s1，s2，…，sm），以及一系列可選的動作A=（a1，a2，…，an）。記rt+1為t時刻在狀態st時采取動作at獲得的即時獎勵，而Q（st，at）為t時刻的一個狀態—動作對（state-action pair）的累計獎勵值（Q值），其按如下方式更新：

Qt+1（st，at）=Q（st，at）+α（rt+1+

γmaxa Q（st+1，a）－Q（st，at））（21）

其中：參數α∈［0，1］為學習率（learning rate）；γ∈［0，1］為折扣因子（discount factor），表示未來獎勵的衰變系數。

對應到QLHH，將Q-學習作為上層策略根據算法所處狀態選擇封裝了LLH的動作，進而根據相應動作確定LLH和解的接受準則，最終使用選擇的算子對解的編碼進行擾動。因此首先設定在該架構下Q-學習中的狀態、動作和獎勵，然后定義LLH，最后闡述動作的選擇和執行方式。

2.3.1 狀態定義

狀態能反應算法當下面臨的真實情況，進而決定強化學習中動作的選擇。由于Q-學習中的所有狀態—動作對的Q值被存放在一張Q表中，所以其要求狀態集合必須是離散且有限的。鑒于該情況，引入一種基于目標函數值的狀態聚合（state aggregation）［13］技術，將算法迭代過程依據目標函數值人為地分割成幾個階段。為使其更能反應實際情況，將其改進為

st=tzt∑tk=1zk（22）

其中：t表示算法的當前迭代次數；st為當前的狀態；zk表示迭代次數為k時算法產生的新解所對應的帶懲罰的目標函數值。

由于式（22）獲得的狀態st∈［0，+∞），所以按照狀態聚合技術，將狀態分割為［0，σl）、［σl，σu）和［σu，+∞）三個區間，其中σl∈（0，1），σu∈［1，+∞），按st所在的值區間確定離散后的狀態。狀態st可理解為對比算法從開始到當前所獲得的新解，當前解相對新解的平均水平有多好，由此將當前解歸納為大幅提升、小幅提升和無明顯提升三種狀態之一。根據聚合后的三種狀態，即可較為客觀地反映當前解的優劣狀態。

2.3.2 動作定義

動作是Q-學習中根據不同狀態作出的反應，經過一段時間的學習和對Q表的擬合，算法即可針對狀態作出獲得累計獎勵最大的反應。大多數基于強化學習的超啟發式算法都把動作設定為低層的啟發式算子（LLH），進而由高層策略直接選址低層啟發式算子對問題的解或解集進行操作。然而有研究發現，在這種設計模式下，解的接受準則對求解結果有不亞于低層算子對求解結果的影響［18］。因此考慮一種封裝低層算子的模式，將可選動作設計為低層算子的評分標準與解的接受準則的組合。

LLH評分標準旨在從不同的方面評估某個LLH的優劣，而接受準則確定是否接受LLH產生的新解。本文采用如表2所示的四種評分標準和表3所示的四種接受準則。

基于上述的四種LLH評分標準和四種解的接受準則，可以組合形成4×4=16種搜索動作。為使算法的可選動作更完整，添加一種特殊的讀取最優解動作，即當搜索過程阻塞時，可選擇將最優解賦值到當前解。最終形成共17種動作。

2.3.3 獎勵定義

QLHH中的獎勵r分為兩部分：a）使用讀取最優解的特殊動作后，將獲得r=－0.1的小懲罰，以避免算法重復選擇讀取最優解的動作；b）采用非特殊動作后，即確定LLH評分標準與解的接受準則后，算法按LLH評分準則使用選中的LLH產生新解，再按相應的接受準則確定是否接受新解，獲得如式（23）所示的獎勵。

r=1""""""" zlt;z*t－TmaxTmax z≥ z*（23）

其中：z為新解的目標函數值；z*為當前最優解的目標函數值；t為當前迭代次數；Tmax為最大迭代次數。按式（23）所示的方式設定，算法在采取非特殊動作后，若能搜索到更優解將獲得r=1的獎勵，否則將會受到一個隨著迭代次數而逐漸減小的懲罰。其意義在于公平獎勵每次目標函數值的變優，以及按難度懲罰搜索效果一般的動作：前期搜索難度小，優化目標函數值容易，因此懲罰較大；后期搜索難度大，優化目標函數值困難，因此懲罰較小。

2.3.4 低層啟發式算子

對于提出的ERCLRM/FD，設計單點插入、序列插入、序列翻轉和雙點交換四種擾動解的低層啟發式算子。

a）單點插入算子描述為隨機將解中一個在點位i的編碼插入到另一個隨機點位j之前。如圖3所示的單點插入算子執行后，物資中心4關閉，而物資中心2開設。

b）序列插入算子描述為隨機選取解中不超過解長度一半的編碼［i，j］，將其插入到另一個隨機點位k之前。如圖4所示的序列插入算子執行后，物資中心2變為開設，且原本由物資中心3服務的需求點{15，14}現改為物資中心2服務。

c）序列翻轉算子描述為翻轉兩個隨機點位i和j之間的編碼。如圖5所示的序列翻轉算子執行后，物資中心3將不再服務需求點{15，14}，但額外服務需求點13；物資中心4取消服務需求點13，轉而服務需求點{14，15}。

d）雙點交換算子描述為交換兩個隨機點位i和j的編碼。如圖6所示的雙點交換算子執行后，物資中心1原本連續服務的需求點{6，8，10}現變為兩趟車分別服務{6}和{10，8}。

值得注意的是，算法將以上算子中的前三種，即單點插入、序列插入和序列翻轉作為參與評分的算子，且三種算子的評分被初始化為+∞以保證至少被選擇一次，而將雙點交換算子用于后續的局部優化搜索。此外，由于以上四種算子可在解的任意位置編碼進行操作，所以產生的新解不一定如上述例子那么理想，甚至可能產生不以物資中心編碼開頭的解。為解決該問題，在使用了以上任意算子后，均執行算法2以保證產生的新解可以正常解碼。

算法2 修復解的操作

輸入：給定的新解x；候選應急物資中心數m。

if xi=0 or xigt;m then

初始化k←U（1，m） //隨機選擇一個物資中心編號

初始化i←1

while xi≠k do

i←i+1

end while

交換解x首位與點位i的編碼

end if

2.3.5 動作的選擇和執行

QLHH在選擇動作時使用一種效果較好的ε-貪婪（ε-greedy）算法［10］，其中ε是一個隨著迭代次數增加而不斷變小的數字，如式（24）所示。

ε=1－0.9×tTmax（24）

其中：t是算法的當前迭代次數；而Tmax是算法的最大迭代次數。ε∈［0.1，1］用于控制算法進行隨機搜索的概率：每次選擇動作時，算法以ε的概率隨機從設定的17種動作中選擇一種，或是以1－ε的概率選擇當前狀態下Q值最大的動作。使用ε-貪婪算法選擇動作時，可以有效避免陷入局部最優。

前文已經提到，QLHH與一般的超啟發式算法框架有些不同，主要體現在低層的LLH經過封裝，上層的HLS只可選擇定義的16種普通的搜索動作與一種特殊的最優解讀取動作。在選擇某種動作后，QLHH執行該動作并迭代t0次：每次首先從單點插入、序列插入和序列翻轉三種LLH中通過選擇的評分準則按輪盤賭法選擇一種用于產生新解，使用算法2確保新解可行后，再使用η次隨機兩點交叉算子進行局部優化搜索，最后使用選擇的接受準則確定是否接受新解。

算法3 動作的執行

輸入：解x；評分標準fs（LLH）；接受準則fa（x）；本輪迭代次數t0；當前迭代次數tc。

for t=tc→tc+t0 do

對前三種LLH使用fs（LLH）評分，并用輪盤賭法選擇其中一種，記為LLH*

對解x使用LLH*，記產生的新解為x*

調用算法2修復新解x*

for i=1→η do //進行局部搜索

對解x*使用雙點交換算子，記產生新解為x′

調用算法2修復新解x′

if z（x′）lt;z（x*） then

x*←x′

end if

end for

if fa（x*） then //若接受解x*

x←x*

end if

end for

2.4 算法參數與算法流程

基于上述各要素的定義與子算法的設計，現可以將其組成如圖7所示的用于求解ERCLRM/FD的QLHH。其中的參數有學習率α、折扣因子γ、ε-貪婪中的隨機因子ε、兩個狀態分割點σl和σu，執行動作的搜索次數t0、局部搜索次數η、懲罰因子M和最大迭代次數Tmax。需要注意的是，為控制QLHH的總迭代次數為Tmax，t0需為Tmax的約數。此外，由于讀取最優解的特殊動作不會進行搜索，所以其不消耗迭代次數。執行該動作后，可認為目標函數值大幅提升，因此下一狀態s′=0。

3 數值實驗與結果分析

本章開展數值實驗驗證QLHH的性能，與兩種搜索方式最接近的算法進行對比：第一種是精心設計的元啟發式算法SALRP［17］；第二種是同樣基于Q-學習的超啟發式算法QHH［13］，以檢驗QLHH的性能，然后通過求解一個實際案例來驗證該算法求解實際問題的效果。

3.1 數據集與模型參數

由于ERCLRM/FD同時考慮選址方案和路徑規劃，使用Prins等人［19］在研究中使用的30個測試數據集，其中問題規模為：應急需求點數n=20，50，100，200，應急物資中心數m=5，10。然而，該數據集中不存在模糊需求量的設定，所以在原需求量的基礎上，按如下方式修改為三角模糊需求：記原數據中某需求量為w，則模糊需求量最可能的值wm=w，下界wl=w+U（－4，－1），上界wu=w+U（1，4），其中U（－4，－1）和U（1，4）分別為［－4，－1］和［1，4］的均勻分布隨機整數，且該過程保證需求量的下界不小于1。此外，用于評價模糊需求度的參數λ在30個測試數據集上均設置為λ=0.5。

3.2 算法參數設置

QLHH中有四項待定參數：兩個狀態分割點σl和σu、折扣因子γ，以及執行動作的搜索次數t0。對于其他非自適應參數，按如下方式進行設置：最大迭代次數Tmax=10 000；局部搜索次數η=100×（m+n+l），其中l為隔斷標示的數量。為對待定參數尋找合適的參數組合，使用田口實驗設計法［20］進行實驗，選用中等大小的13號數據集（m=5，n=100）進行測試，每項參數考慮三種合理的參數設定，使用正交表L9（34）進行實驗，且每組實驗均重復執行30次以盡量減小隨機誤差，將每組具體參數值實驗獲得的平均目標函數值記錄在表4中。

由此可得，QLHH在ERCLRM/FD上的算法參數等級變化趨勢如圖8所示，而最終擇優后按如下設置設定待定參數：σl=0.8，σl=1.1，γ=0.8，以及t0=20。

3.3 實驗環境

為盡量保證所有算法在相同的條件下運行，本文提出的QLHH，以及用于對比的SALRP和QHH均使用C++實現，且實驗平臺均為Intel Core i5 2.9 GHz的CPU和16 GB運行內存，操作系統為Windows 10。為盡可能消除算法中隨機性帶來的差異，每種算法分別在每個數據集上獨立執行30次，算法的各項參數也盡可能相同，具體按照如下方式設置：

a）QLHH中，最大迭代次數Tmax=10 000；局部搜索次數η=100×（m+n+l），其中隔斷標示數l按式（19）設定；狀態分割點σl=0.8，σu=1.1；折扣因子γ=0.8；執行動作的搜索次數t0=20；自適應的學習率α=1－0.9t/Tmax，ε-貪婪中的ε=1-0.9t/Tmax，其中t為當前迭代次數；懲罰因子M=∑i∈Ifi/∑i∈Iqi，后續每迭代100次增大兩倍。

b）SALRP中，初始溫度為30，最終溫度為0.1；降溫系數為0.98；解的擾動次數為5 000×（m+n+l），其中隔斷標示數l按式（19）設定；波茲曼系數為1/9；懲罰因子M=∑i∈Ifi/∑i∈Iqi，后續每迭代100次增大兩倍；若連續迭代100輪最優解無提升則算法結束。

c）QHH中，最大迭代次數Tmax=10 000；擾動次數η=100×（m+n+l），其中隔斷標示數l按式（19）設定；狀態分割點σl=0.85，σu=1；折扣因子γ=0.7；初始溫度為6，最終溫度為1；降溫系數為0.7；自適應的學習率α=1－0.9t/Tmax，ε-貪婪中的ε=1－t/Tmax，其中t為當前迭代次數；懲罰因子M=∑i∈Ifi/∑i∈Iqi，后續每迭代100次增大兩倍。此外，由于原文獻中QHH并未用于求解與LRP相關的組合優化問題，所以只采用了其中的架構，而低層可選算子為本文使用的單點插入、序列插入、序列反轉以及雙點交換算子。

3.4 實驗結果與分析

基于以上設置，將QLHH與SALRP和QHH進行對比實驗，分別在30個數據集上進行實驗且每組實驗重復30次，如表5所示的平均目標函數值和相對誤差百分比，以及表6所示的Wilcoxon符號秩和檢驗。所有測試采用95%的置信區間，并且符號“+”和“－”分別代表QLHH顯著優于或顯著劣于某個對比算法，而符號“=”則表示兩種相比較的算法之間沒有顯著的區別。記R+為QLHH顯著優于其他某個算法的秩和值，而R－為顯著劣于其他某個算法的秩和值，由于有R++R-=N（N+1）/2=465，其中N為每組實驗的重復次數，在表中僅展示Rm=min（R+，R－）以及相應的P值。每個數據集上的最優指標或顯著（P≤ 0.05）的結果被標記為粗體。

從表5、6可以發現，QLHH相較于SALRP和QHH的平均誤差百分比有小幅優勢；在所有的30個測試數據集中，QLHH在18個數據集上顯著優于SALRP，在19個數據集上顯著優于QHH，分別在20號和16號數據集上顯著劣于SALRP和QHH。由此可見，采用QLHH在求解ERCLRM/FD時對比兩種基于單解的元啟發式算法和超啟發式算法都明顯存在優勢，僅在極個別數據集上性能不足。

3.5 案例分析

為進一步驗證ERCLRM/FD和QLHH在實際場景的可行性，本節求解一個上海市的案例。其中各應急點最可能的需求量wm為2010年公布的人口普查數據，而模糊需求量下界為wl=「（1+U（－0.2，0））·wm，上界為wu=「（1+U（0，0.2））×w，其中U（－0.2，0）和U（0，0.2）分別為［－0.2，0］和［0，0.2］的均勻分布隨機實數。此外，根據實際情況將每個應急物資中心點的最大服務容量qi（i∈I）設置為2 000 000，配送車輛的容量C=1 000 000，車輛使用固定消耗資源量T=1 000。對于物資中心的開設資源消耗量fi，設定為|fi=N（10 000，2 0002）|，其中N（10 000，2 0002）是均值為10 000，標準差為2 000的高斯分布，獲得的結果向上取整。特別地，由于案例中需求點47的最大需求量為1 436 983，遠超車輛容量C，所以對該點放寬約束：至多可由兩輛車配送，且其中一輛車必須滿載服務該點。兩點（x1，y1）和（x2，y2）之間的距離L按式（25）計算，其中R為地球半徑。

L=2R arcsin（sin2（y1－y22）+cos（y1）cos（y2）sin2（x1－x22））（25）

模型中的模糊度參數λ分別設置為λ=0，0.2，0.4，0.6，0.8，1，以分析不同λ對求解結果的影響，由此獲得的選址—路徑解決方案如圖9所示。值得注意的是，該圖中的配送路徑并非實際的行駛路徑，僅代表需求點的服務順序。可以看到，隨著λ由0增加至1，求得的總體資源消耗量從242 444下降至233 466。造成該情況的原因是各需求點的需求量模糊程度下降，對應的需求量期望值也因此下降，所以每趟車輛可配送更多的需求點，而各應急物資中心也可服務更多的需求點。對應地，開設的物資中心數也總體呈下降趨勢。在實際應用該模型時，還可根據各需求點的情況不同而設定不同的模糊度λ，由此為決策人提供容錯率更高的解決方案以供參考。

4 結束語

本文研究突發事件爆發后，信息不對稱導致的需求不確定情境下的應急物資中心選址—路徑問題，由此提出了一種以三角模糊數刻畫需求量的ERCLRM/FD。考慮到約束的復雜性，引入隔斷標示，并構造解的編碼方式；基于該編碼，設計一種以強化學習領域中的Q-學習為高層啟發式策略，以LLH評分標準和解的接受準則組合為動作，進而抉擇低層LLH的超啟發式算法QLHH。為檢驗提出的QLHH的性能，將QLHH與兩種應用在相似問題的算法（SALRP和QHH）進行對比，實驗結果說明QLHH在求解ERCLRM/FD時表現出更優的性能。最后，通過一個實際案例分析驗證了算法在實際場景下的可行性。基于上述的數值結果，本文提出的QLHH在求解ERCLRM/FD的有效性和通用性得到驗證，由此在實際應用中可為決策人提供合理的解決方案。

在未來的研究工作中，考慮舍棄局限性較強的Q表同時移除狀態聚合技術，用深度學習的神經網絡來更靈活地擬合連續狀態下的Q表，并輔以其他搜索特征來更準確地表征算法所處的狀態，以輔助Q-學習的決策。此外，針對LRP的最新算法也可學習其設計思路，以形成更智能的超啟發式算法。

參考文獻：

［1］Salman F S，Yücel E. Emergency facility location under random network damage：insights from the Istanbul case［J］. Computers amp; Ope-rations Research，2015，62： 266-281.

［2］Salhi S，Rand G K.The effect of ignoring routes when locating depots［J］.European Journal of Operational Research，1989，39（2）：150-156.

［3］陳業華，白靜，李興源. 多階段災后救援選址—路徑模型及求解算法［J］. 工業工程與管理，2017，22（5）： 150-157. （Chen Yehua，Bai Jing，Li Xingyuan. Model and algorithm for location-routing of multi-stage post-disaster emergency rescue［J］. Industrial Enginee-ring and Management，2017，22（5）： 150-157.）

［4］Liu Kenan. Post-earthquake medical evacuation system design based on hierarchical multi-objective optimization model： an earthquake case study［J］. International Journal of Disaster Risk Reduction，2020，51： 101785.

［5］孫華麗，項美康，薛耀鋒. 不確定信息下應急設施選址—路徑魯棒優化［J］. 系統管理學報，2019，28（6）： 1126-1133. （Sun Huali，Xiang Meikang，Xue Yaofeng. Robust optimization for emergency location-routing problem with uncertainty［J］. Journal of Systems amp; Management，2019，28（6）： 1126-1133.）

［6］郭鵬輝，朱建軍，王翯華. 考慮異質物資合車運輸的災后救援選址—路徑—配給優化［J］. 系統工程理論與實踐，2019，39（9）： 2345-2360. （Guo Penghui，Zhu Jianjun，Wang Hehua. Location-routing allocation problem with consolidated shipping of heterogeneous relief supplies in post-disaster rescue［J］. Systems Engineering： Theory amp; Practice，2019，39（9）： 2345-2360.）

［7］Wei Xiaowen，Qiu Huaxin，Wang Dujuan，et al. An integrated location-routing problem with post-disaster relief distribution［J］. Computers amp; Industrial Engineering，2020，147： 106632.

［8］鄭夏，馬良. 考慮災后分區的應急物資LRP問題研究［J］. 運籌與管理，2020，29（11）： 66-77. （Zheng Xia，Ma Liang. Research on LRP of emergency supplies considering post-disaster zoning［J］.Ope-rations Research and Management，2020，29（11）： 66-77.）

［9］Jiménez M，Arenas M，Bilbao A，et al. Linear programming with fuzzy parameters： an interactive method resolution［J］. European Journal of Operational Research，2007，177（3）： 1599-1609.

［10］Sutton R S，Barto A G. Reinforcement learning： an introduction［M］. Cambridge，MA： MIT Press，2018： 118-120.

［11］Mnih V，Kavukcuoglu K，Silver D，et al. Human-level control through deep reinforcement learning［J］. Nature，2015，518（7540）： 529-533.

［12］張景玲，馮勤炳，趙燕偉，等. 基于強化學習的超啟發算法求解有容量車輛路徑問題［J］. 計算機集成制造系統，2020，26（4）： 1118-1129. （Zhang Jingling，Feng Qinbing，Zhao Yanwei，et al. Hyper-heuristic for CVRP with reinforcement learning［J］. Computer Integrated Manufacturing Systems，2020，26（4）： 1118-1129.）

［13］Lin Jian，Li Yangyuan，Song Hongbo. Semiconductor final testing scheduling using Q-learning based hyper-heuristic［J］. Expert Systems with Applications，2022，187： 115978.

［14］Choong S S，Wong L P，Lim C P. Automatic design of hyper-heuristic based on reinforcement learning［J］. Information Sciences，2018，436： 89-107.

［15］Fazayeli S，Eydi A，Kamalabadi I N. Location-routing problem in multimodal transportation network with time windows and fuzzy demands： presenting a two-part genetic algorithm［J］. Computers amp; Industrial Engineering，2018，119： 233-246.

［16］Heilpern S. The expected value of a fuzzy number［J］. Fuzzy Sets and Systems，1992，47（1）： 81-86.

［17］Vincent F Y，Lin S W，Lee W，et al. A simulated annealing heuristic for the capacitated location routing problem［J］. Computers amp; Industrial Engineering，2010，58（2）： 288-299.

［18］Sabar N R，Ayob M，Kendall G，et al. Automatic design of a hyper-heuristic framework with gene expression programming for combinatorial optimization problems［J］. IEEE Trans on Evolutionary Computations，2015，19（3）： 309-325.

［19］Prins C，Prodhon C，Calvo R W. Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking［J］. 4OR，2006，4（3）： 221-238.

［20］Deng Jin，Wang Ling. A competitive memetic algorithm for multi-objective distributed permutation flow shop scheduling problem［J］. Swarm and Evolutionary Computation，2017，32（1）： 121-131.