基于算子學習的多目標深度強化學習模型求解消防設施選址問題

摘 要：針對消防設施選址問題，構建考慮時效性、市民等待救援的焦急心理和建設成本的三目標消防設施選址模型，以實現更科學的消防設施布局。鑒于該問題的NP難特性，提出基于算子學習的多目標深度強化學習模型（multi-objective deep reinforcement learning，MDRL）。設計多種優化算子作為強化學習的動作空間，訓練策略網絡以選擇最佳優化算子來改進解決方案。針對多目標問題，設計基于優勢差異的方法（MDRL-AD）和基于支配性評估的方法（MDRL-DE）。采用四種規模的測試算例及實際案例進行數值實驗，將MDRL和改進的NSGA-Ⅱ、MOPSO、L2I算法進行比較，并利用Hypervolume指標、Spacing指標、Ω指標、IGD指標對算法性能進行評估。實驗結果表明，MDRL-AD方法更適用于求解小規模算例，MDRL-DE方法則在求解大規模和超大規模算例時相比其他算法優勢明顯。MDRL在非劣解集的收斂性和均勻性方面明顯優于其他對比算法，為消防設施布局規劃提供了一種有競爭力的解決方案。

關鍵詞： 深度強化學習； 算子學習； 優化算子； 多目標優化； 消防設施選址問題

中圖分類號： TP183 文獻標志碼： A 文章編號： 1001-3695（2025）02-021-0477-09

doi： 10.19734/j.issn.1001-3695.2024.06.0276

Multi-objective deep reinforcement learning model based on operator

learning for solving fire facility location problems

Liu Yong^’， Liu Yuxuan， Ma Liang

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

Abstract：To address the fire station location problem considering timeliness， citizens’ anxiety during rescue waits， and construction costs， it developed a three-objective model to achieve a more scientific layout of firefighting facilities. Given the NP-hard nature of this problem， it introduced operator learning to expand the action space. It trained policy networks to select the optimal operators， using two methods： MDRL-AD and MDRL-DE， tailored for different objectives. Through numerical experiments on various scales and real-world cases， it compared MDRL with the improved NSGA-Ⅱ， MOPSO， and L2I algorithms. It evaluated the algorithm performance using Hypervolume， Spacing， Ω-dominance， and IGD metrics. The results demonstrate that MDRL-DE performs notably well in large and very large-scale scenarios， offering competitive solutions in the convergence and uniformity of non-dominated solution sets for fire facility layout planning.

Key words：deep reinforcement learning; operator learning; optimization operators; multi-objective optimization; fire facility siting problem

0 引言

火災作為一種常見的突發性災害，救援不及時可能會造成巨大的人員傷亡和財產損失，特別是在人口密集區域和商業中心，加強對火災的應急響應能力十分重要。截至2024年上半年，全國共接報火災45萬起、亡947人、傷989人、直接財產損失26.8億元。因此，城市建設中需要重點考慮消防設施的布局，確保其能夠覆蓋到可能發生火災的各個地區，并且能夠在火災發生時迅速響應并展開救援行動，保障城市居民的生命和財產安全。目前，國內外對于消防設施選址問題進行了大量研究。許秋艷等人^［1］使用陰陽平衡啟發式算法求解了考慮時效性和成本的雙目標消防救援站選址模型。賀元驊等人^［2］建立了基于熵權直覺模糊拓展的機場消防站選址模型。王寧等人^［3］同時考慮消防站均衡性和消防效益建立了多目標消防站選址模型。叢亦天^［4］以微型消防站選址問題為研究對象，建立了需求點到微型消防站最大距離最小的選址模型。Jing等人^［5］考慮了服務覆蓋率和可訪問性，以及現有站點的影響，提出了一種融合覆蓋率和中位數目標的雙目標優化模型。Yang等人^［6］充分考慮來自不同火災風險類別地區的設施需求，建立了最小化建設成本和最小化火災損失模型。Erden等人^［7］結合需求匹配度模型制定了新增消防站優化布局方案， 減少了應急救援的響應時間。

消防設施選址問題屬于經典的組合優化問題，且為NP難問題^［3］。求解NP難問題的傳統方法主要分為精確方法和啟發式算法。隨著問題規模的增大，精確算法的計算時間復雜度急劇增加，因此更多采用啟發式算法求解大規模問題以獲得近似最優解。然而當前的啟發式優化算法仍存在一些局限性，例如搜索過程可能陷入局部最優解，導致算法求解精度下降；在高維場景下，算法搜索空間的擴展困難，導致算法的收斂速度緩慢，計算時間過長。

近年出現了許多通過深度強化學習來對NP難問題進行求解的方法^［8］。相較于傳統方法，深度強化學習具有快速求解、支持問題規模更大、模型的泛化能力強的優點。在最近的研究成果中，Costa等人^［9］提出了基于深度強化學習改進啟發式算法，通過Transformer網絡訓練2-opt的優化方式并應用于求解TSP。Kool等人^［10］提出了基于注意力機制以及指針網絡的模型，并利用帶有基準的策略梯度算法訓練網絡，實驗中利用該模型有效地求解了包括VRP在內的多個組合優化問題，該網絡結構也是目前求解組合優化較為高效的深度強化學習方法。在此基礎上，許多學者開始使用深度強化學習端到端的方法求解選址問題。王中等人^［11］提出了基于改進圖注意力網絡的深度強化學習模型來求解公共設施服務選址問題。梁浩健^［12］通過將貪婪方法和圖卷積網絡模型結合，提出了一種端到端的方法用于直接求解p-中心選址問題。Drori等人^［13］利用神經網絡求解多種圖組合優化問題，并且提出的模型具有從隨機點訓練泛化到真實城市位置中的能力。Li等人^［14］利用深度強化學習的端到端方法求解了最小頂點覆蓋選址問題，該模型能直接輸出所有選擇節點的概率，取代了以往深度強化模型逐步構造解的方式。

深度強化學習改進的局部搜索方法是近年來興起的另外一類方法，該方法利用深度強化學習算法對搜索規則進行學習，其優化效果可以超越傳統的優化算法。Lu等人^［15］提出了一種learning to improve（L2I）基于算子的改進方法，該算法總體流程采用局部搜索算法，算法選擇算子對當前解改進或者擾動。盛佳浩等人^［16］利用帶有禁忌搜索的深度強化學習算法，通過局部搜索的方式求解的多維背包問題，驗證了深度強化學習求解0-1問題的可行性和有效性。伍康等人^［17］使用圖神經網絡，通過鄰域搜索的方式，有效求解了CVRP。

上述研究為消防設施選址問題提供了很多解決方案，但是在問題建模中，很少有研究考慮到市民等待救援的心理因素，求解多目標選址問題的文獻相對較少，并且缺少綜合考慮時效性、市民等待救援的焦急心理和建設成本的研究。因此，本文考慮市民心理因素， 建立綜合考慮時效性、市民等待救援的焦急心理和建設成本的多目標選址模型。對于求解算法，目前大多數研究都是使用傳統的啟發式算法求解消防站選址問題，而且多數研究都集中在中小規模，小規模問題并不能很好地應用到實際問題當中。另外通過上述文獻可知，深度強化學習算法可以有效求解0-1編碼的組合優化問題，但是目前深度強化學習求解選址問題的文獻都集中在端到端方法，基于局部搜索方法求解選址問題的研究很少，并且大多數深度強化學習研究都集中在求解單目標問題，對于求解大規模多目標問題缺少比較有效且快速的方法。針對該問題，提出一種算子自適應選擇的多目標深度強化學習模型（MDRL），通過對不同規模的算例和實際案例進行求解，并與其他算法進行對比實驗。

1 多目標消防設施選址模型

1.1 問題描述

消防設施選址問題的首要考慮是救援的到達時間。在火災發生的緊急情況下，每一秒都至關重要，合理的消防設施布局可以縮短救援時間，提高救援效率。其次，長時間等待救援會增加市民心理壓力，可能會引發恐慌和秩序混亂，甚至導致踩踏等事故發生。因此，將市民焦急心理程度作為模型目標，用sigmoid函數模擬，市民等待時間越長，焦急心理程度越高，通過優化消防設施布局使市民焦急心理程度最小化，有助于維護秩序和社會的穩定，增強公眾對政府和消防部門的信任度。另外，消防設施建設過多不僅會占用大量空間，而且會花費大量成本造成資源浪費，所以將消防設施建設總成本最小化作為模型的第三個目標。本文將當前已建設的消防設施加入模型進行考慮，已有消防站本身就能滿足一部分應急需求。考慮到一些新城區基礎設施建設剛剛起步，消防設施不足以滿足全部需求，所以需要新增消防設施。新增消防設施分為消防站和微型消防站兩類。消防站覆蓋范圍廣響應速度快，但是建設成本高，占地面積大；微型消防站部署更加靈活，成本低占地小，但是覆蓋范圍小，響應速度慢。所以要根據兩種消防設施的特點選擇合適的進行建設。

根據以上問題描述，考慮已有消防設施的救援能力和兩種不同類型消防設施的特點，建立綜合時效性、心理因素、經濟性的多目標消防設施選址模型。

1.2 模型構建

構建的選址模型所需的參數和決策變量及其相應的符號解釋，如表1和2所示。

根據以上符號定義，構建的綜合考慮時效性、市民心理和成本的三目標消防設施選址模型為

其中：目標式（1）表示最長應急到達時間最小化；目標式（2）表示市民焦慮心理總和最小化；目標式（3）表示消防設施總建設成本最小化；式（4）表示應急需求點需要的消防設施數量約束；式（5）表示應急需求點能接受的最長救援時間約束；式（6）表示新增消防設施的總數量約束；式（7）表示建站后才能進行救援分配；式（8）（9）為需求點i分配的救援時間；式（10）為焦急心理函數，外層為sigmoid函數，通過tan函數和調節系數對變量范圍進行縮放調整；式（11）（12）為消防設施點到達需求點的時間計算公式；式（13）為救援分配變量；式（14）為決策變量；式（15）為已有消防設施的救援分配變量。針對該多目標模型NP難問題特性，本文在深度強化學習理論基礎上，設計基于算子學習多目標深度強化學習模型來求解該問題。

2 基于算子學習的多目標深度強化學習模型

基于算子學習是一種強化學習方法，智能體的動作空間是一組優化算子。本文將消防站設施選址問題抽象為馬爾可夫決策過程，通過訓練策略網絡，讓策略網絡根據當前的狀態輸出選擇每個算子的概率，根據概率選擇最合適的優化算子不斷改進問題解，以找到更優的選址方案。決策過程由狀態、動作、策略網絡、獎勵、回報函數五個要素構成。具體表示如下：

a）狀態：S={s_g，s_l}是輸入到策略網絡的信息，包含當前實例的全局信息s_g和局部信息s_l。其中s_g為靜態信息，由問題實例本身決定，不會隨著智能體做出的動作而改變。s_l是動態信息，會隨著智能體做出動作后不斷發生變化。

b）策略網絡： 深度學習的神經網絡模型，通過訓練后能夠根據當前狀態做出決策，選擇最合適的動作，本文中策略網絡輸出的是選擇每個算子的概率。

c）動作：A={A₁，A₂，A₃，…，A_n}是強化學習中的動作空間，是智能體可選擇的所有可能行動的集合。本文中動作空間是一組優化算子，每一種動作對應一種優化算子，n為優化算子的種類個數。由策略網絡根據當前狀態來決策，選擇最合適的優化算子來改進當前解。

d）獎勵：r_t是環境根據策略網絡t時刻選擇的算子和狀態的組合而確定的反饋信號，用于評估策略網絡選擇優化算子的好壞。

e）回報函數：回報是獎勵累積的總和。算法的目標為最大化回報。對于多目標深度強化學習模型而言，更優質的非劣解將帶來更高的回報，這也意味著在制定消防站選址方案時，該選址方案的多目標綜合效益將更好。

2.1 模型框架

基于算子學習的多目標深度強化學習模型（MDRL）的框架如圖1所示。首先初始化問題實例，生成初始解，并存入舊解庫，同時初始化環境。接下來，控制器將初始解狀態信息輸入策略網絡，輸出選擇算子的概率。根據概率隨機采樣選擇優化算子，更新舊解生成新解。將新解和舊解輸入多目標解比較器，確定支配關系，并反饋給控制器。最后，控制器更新環境，環境反饋獎勵，策略網絡通過反向傳播更新參數。控制器將新的解狀態信息傳輸給策略網絡，進行下一輪學習。

2.2 狀態

控制器輸入到策略網絡的狀態分為靜態狀態信息和動態狀態信息兩類。對于同一實例，靜態狀態信息是保持不變的，不會隨策略網絡做出動作而發生改變。而動態狀態信息會隨著動作和環境的變化發生改變。靜態狀態信息的詳細內容如表3所示，靜態狀態信息類型分為備選點和需求點信息。對于備選點j，記錄了其位置、建站成本以及服務范圍內的需求點數量信息。而對于需求點i，則包括了其位置、人口密度、最大救援時間約束以及最小服務數量約束。特別地，對于消防站選址模型中的已有消防站k的信息，將其與備選點信息合并輸入到策略網絡中。已有消防站k的信息包括位置、服務范圍內需求點的數量。為了保持備選點j和已有消防站k嵌入信息維度的一致性，將已有消防站k的信息加入建站成本c_k并將成本全部設置為0。

動態狀態信息的詳細內容如表4所示，動態狀態信息類型包括當前解、備選點信息、歷史選擇、歷史選擇的影響、掩碼信息。當前解的編碼信息如圖2所示，由備選點編碼與已有消防站編碼拼接而成。備選點位置j的編碼sol_j對應備選點j的建站方案（1為建站，0為不建站），已有消防站的解編碼設置為1。

歷史選擇與獎勵需要經過處理變成歷史特征才能嵌入到策略網絡中。t時刻的歷史特征信息hist.f_t的計算公式為

其中：e_t－h為歷史影響，會隨著時間推移淡化影響；ρ為遺忘因子，ρ∈（0，1）。假設記錄歷史步驟三次，三次選擇的算子序號分別為{2、5、1}，三次歷史獎勵分別為{2、-1、1}，算子個數為6個，ρ=0.9。歷史特征信息的詳細計算過程如圖3所示。

在算子產生新解后，掩碼機制會根據控制器傳入的新解與舊解之間的支配關系進行判斷。如果t時刻選擇的算子改變舊解后沒有產生非劣解，那么在t+1時刻，掩碼信息將會把上次選擇的算子給掩蓋掉，引導策略網絡在t+1時刻選擇其他算子。掩碼采用文獻［16］哈希表的設計方法。

2.3 策略網絡

2.3.1 策略網絡模型結構

本文使用的策略網絡模型結構如圖4所示，網絡整體結構由編碼器和解碼器兩大部分組成。編碼器的輸入數據有當前解、備選點信息、需求點信息。當前解和備選點信息拼接后，通過嵌入層1，映射維度為64。需求點信息通過嵌入層2，映射維度同樣為64，與備選點信息拼接一同放入到編碼器中。

編碼器含有N個相同的復合結構，復合結構內部依次為多頭注意力層、第一個BatchNorm層、前饋神經網絡、第二個BatchNorm層，并且通過兩個殘差連接結構減輕梯度消失問題，并防止網絡過擬合。多頭注意力層頭數為8個，輸出的向量長度為64。前饋神經網絡使用ReLU激活函數，中間層的維度設置為512×4。通過N層編碼器復合結構后，數據特征被輸入到解碼器的嵌入層3中。解碼器的輸入包括歷史特征信息和掩碼信息。編碼器的輸出通過第三個嵌入層后與歷史特征拼接，一同輸入到多層感知器（MLP）中。最后，掩碼信息覆蓋到MLP輸出的數據，為解決梯度消失問題，使用按維度縮放^［18］的softmax函數計算選擇算子的概率向量。

2.3.2 策略網絡訓練方法

本文策略網絡采用帶基線的REINFORCE策略梯度算法^［19］訓練策略網絡。

Δ_θJ（θ|S）=E_{π～pθ（.|s）}［（L_π|S－b（s））Δ_θlog（p_θ（π|S））］（18）

策略梯度算法的目標是最大化回報，t時刻回報的計算公式為

R_t=∑hγ^t－1+h·r_t+h（19）

其中：r_t+h為t+h時刻的獎勵；γ為折扣回報率，本文使用與文獻［15］相同的折扣回報率，γ=1。給定一個實例狀態S，J（θ∣s）表示在狀態S下執行策略π的期望回報。策略網絡根據狀態S輸出的選擇算子概率向量為 p_πθ（A_ts）。A_t為選擇的算子，A_t～π（.|s_t）。策略網絡多次動作π積累的回報量為R_π，基線R_πbl用于減小訓練時的方差，使訓練過程更加穩定。θ為網絡參數。則帶有基線的策略梯度的計算如式（20）所示。通過訓練網絡，采用梯度上升的方式來更新參數θ，使策略網絡能在給定實例狀態S時選擇最優的算子使回報最大化。

Δ_θJ（θ|S）=E_{π～pθ（.|s）}［（R_π－R_πbl）Δ_θlog（p_πθ（A_ts））］（20）

2.4 優化算子

本文設計了兩組優化算子，分別為問題實例導向的優化算子（problem instance-oriented optimization operators，PIOO）和編碼規模導向的優化算子（decoding scale-oriented optimization ope-rators， DSOO）。PIOO算子組從問題實例的背景出發，與實例的動態信息結合，算子的優化方向更加細化，與問題的多個目標關聯，對具體的問題模型更具有針對性。DSOO算子組從解的編碼角度出發，該算子的擾動幅度會根據編碼規模的變化來自適應調整。DSOO具有更廣泛的適用性，可以應用到更多0-1編碼問題當中。本文在實驗過程中將使用這兩組算子作為動作空間訓練網絡，并進行數據測試對比。

PIOO算子組詳細內容如表5所示。PIOO分為交換算子、翻轉算子和破壞算子三大類。其中，交換算子有兩種，操作是將解編碼的兩個或三個隨機位置進行交換；翻轉算子需要結合實例信息進行優化，需要根據實際建站情況選擇性地進行翻轉操作；破壞算子根據問題實例的目標函數設計，分別從最小化時間和最小化成本兩個目標維度對解進行擾動。

DSOO算子組的詳細內容如表6所示。DSOO分為交換算子與翻轉算子兩大類。交換算子新增一種自適應交換算子Swap（n），會根據解的編碼長度（decode_length）自主調整擾動幅度大小，n=α·decode_length。其中，α為Swap（n）的規模敏感系數，α∈（0，1）；DSOO的翻轉算子更加泛化，不再關聯具體的實例信息，適用于更廣泛的場景。新增的自適應翻轉算子Flip（m）與Swap（n）類似，m=β·decode_length。其中，β為Flip（m）的規模敏感系數。

2.5 獎勵函數

針對多目標問題，本文設計了兩種獎勵函數r，分別為優勢差異驅動的獎勵函數（advantage disparity-driven reward，ADR）、支配性評估獎勵函數（dominance-evaluation reward，DER）。本文在實驗過程中也采取上述兩種獎勵的計算方式訓練相應的模型進行對比測試。ADR方法將問題的每個目標視為一個子問題，通過權重系數把每個子問題的目標值進行加權得到當前解的優勢值。在選擇算子之前，計算當前解的優勢值并將其作為t時刻的基準baseline_t。將t+1時刻新解的優勢值與baseline_t的差值作為獎勵。t+1時刻的獎勵值為r=advantage－baseline_t。ADR方法獎勵的詳細計算過程如下：首先對同一批次n個數據的每個目標值進行L₂范數歸一化，避免不同目標函數值尺度不一致對結果產生影響。再將三個目標值乘以目標對應的權重來計算當前解的優勢值，解的優勢advantage如式（21）所示。其中， f_i為目標i的函數值，μ_j為目標j的權重系數，μ_j∈（0，1］。

advantage=∑3i=1μ_if_if²_i1+f²_i2+…+f²_in（21）

DER方法基于控制器傳入的支配信息來計算當前獎勵，根據支配關系調節獎勵系數。支配關系分為以下三種情況：a）如果算子產生的新解支配舊解，獎勵系數τ₁=2；b）如果新解與舊解互為非劣解，τ₂=1；c）如果新解被舊解支配或與舊解完全一樣，τ₃=－1。文獻［15］通過遍歷算子作用位置的方法，計算當前算子的獎勵值，模型訓練時間復雜度過高。本文使用蒙特卡羅方法隨機選擇算子作用位置，模擬評估使用算子后獎勵的期望，降低了模型訓練的時間復雜度。DER方法獎勵函數計算公式為

r=δ·tanh（∑3i=1τ_iE（p_i）σ^h_i）（22）

σ_i=1

i=3

σ_igt;1others（23）

其中：i對應新解和舊解三種支配關系情況；E（p_i）表示情況i出現的概率在蒙特卡羅模擬中的期望值；σ_i為激勵因子；h為使用算子的次數。

隨著解不斷改進，產生新的非劣解的概率大幅降低，如圖5所示，可能會出現獎勵值一直為負的情況，無法反映算子對解作用的真實情況，影響網絡參數更新，導致訓練效果不穩定。因此，本文引入了激勵因子σ來改善該問題。如圖5所示，激勵因子會隨著動作次數的增加逐步提高產生非劣解時反饋給策略網絡的獎勵值，確保即使在解改進變得困難的情況下，仍能夠為網絡提供正向反饋。通過引入激勵因子，有效地解決了獎勵值持續為負的問題，進而改善了網絡訓練效果。

激勵因子需要設置合適的值才能更好地發揮作用。如圖6所示，激勵因子值設置過大，造成獎勵值始終為正值，當策略網絡選擇不合適的算子時也能得到正向反饋，導致訓練效果不佳；激勵因子設置值過小，改善效果不明顯；本文通過測試發現激勵因子設置在［1.028，1.032］內效果較好，激勵因子值與獎勵的平均值對應關系如圖7所示。

圖7 激勵因子值與獎勵平均值對應關系Fig.7 Relationship between incentive factor values and average reward

另外，DER方法計算獎勵時使用雙曲正切函數tanh限制獎勵值的范圍，讓訓練過程更穩定。δ為獎勵尺度，將獎勵限制在（－δ，δ）內。

3 數值實驗

3.1 實驗環境與參數設置

本文實驗基于Python 3.8的代碼實現，利用PyTorch框架構建模型。在GPU（A40-PCIE，顯存48 GB）上進行網絡模型訓練，服務器環境為搭載Intel^? Xeon^? Gold 6348 CPU @ 2.6 GHz 的Windows操作系統。實驗過程中一些重要參數設置如表7所示。

本文采用四種規模隨機生成的問題算例作為數據集，四種規模分別對應小、中、大、超大規模。其中，小規模算例備選點50個，需求點20個，已有消防站個數1個，建站數量約束為［1，12］，速度參數設為1.2；中等規模備選點100個，需求點個數30個，建站數量約束為［1，15］，已有消防站個數2個，速度參數設為1; 大規模算例備選點200個，需求點個數為50個，已有消防站個數3個，建站數量約束為［1，25］，速度參數設為0.8；超大規模算例備選點個數為500個，需求點100個，建站數量約束為［1，35］，速度參數設為0.7，已有消防站個數4個。需求點服務數量約束隨機生成范圍設置為［1，3］，需求點時間約束隨機生成范圍設為［0，2，0.55］，需求點人口密度隨機生成范圍為［0.1，0.9］。備選點建站成本隨機生成范圍為［0.1，0.8］，需求點與備選點坐標隨機生成范圍為［0，1］。

本文使用小規模和中規模的數據集訓練網絡，訓練集實例共28 800個，訓練集隨機生成的種子設置為123。使用四種規模隨機生成的測試集解實例共1 000個，測試集隨機生成的種子設置為456。其中700個用于不同規模的算法對比，另外300個用于兩個算子組比較。

3.2 策略網絡訓練過程

本文共訓練了四組策略網絡，分別為基于PIOO算子組的ADR和DER方法的策略網絡、基于DSOO算子組的ADR和DER方法的策略網絡。通過大量實驗發現PIOO算子和DER方法求解能力相對較好（具體在3.3.1和3.3.2節詳細說明），所以選取基于PIOO算子組的DER方法和L2I^［15］算法進行對比。

訓練過程使用相同的訓練集和相同的初始解，由于原始的L2I算法只能解決單目標整數編碼問題，所以后續實驗中L2I算法使用文獻［16］中針對0-1問題設計的提升算子組，并且獎勵函數使用本文相同的DER方法與MDRL進行對比。L2I的策略網絡的嵌入層根據問題重新設計，其余網絡結構保持不變。在訓練過程中，MDRL與L2I算法的策略網絡得到的回報如圖8所示。為方便觀察，每10個訓練epoch記錄一次回報值。根據訓練結果可見，搭配PIOO算子組的MDRL模型，策略網絡在訓練過程獲得的回報顯著高于L2I算法，MDRL模型的網絡訓練過程更加平穩，更適合求解多目標選址問題。

初始解作為策略網絡訓練時輸入數據的一部分，其質量直接影響了算法的收斂速度和最終結果的優劣，并且初始解的多樣性也影響策略網絡的訓練效果和泛化能力。所以本文采用了三種方式來批量生成初始解，初始解生成的算法偽代碼如算法1所示。首先通過隨機生成初始解來保證多樣性，剔除不滿足約束的解后，使用貪心添加的策略從兩種途徑生成質量較高的解，隨機將最小時間和最大化性價比的備選點添加到建站點中，在滿足解多樣性的同時保證解的質量。

算法1 初始解的批量生成算法

輸入：兩種貪心添加的策略分配比例rate。

輸出：初始解init_s。

a）init_s ← rand_spawn_solution（） //嘗試隨機生成初始解

b）if ！obey_constrant：select=rand.random（），轉步驟c）;else：轉步驟a） //如果隨機解不滿足約束，按比例選擇兩種貪心策略

c）if select gt; rate：轉步驟d）；else：轉步驟f）

d）if obey_constrant： 轉步驟h）；else：轉步驟e）

e）j ←min（t_ij）， init_s［iter］［j］ ← 1，執行后轉步驟d） /*最小時間貪心添加策略*/

f）if obey_constrant： 轉步驟h）；else：轉步驟g）

g）j ← max（num_j/c_j）， init_s［iter］［j］ ←1，執行后轉步驟f） /*最大化性價比的貪心添加策略*/

h）return init_s

3.3 小規模算例驗證

為驗證選址模型的規范性和MDRL算法的有效性，使用cplex求解器對10個小規模算例進行求解。由于cplex求解器無法給出多個目標的非劣解，所以采用三個目標加權求和的方式尋找模型最優解，求解結果如表8所示。經驗證clpex成功求解出選址模型的最優解，MDRL算法在求解出最優解的同時還求解多個非劣解，在10個算例中，MDLR算法求解出的非劣解集中均包含cplex的最優解，結果驗證了選址模型的規范性和MDRL算法的有效性。

3.4 算法測試

本文采用Hypervolume指標^［20］、Spacing指標^［21］、Ω支配性指標^［22］、IGD指標^［23］四個具有代表性的多目標評價指標對算法優化性能進行評估。Hypervolume指標用于評估算法非劣解集收斂性，依照參考點設置，該指標值越大，說明算法非劣解集收斂性越好。Spacing指標用于評估非劣解集的多樣性與分布均勻性，該指標值越小，算法非劣解集的多樣性越好，分布更加均勻。Ω支配性指標用于評估算法獲得帕累托前沿所占比例，該指標越大，說明算法得到非劣解數量越多，算法效果也好。IGD指標同時評價算法收斂性和多樣性，該指標越小，算法性能越好。

3.4.1 不同算子組優化效果對比

將兩組算子在小、中、大規模分別使用100個測試實例進行對比。由表9結果可見，DSOO和PIOO在小規模算例中優化效果接近，計算結果在三個多目標評價指標中各有優劣。小規模算例中，DSOO算子組在Hypervolume和Spacing指標上優化效果略好于PIOO，但劣于PIOO的Ω指標。隨著算例的規模擴大，在中等規模和大規模實例中，PIOO相對于DSOO的優勢逐漸明顯，在大規模實例中，PIOO全部指標都優于DSOO。

本文使用算子相對提升率φ來衡量算子的優化效率，φ值越大表示算子更容易改進當前解，產生非劣解的概率更高。算子相對提升率φ的計算如式（24）所示，其中n_s為產生非劣解的個數，step為算子相對優化次數。兩種算子組合在不同規模算例的相對提升率如圖9所示。兩組算子在小規模算例優化效果非常接近。但隨著問題規模擴大，DSOO的φ值快速下降，PIOO的φ值相對平穩，PIOO在大規模算例性能明顯優于DSOO。

φ=n_sstep×100%（24）

綜合考慮表9和圖9中四個指標的結果，PIOO算子組更加適合本文問題的求解。因此本文在后續的實驗對比過程中，均采用PIOO算子組進行對比實驗。

3.4.2 不同算法的求解性能比較

本文選取了改進的快速非支配排序遺傳算法（NSGA-Ⅱ）^{［24，25］}、改進的多目標粒子群算法（MOPSO）^{［26，27］}、L2I深度強化學習算法^［15］，與本文基于ADR方法的MDRL算法（MDRL-AD）和基于DER方法的MDRL算法（MDRL-DE）進行比較。改進的NSGA-Ⅱ使用與文獻［25］相同的交叉策略，并引入與文獻相同的鄰域搜索策略，加入insert和swap算子^［25］，變異和交叉概率分別設置為0.1和0.8，與文獻保持一致。改進的MOPSO使用與文獻［27］相同的變異操作，加入動態變異機制提高算法搜索能力。

實驗測試算例700個，其中小中大規模各200個算例，超大規模100個算例。不同算法均在相同算例和相同的初始解進行測試，迭代次數都設置為100次。不同算法在四種規模的測試集求解結果如表10所示。為了更直觀體現優化過程，選取一個中等規模算例，不同算法隨著迭代次數的Hypervolume指標值變化如圖10所示，可見本文MDRL算法在中等算例中求解質量和優化速度均優于其他算法。

由表10結果可知，總體上，本文提出的兩種算法在四種規模測試集的求解結果均好于對比的三種算法。在絕大多數算例下，MDRL算法求解結果的 Hypervolume、Spacing、Ω、IGD指標的平均值和標準差均好于其他三種算法。結果表明，MDRL算法求解質量和穩定性均超過其他三種算法，并且在超大規模算例中，MDRL依然有良好的泛化性和求解性能。

根據實驗結果可知，在小規模實驗中，DER三個評價指標均優于ADR方法。中等規模算例實驗下，ADR和DER方法求解性能十分接近，DER略好于ADR。隨著算例規模變大，DER方法的優勢更加明顯，在大規模和超大規模實驗中，DER方法的三個評價指標均優于ADR方法。此結果可歸因于基于支配關系的DER獎勵計算方式能夠更準確地反映出在大規模多目標問題中解之間的非劣關系。相比之下，基于子問題權重合并的ADR獎勵計算方式難以捕捉到大規模多目標問題解的特征。因此ADR方法更加適合求解小規模算例，而DER方法更適合求解大規模算例。

4 案例分析

為進一步測試MDRL算法求解實際問題的性能和泛化能力，選取上海市奉賢新城部分區域作為實際案例背景進行分析求解。本文考慮實際情況，根據人流量數據估計人口密度，奉賢新城區人流量數據如圖11所示，陰影區域為人流量密集區域。基于人流量數據選取商場、居民區、學校等人口密集區域作為救援需求點，選取空地較大且交通方便的位置作為消防站備選點，選取部分建筑密集空地狹小的區域作為微型消防站備選點。其中普通消防站備選點也可當作微型消防站備選點。人口密度、救援速度、時間約束等根據實際數據情況進行設定。

目前該區域中現有消防站共5個，普通消防站4個，微型消防站1個。案例選取的消防設施備選點共83個，其中消防站候選點23個，微型消防站備選點60個。應急救援需求點36個。相關設施點的實際位置如圖11所示。根據點實際位置的經緯度使用式（25）球面距離公式計算出備選點與需求點實際的距離。

d_ij=r_e·arccossin（Lat_i）sin（Lat_j）+

cos（Lat_i）cos（Lat_j）·cos（|Lon_i－Lon_j|）（25）

其中：r_e為地球半徑，取6 371 km；lat為緯度；lon為經度。其他數據信息根據實際情況按照一定范圍進行設置，新增消防站總數量約束設置為［1，8］，普通消防站建設成本為800～1 500萬，普通消防站救援速度在50～80 km/h。微型消防站建設成本為50～200萬，速度為15～20 km/h。需求點設置人口密度為0.2～8，需要的消防設施數量為1～3個。需求點的最大救援到達時間約束根據國家救援標準設置在5 min以內，根據已有的消防站設施救援能力計算，該案例中36個需求點中有8個需求點沒有達到該救援標準，有13個需求點沒有滿足模型的救援設施數量約束，所以需要新增消防設施來優化消防布局。

算法求解實際案例的最優建站方案和相對應的目標值結果如表11所示，建站方案為要建站的消防設施序號。其中范圍0到22為普通消防站的選址序號、23到82為微型消防站的選址序號。每個建站方案對應的三個目標值，其中最大救援時間的單位為秒，成本單位為10⁶元。最優方案共計44個，均為三個目標的非劣解，選取15個具有代表性的方案如表11所示。

由表11中數據分析可得，最大救援時間反映單個需求點的極端救援情況，焦急心理值反映區域整體的救援情況，二者沒有明顯正相關性；增加建設成本能顯著降低市民焦急心理程度，但是未必能顯著減少最大救援時間。綜合考慮上述結果，優先以最大救援時間最短和焦急心理程度最小挑選一個非劣解作為建站方案，該方案最大響應時間在所有方案中最短。該方案新建3個普通消防站，和4個微型消防站。建站序號為［2， 7， 19， 36， 47， 49，50］，其中2、7、19為新增消防站序號，36、47、49、50為新增微型消防站序號。該方案對應三個目標的值：最大救援響應時間為277.2 s，市民焦急心理程度為26.2，總建設成本為3 240萬元。

不同算法對于該實際案例的求解結果如表12所示。所有算法都使用相同的初始解，種群數量都設置為100，迭代次數都設置為100次。Hypervolume參考點設置為［300，30，100］，分別對應最大救援時間、心理目標和建站成本。

結果表明，對于實際案例，MDRL算法的Hypervolume指標、Spacing指標、Ω指標、IGD指標均明顯優于其他對比算法。為了更直觀體現優化過程，不同算法隨著迭代次數的Hypervolume指標值變化如圖12所示。可見，MDRL算法在實際案例中求解質量和優化速度明顯均優于其他對比算法。并且，MDRL-DE方法的求解性能略好于MDRL-AD方法，與測試集中等規模算例結果基本一致，表明輸入數據尺度變化對策略網絡的影響較小，進而驗證了MDRL算法優異的泛化能力。

圖12 不同算法在實際案例的求解性能對比Fig.12 Comparison of results of different algorithms in practical cases

不同算法計算出的非劣解集如圖13所示，由圖可見，MDRL算法非劣解數量明顯多于其他算法。將5種算法計算出的非劣解集進行合并，并對合并后的非劣解集做非支配排序，最終得到的帕累托前沿如圖14所示。帕累托前沿共44個不重復的非劣解。MDRL-DE方法計算出32個非劣解，MDRL-AD 方法為21個；L2I方法非劣解為6個；MOPSO為3個；NSGA-Ⅱ為4個。由此可見本文的MDRL算法求解實際案例的性能明顯優于其他對比算法。

5 結束語

本文引入心理函數衡量火災時市民焦急心理，建立了考慮市民救援時間、焦急心理、成本的三目標消防設施選址模型。針對多目標選址問題，本文提出了基于算子學習的多目標深度強化學習模型MDRL。設計了多種算子組合和獎勵函數，并通過多組實驗對比得出，問題實例導向的優化算子更加有效。通過四種不同規模的算例進行測試，并與改進的NSGA-Ⅱ、多目MOPSO、L2I深度強化學習算法進行對比。結果表明MDRL在四種規模算例都具有更好的優化性能，并且在200個備選點的大規模算例和500個備選點的超大規模算例，相比其他對比算法優勢更加明顯。通過實驗發現，基于優勢差異的獎勵方法MDRL-AD更加適合小規模多目標問題，基于支配性評估的獎勵方法MDRL-DE更適合求解大規模多目標問題。最后本文采用上海奉賢新城作為實際案例進行求解，在實際案例求解中MDRL依然求解性能良好，對于不同類型數據表現出優異的泛化能力，最后為消防設施選址問題的實際案例給出了一個滿意的可行選址方案。在消防設施選址的基礎上，后續研究工作將著重探究消防車輛的動態調度問題，并設計基于深度強化學習的選址加調度問題算法。

參考文獻：

［1］許秋艷， 馬良， 劉勇. 雙目標消防救援站選址模型的元胞陰陽平衡優化算法 ［J］. 運籌與管理， 2022， 31（12）： 31-37. （Xu Qiu-Yan， Ma Liang， Liu Yong. Cellular Yin-Yang pair optimization algorithm for bi-objective fire rescue facility location model ［J］. Operations Research and Management Science， 2022， 31（12）： 31-37.）

［2］賀元驊， 黃一覽， 熊升華. 基于熵權直覺模糊拓展MULTIMOORA的機場消防站選址評價模型 ［J］. 控制與決策， 2023， 38（1）： 265-273. （He Yuanhua， Huang Yilan， Xiong Shenghua. An evaluation model of airport fire stations selection based on entropy weighting informationistic fuzzy extended MULTIMOORA ［J］. Control and Decision， 2023， 38（1）： 265-273.）

［3］王寧， 許益， 張磊， 等. 考慮消防聯動與效益的消防站多目標選址方法 ［J］. 系統工程理論與實踐， 2020， 40（3）： 664-678. （Wang Ning， Xu Yi， Zhang Lei， et al. Consideration of fire station multi-target location method for fire stations considering fire-fighting collaboration and efficiency ［J］. Systems Engineering Theory and Practice， 2020， 40（3）： 664-678.）

［4］叢亦天. 基于遺傳算法的微型消防站選址模型 ［D］. 哈爾濱：哈爾濱理工大學， 2023. （Cong Yitian. A micro fire station location model based on genetic algorithm ［D］. Harbin： Harbin University of Science and Technology， 2023.）

［5］Jing Yao， Zhang Xiaoxiang， Murray A T. Location optimization of urban fire stations： access and service coverage ［J］. Computers， Environment and Urban Systems， 2019， 73： 184-190.

［6］Yang Lili， Jones B F， Yang S H. A fuzzy multi-objective programming for optimization of fire station locations through genetic algorithms ［J］. European Journal of Operational Research， 2007， 181（2）： 903-915.

［7］Erden T， Cokun M Z. Multi-criteria site selection for fire services： the interaction with analytic hierarchy process and geographic information systems ［EB/OL］. （2010）［2024-05-03］. https：//nhess.copernicus.org/articles/10/2127/2010/.

［8］李凱文， 張濤， 王銳， 等. 基于深度強化學習的組合優化研究進展 ［J］. 自動化學報， 2021， 47（11）： 2521-2537. （Li Kaiwen， Zhang Tao， Wang Rui， et al. Research reviews of combinatorial optimization methods based on deep reinforcement learning ［J］. Acta Automatica Sinica， 2021， 47（11）： 2521-2537.）

［9］Costa P， Rhuggenaath J， Zhang Yingqian， et al. Learning 2-optheuristics for the traveling salesman problem via deep reinforcement lear-ning ［C］// Proc of the 12th Asian Conference on Machine Learning. New York： PMLR， 2020： 465-480.

［10］Kool W， Hoof H V， Welling M. Attention， learn to solve routing problems！ ［EB/OL］. （2019）. https：//arxiv.org/pdf/1803.0847.

［11］王中， 曹凱. 耦合改進圖注意力網絡與深度強化學習的公共服務設施智能化選址方法 ［J］. 地球信息科學學報，2024，26（11）：2452-2464. （Wang Zhong， Cao Kai. An intelligent site selection approach for public service facilities coupled with improved graph attention network and deep reinforcement learning ［J］. Journal of Earth Information Science， 2024，26（11）：2452-2464.）

［12］梁浩健. 基于深度學習的地理空間優化問題算法研究 ［D］. 長春：吉林大學， 2024. （Liang Haojian. Research on algorithms for geospatial optimization problems based on deep learning ［D］. Changchun：Jilin University， 2024.）

［13］Drori I， Kharkar A， Sickinger W R， et al. Learning to solve combinatorial optimization problems on real-world graphs in linear time ［C］// Proc of the 19th IEEE International Conference on Machine Learning and Applications. Piscataway，NJ：IEEE Press， 2020： 19-24.

［14］Li Zhuwen， Chen Qifeng， Koltun V. Combinatorial optimization with graph convolutional networks and guided tree search ［C］// Proc of the 32nd International Conference on Neural Information Processing Systems. New York：ACM Press， 2018： 537-546.

［15］Lu Hao， Zhang Xingwen， Yang Shuang. A learning-based iterative method for solving vehicle routing problems ［EB/OL］. （2020）. https：//arxiv. org/pdf/2006. 09100v1.

［16］盛佳浩， 馬良， 劉勇. 自記憶的深度強化學習模型求解多維背包問題 ［J/OL］. 小型微型計算機系統. ［2024-06-19］. http：//kns. cnki. net/kcms/detail/21. 1106. TP. 20230707. 1332. 004. html. （Sheng Jiahao， Ma Liang， Liu Yong. Based self memorized deep reinforcement learning model for solving multidimensional knapsack problem ［J/OL］. Journal of Chinese Computer Systems. ［2024-06-19］. http：//kns. cnki. net/kcms/detail/21. 1106. TP. 20230707. 1332. 004. html.）

［17］伍康， 夏維， 王子源. 一種基于圖神經網絡的改進鄰域搜索算法 ［J］. 計算機應用研究， 2024， 41（5）： 1402-1408. （Wu kang， Xia Wei， Wang Ziyuan. Improved neighborhood search algorithmbased on graph neural network ［J］. Application Research of Computers， 2024， 41（5）： 1402-1408.）

［18］Vaswani A， Shazeer N， Parmar N， et al. Attention is all you need ［EB/OL］. （2017）. https：//arxiv.org/abs/1706. 03762.

［19］Williams R J. Simple statistical gradient-following algorithms for connectionist reinforcement learning ［J］. Machine Learning， 1992， 8（3-4）： 229-256.

［20］鄭金華， 鄒娟. 多目標進化優化 ［M］. 北京： 科學出版社， 2018. （Zheng Jinhua， Zou Juan. Multi-objective evolutionary optimization ［M］. Beijing： Science Press， 2018.）

［21］Ngambusabongsopa R. A novel diversity guided particle swarm multi-objective optimization algorithm ［D］. Changsha：Hunan University， 2011.

［22］姚遠遠， 葉春明， 楊楓. 雙目標可重入混合流水車間調度問題的離散灰狼優化算法 ［J］. 運籌與管理， 2019， 28（8）： 190-199. （Yao Yuanyuan， Ye Chunming， Yang Feng. Discrete grey wolf optimization algorithm for bi-objective reentrant hybrid flow shop scheduling problem ［J］. Operations Research and Management Science， 2019， 28（8）： 190-199.）

［23］么雙雙， 董志明， 王顯鵬. 基于分解的多目標多因子進化算法 ［J］. 控制與決策， 2021， 36（3）： 637-644. （Mo Shuangshuang， Dong Zhiming， Wang Xianpeng. Decomposition-based multi-objective multi-factor evolutionary algorithm ［J］. Control and Decision， 2021， 36（3）： 637-644.）

［24］Reyes-Sierra M， Coello C C A. Multi-objective particle swarm optimizers： a survey of the state-of-the-art ［J］. International Journal of Computational Intelligence Research， 2006， 2（3）： 287-308.

［25］王付宇， 王欣蕊， 賀昕， 等. 考慮需求緊迫度和綜合滿意度的應急物資選址-調度問題 ［J］. 系統工程， 2024， 42（1）： 37-50. （Wang Fuyu， Wang Xinrui， He Xin， et al. Emergency supplies location-scheduling problem considering urgency of demand and comprehensive satisfaction［J］. Systems Engineering， 2024， 42（1）： 37-50.）

［26］Deb K， Agrawal S， Pratap A， et al. A fast and elitist multiobjective genetic algorithm： NSGA-Ⅱ ［J］. IEEE Trans on Evolutionary Computation， 2002， 6（2）： 182-197.

［27］趙海茹， 陳玲. 改進MOPSO在物流節點選址模型中的應用 ［J］. 計算機工程與應用， 2016， 52（12）： 239-244. （Zhao Hairu， Chen Ling. Application of improved MOPSO in logistics node location mo-del［J］. Computer Engineering and Applications， 2016， 52（12）： 239-244.）