強化圖注意力網絡模型在選址路徑問題中的應用

中圖分類號：TP391 文獻標志碼：ADOI： 10.12475/aie.20250307

本文引用格式：，，.等.強化圖注意力網絡模型在選址路徑問題中的應用[J].自動化與信息工程，2025，46（3）：43-51.HUANG Shuo， ZHANG Xuexi， XIE Xingwang， et al. Application of reinforced graph atention network model forlocation routing problem[J]. Automation amp; Information Engineering，2025，46（3）：43-51.

文章編號：1674-2605（2025）03-0007-09開放獲取

Application of Reinforced Graph Attention Network Model for Location Routing Problem

HUANG Shuo ZHANG XuexiXIE XingWang ZHANG Tao （Guangdong University of Technology， Guangzhou 51ooo6， China）

Abstract：Toaddress the limitationof traditional atention network modelsinefectivelypreserving graph structural informationforLocationRoutingProblems，thispaperproposesareinforced graphatentionnetworkmodel.First，whileretaining graph structuralinformation，theencoderextracts node informationfromthe graph structurethroughatention mechanisms toobtain high-dimensional featurerepresentationsofnodesandglobal graph feature information.Then，thedecoderutilzes GatedRecurrent Units to efectivelycapture temporaldependencies innodesequencesandacquirescompletesolutions viastep-by-stepdecodng. Finaly，anauxiliaryValueNetwork isintroduced toevaluatethevalueofachaction，guiding policyupdatestoenhanctraiing efficiency.Experimentalresultsdemonstratethatthisreinforcedgraphatentionnetworkmodelcanrapidlyobtainhigh-quality solutions for LRP.

Keywords： location routing problem; reinforcement learing; graph atention network; value network; graph structure

0 引言

選址路徑問題（location routing problem，LRP）是一個組合優化問題，旨在同時優化設施位置與車輛運輸路徑，以最小化總成本，廣泛應用于物流、供應鏈管理等領域。

隨著交通物流產業的持續發展，LRP逐漸成為運籌優化領域的研究熱點，同時衍生了眾多改進的數學模型。文獻[1]最早提出了LRP，但由于其復雜性和動態變化的特點，求解相對困難。為此，學者們提出了多種運籌優化算法，主要分為精確算法[2-6]和啟發式算法[7-9]兩類。文獻[10]構建了LRP的整數規劃模型，并利用分支定界法進行求解，這是采用精確算法求解LRP的初步嘗試。隨后，許多學者采用基于0-1線性模型的分支定界法[11]，求解基于切割和定界算法[12]的

LRP。但精確算法僅適用于解決中小規模的LRP，越來越多的學者開始關注能夠處理大規模LRP的啟發式算法。文獻[13]設計并實現了一種基于非支配排序的離散螢火蟲算法來求解LRP，該算法在多樣性指標上表現更好，且更具魯棒性。文獻[14]提出一種基于樹的搜索算法用于位置決策，并結合禁忌搜索算法，通過分裂、交換、搬遷等操作進行路徑規劃，能夠在較短時間內獲得更好的解決方案。

隨著深度強化學習在組合優化問題求解中[15]的成功應用，越來越多的學者嘗試利用其來解決LRP。文獻[16]首次采用端對端的方式將深度學習應用于旅行商問題。隨后，文獻[17]利用強化學習替代監督學習，求解車輛路徑問題，并取得了接近最優解的性能。文獻[18]基于Transformer 模型架構提出一種基于注意力機制的網絡模型，并采用帶基線的策略梯度算法進行網絡訓練，提高了車輛路徑等組合優化問題的求解效率。在文獻[18]的基礎上，文獻[19]提出一種基于強化學習的兩階段算法，分別設計了用于解決選址問題和車輛路徑問題的注意力模型，聯合求解LRP。然而，基于注意力機制的模型雖然能捕捉節點間的關聯關系，但無法保留圖結構信息，導致關鍵特征信息丟失。另外，以往的模型訓練大多采用整體學習策略，難以提供有效的動作價值。

為此，本文提出一種用于求解LRP的強化圖注意力網絡（enhanced graph attention network， EGAT）模型，在有效保留圖結構信息的基礎上，通過注意力機制自動學習圖結構中節點間的重要特征，增強模型對關鍵特征的感知能力。此外，還設計了額外的價值網絡，用于評估每個動作的價值，以引導策略更新。

1 問題與模型

1.1 問題描述

LRP的目標是在已知客戶位置和需求的情況下，從多個倉庫中選擇最佳倉庫，并確定最優配送方案和車輛運輸路徑，以實現總成本（倉庫運營成本、車輛固定成本、車輛運輸成本）最低，LRP示意圖如圖1所示。

為了便于分析和研究，對LRP做出以下假設：

1） 所有車輛的車型、運輸成本相同；

2） 客戶需求小于車輛容量上限；

3） 每個客戶有且僅有一個倉庫為其服務；

4） 倉庫之間不允許存在運輸路徑；

5） 每輛車從一個倉庫出發且返回同一倉庫。

1.2 LRP數學模型

假設有 n 個節點，每個節點代表倉庫或者客戶，節點集合為 N=N_d?N_c={1，2，...，n} 。其中，有 D 個倉庫，倉庫集合為 N_d={1，2，...，D} ；有 C 個客戶，客戶集合為 N_c={D+1，D+2，...，D+C} ；車輛路徑集合為 R={1，2，…} ，其他參數如表1所示。

LRP的數學模型為

式中： z_min 為最小化總成本的目標函數， （204號為倉庫運營成本， 為車輛運輸成本， 為車輛固定成本。

s.t.

公式（2）確保車輛駛入、駛出每個節點。

e_ijk+e_jik≤1，?i，j∈N，k∈R

公式（3）確保車輛不會重復駛入相同的路徑

e_ijk=0，?i=j∈N，k∈R

公式（4）確保從某節點出發的車輛不會駛回該節點。

e_ijk=0，?i，j∈N_d，k∈R

公式（5）確保倉庫之間不存在運輸路徑。

公式（6防止每條路徑中產生子路徑。

公式（7）確保每條路徑上的客戶總需求不超過車輛容量上限。

公式（8）確保倉庫服務的客戶總需求不超過倉庫容量上限。

公式（9）確保每個客戶有且僅有一個倉庫為其

服務。

公式（10）、（11）確保每條路徑上有且僅有一個倉庫。

公式（12）通過倉庫與客戶之間的路徑，限制倉庫的開放數量。

2 算法描述

LRP可被視為一個順序決策過程，能夠采用深度強化學習算法進行求解。

2.1 EGAT模型

本文提出的EGAT模型主要由編碼器、解碼器和價值網絡組成，結構如圖2所示。

編碼器在保留原有輸入圖結構的情況下，提取輸入圖結構中的節點信息，以獲得節點的高維特征表示及整體圖特征信息。

解碼器接收編碼器輸出的節點特征表示和圖特征信息，并采用逐步解碼的方式，在每個時間步選擇動作并更新狀態，直至獲取完整解。

價值網絡在訓練過程中提供動作的價值，輔助EGAT模型學習更精細的動作，使策略更新更穩定。

2.2 編碼器

編碼器由嵌入層和圖注意力網絡層組成，結構如

圖3所示。其中，圖注意力網絡層由3個圖注意力層和1個前饋層構成。

2.2.1 嵌入層

嵌入層的輸入 X={x₁，x₂，...，x_n} 為倉庫和客戶的節點信息。其中， ， s_xi?s_yi 為節點 i （204號的二維坐標， d_i 為節點 i 的需求（倉庫需求為0）。嵌入層將每個輸入 x_i 映射到節點嵌入特征 h_i⁰ （特征維度為128）：

h_i⁰=W^x×x_i+b^x

式中： W^x 、 b^x 分別為可學習的權值矩陣和偏置。

2.2.2 圖注意力層

將節點嵌入特征 h⁰={h₁⁰，h₂⁰，...，h_n⁰} 輸入到圖注意力層，以捕獲節點間的關聯關系和重要性。

首先，根據節點嵌入特征 h_i⁰ 、鄰接節點的嵌入特征 h_j⁰ 來計算注意力權重 α_ij ：

式中： W^g 為特征變換矩陣， a 為注意力權重的學習參數， || 為特征拼接操作， 為節點 i 的鄰接節點集合。

然后，根據注意力權重對鄰接節點的特征進行加權求和，更新節點嵌入特征為 ：

式中： σ 為ReLU激活函數， W^a 為可訓練權重

矩陣。

通過多頭注意力機制，將多個注意力頭的輸出拼接或平均，進一步豐富節點的表達能力。

最后，圖注意力層輸出更新后的節點嵌入特征 （20

2.2.3 前饋層

將更新后的節點嵌入特征輸入到前饋層，進一步提取節點的高維非線性特征，以提升模型的表達能力。

式中： 為第一個全連接層的網絡參數， W₂^F 和 |b₂^F 為第二個全連接層的網絡參數。

最后， 整體圖特征 h^g 為

2.3 解碼器

本文采用強化學習框架將LRP的求解建模為一個馬爾可夫決策過程。

首先，LRP的求解狀態表示為 S={S_g，S_a} ，其中S_g 為編碼器輸出的整體圖特征信息； 為智能體狀態， 為智能體上一步選擇的節點， L_t 為當前車輛的剩余容量；

然后，動作 π_t 為智能體在當前時間步 t 所選擇的節點；

最后，回報 R 為總成本的負數。

解碼器可充當強化學習框架下的智能體，主要由嵌入層、門控循環單元和全連接層組成，結構如圖4所示。

2.3.1 嵌入層

嵌入層將智能體的狀態特征 h^c 映射為上下文特征向量 ：

式中： W^c 和 b^c 為解碼器嵌入層的網絡參數。

2.3.2 門控循環單元

將上下文特征向量輸入到門控循環單元，以捕獲節點間的動態依賴關系和交互信息。

首先，通過公式（20）＼～（23）更新上一個時間步 t -1的輸入節點嵌入特征 和上下文特征 的隱藏狀態：

式中： z_t 為更新門， W^z ， U^z 和 b^z 為更新門可訓練的權重參數矩陣， r_t 為重置門， W^r 、 U^r 和 b^r 為重置門可訓練的權重參數矩陣， W^h 、 U^h 和 b^h 為隱藏狀態權重參數， ? 為元素級乘法。

2.3.3 全連接層

全連接層接收門控循環單元輸出的隱藏狀態序列 ，先將其映射到輸出動作空間 u_t ，再通過 softmax函數輸出概率分數 p_t

式中：W\"和b\"為可訓練的權重參數矩陣，uj，t

為 u_t 第 j 行參數。

根據概率分數 p_t 進行多項式采樣，獲得動作 π_t 。重復以上步驟直到訪問完所有客戶，生成完整解π={π₁，π₂，...，π_T} 。

2.4 價值網絡及訓練算法

價值網絡采用與解碼器相同的網絡結構，其輸入為解碼器輸出動作所選擇的節點，輸出為一維的評估分數，用以評估編碼器輸出動作的優劣。

本文結合策略優化和價值評估的訓練方法，能夠有效平衡策略梯度算法的高方差和基于值函數方法的偏差問題。對于一個給定的實例 s ，將EGAT模型的編碼器-解碼器結構組合為策略網絡 θ ，通過策略網絡 θ 輸出策略的動作概率分布 p_θ（π|s） 采樣得到動作π_t ，即 π_t=sample（p_θ（π∣s））. 。同時，將價值網絡估計狀態的狀態基準值 V_φ（s） 作為策略梯度更新的基準，以降低估計方差。

根據策略梯度定理，策略網絡的期望累計回報為

L（θ）=E_πθ[R（π）]

式中： R（π） 為策略解 π={π₁，π₂，...，π_T} 的累計回報。

策略梯度的計算公式為

式中： A_t=R_t-V_φ（s） 為優勢函數，用于衡量當前動作的實際回報 R_t 與狀態基準值 V_φ（s） 的偏差。

在每次訓練迭代過程中，通過梯度上升法更新策略網絡參數 θ ，通過最小化狀態值的均方誤差更新價值網絡參數 φ ：

θ←θ+α_θ??_θL（θ）

φφ-α_φ??_φ（R_t-V_φ（s））²

式中： α_θ 和 α_φ 為學習率。

EGAT模型訓練算法的偽代碼如下：

EGAT模型訓練算法

輸入：節點集 N ，訓練輪數 E ，批次 B ，步數限制 T ，策

略網絡參數0

輸出：位置-路徑構建策略

1：隨機初始化策略網絡參數 θ

2：for epoch do

3： for batch ω=1，2，…，B do

4： 獲取當前批次數據，設置 t←0

5： while t

6： 根據策略網絡參數 θ 選擇節點 π_t （204號

7： t←t+1

8： end

9： 根據公式（26）和（27）計算梯度 abla_θL（θ）

10： 更新策略網絡參數

11： 更新價值網絡參數

12： end

13：end

首先，調整相關的訓練超參數，并初始化策略網絡參數 θ ;

然后，根據策略網絡參數 θ ，對批次中的每個實例逐步生成動作 π_t ，直到選擇完所有節點；

最后，根據公式（26）、（27）計算策略梯度 abla_θL（θ） ，用于更新策略網絡參數θ和價值網絡參數 φ 。

3.1 實驗設置

本實驗在NVIDIAA30、IntelXeonSilver4310CPU（2.10GHz）和128GBRAM上進行，通過Python3.10和PyTorch2.1.0實現EGAT模型訓練。

EGAT模型訓練參數設置：訓練輪數為100輪，每輪的批次為6400次，每批算例為640例；采用Adam優化器來優化策略網絡參數，學習率為1 ×10^-4 。

通過3種不同規模的實例來評估本文提出的EGAT模型性能：小規模實例（20個客戶，5個倉庫，車輛容量30噸）、中規模實例（50個客戶，5個倉庫，車輛容量50噸）、大規模實例（100個客戶、10個倉庫，車輛容量50噸），節點在 [0，100]×[0，100] 上均勻分布。在3種不同規模的實例上分別測試1000次，并將實例平均求解成本和平均求解時間作為模型性能的評價指標。平均成本越低，代表模型性能越好；平均求解時間越短，代表模型求解效率越高。

3.2 對比實驗

為驗證本文提出的EGAT模型的有效性，將其與文獻[8]的注意力模型（attentionmodel，AM）[18]進行對比實驗。相較于AM采用的強化學習訓練算法[20]，本文EGAT模型采用價值網絡來引導策略更新，減少了策略梯度估計的方差，提升了訓練效率。EGAT模型與AM訓練曲線如圖5所示。

由圖5可知：EGAT模型與AM訓練曲線具有一致的下降趨勢，即總成本在開始時迅速下降，然后逐漸趨于穩定；EGAT模型的最終穩態值和訓練穩定性均優于AM，表明引入價值網絡加速了模型收斂過程，提升了訓練穩定性和策略的最終表現。

3.3 消融實驗

為了進一步評估價值網絡對模型的影響，將未采用價值網絡和采用價值網絡的圖注意力模型在大規模實例上進行訓練，訓練曲線如圖6所示。

由圖6可知，采用價值網絡的圖注意力（EGAT）模型的訓練曲線下降較為平滑且連續，下降幅度較大且波動較小；未采用價值網絡的圖注意力模型的訓練曲線波動較大且存在震蕩，表明價值網絡能夠有效提升模型的訓練效果和性能。

3.4模型性能評估

為進一步驗證EGAT模型的性能，將其與AM及求解LRP的常用算法：精確算法（采用Gurobi求解器）、模擬退火（simulated annealing，SA）算法[21]、遺傳算法（genetic algorithm，GA）[22]和灰狼優化（graywolfoptimization，GWO）算法[23-24]在求解成本、求解時間兩個評價指標上進行對比，結果分別如表2、3所示。

由表2、3可知：本文提出的EGAT模型在20-5和50-5規模問題上，求解成本與Gurobi、SA、GA和GWO算法相近，但求解時間顯著快于上述算法；在100-10規模問題上，其求解成本和求解時間均優于上述算法。具體而言：Gurobi在小規模問題上能夠獲得最優解，但其求解時間隨著規模問題的增大而顯著增加；GA和SA算法在中小規模問題上表現尚可，但在大規模問題上求解成本與求解時間均上升；GWO算法求解成本較低，但求解時間較長。相較于同樣采用深度強化學習框架的AM，EGAT模型的求解成本和求解時間均表現得更好，這主要得益于強化圖注意力模型的快速推理能力，能夠在較短的時間內生成高質量的解。實驗結果有效證明了本文提出的EGAT模型求解LRP的實用性和有效性。

4結論

本文提出一種EGAT模型，相較于傳統的Trans-former模型架構，可有效保留圖結構信息，增強對關鍵特征的感知能力。此外，通過引入額外的價值網絡來評估每個動作的價值，引導策略更新，減少策略梯度估計的方差，提升訓練效率。實驗結果表明，本文提出的EGAT模型在小規模問題上的求解成本與傳統算法相當，但效率更高；在中大規模問題上的求解成本和求解時間均優于傳統算法，證明了其在LRP求解中的實用性和高效性。后續研究將考慮模型在更復雜現實場景下的泛化能力和更大規模問題上的求解能力。

? The author（s） 2024.This isan open access article under the CC BY-NC-ND 4.0 License （https：//creativecommons.org/licenses/ by-nc-nd/4.0/）

參考文獻

[1] COOPERL.The transportation location problem[J]. Operations Research，1972，20（1）：94-108.

[2] BERGER， R， COULLARD， C， DASKIN M. Location routing problems with distance constraints[J].Transportation Science， 2007，41（1）：29-43.

[3]FEILLETD，DEJAXP，GENDREAUM，et al.An exact algorithm for the elementary shortestpath problem with resource constraints：Application to some vehicle routing problems[J].Networks：An Intemational Journal，20o4，44（3）：216- 229.

[4] AKCA Z， BERGER R， RALPHS T. A branch-and-price algorithm for combined location and routing problems under capacity restrictions[C]//Uperations Researcn and Cyber-Intras tructure. Springer US，2009：309-330.

[5] BALDACCI R. MINGOZZI A， WOLFLER CALVO， R. An exact method for the capacitated location-routing problem[J]. OperationsResearch，2011，59（5）：1284-1296.

[6] CONTARDO C， CORDEAU J F， GENDRON B. An exact algorithm based on cut-and-column generation for the capacitated location-routing problem[J]. INFORMS Journal on Computing， 2014，26（1）：88-102.

[7]MANIEZZO V， STUTZLE T， VOB S. Matheuristics， volume 10 of annalsof information systems[J].New York： Springer，2010.

[8] CONTARDO C， CORDEAU JF， GENDRON B. A GRASP + ILP-based metaheuristic for the capacitated location-routing problem[J]. Journal ofHeuristics，2014，20：1-38.

[9] ALVIM A，TAILLARD E. POPMUSIC for the world locationrouting problem[J]. EURO Joumal on Transportation and Logistics，2013，2（3）：231-254.

[10]LAPORTE G， NOBERT Y. An exact algorithm for minimizing routing and operating costs in depot location[J]. European Journal of Operational Research， 1981，6（2）：224-226.

[11]BELENGUERJM，BENAVENTE，PRINSC，etal.Abranchand-cut method for the capacitated location-routing problem[J]. Computers amp; Operations Research，2011，38（6）：931-941.

[12] CONTARDO C， CORDEAU J F， GENDRON B. An exact algorithm based on cut-and-column generation for the capacitated location-routing problem[J]. INFORMS Joumal on Computing，2014，26（1）：88-102.

[13] SHAHSAVARI-POUR N， BAHRAM-POUR N， KAZEMI M . Fuzzy multi-objective location and routing problem[J]. Journal of of Intelligent amp; Fuzzy Systems，2020，39（3）：3259-3273.

[14] SCHNEIDER M，LOFFER M.Large composite neighborhoods for the capacitated location-routing problem[J]. Transportation Science，2019，53（1）：301-318.

[15] BENGIO Y， LODI A， PROUVOST A. Machine learning for combinatorial optimization： a methodological tour d' horizon [J].European Joumal of Operational Research，2021，290（2）： 405-421.

[16] VINYALS O， FORTUNATO M， JAITLY N. Pointer networks [C]. The 29th Conference on Neural Information Processing Systems.Montreal，2015：2692-2700.

[17]BELLO I， PHAMH， LE Q V，et al.Neural combinatorial optimization with reinforcement learning[J]. arXiv： 1611. 09940，2016.

[18] KOOL W， VAN HOOF H， WELLING M. Attention， leam to solve routing problems[J].arXiv：1803.08475，2018.

[19]WANG S， ZHOUJ，LIANGH， et al.A neW approach for solvinglocationroutingproblemswithdeepreinforcement learming of emergencymedical facility[C]//Proceedingsof the 8th ACM SIGSPATIAL International Workshop on Security Response using GIS， 2023：50-53.

[20] WILLIAMSR J. Simple statistical gradient-following algorithms forconnectionist reinforcement learning[J].Machine Learning，1992，8：229-256.

[21]YUX， ZHOUY，LIUXF.The two-echelon multi-objective location routing problem inspired by realisticwaste collection applications：The composablemodel andametaheuristicalgorithm[J]. Applied Soft Computing， 2020，94：106477.

[22]HIASSATA，DIABATA，RAHWANI.A genetic algorithm approach for location-inventory-routing problem with perishable products[J].Joumal ofManufacturing Systems，2017，42： 93-103.

[23]馮苗苗，崔敏，呂淑清，等.混合遺傳灰狼算法在裝配車間調 度中的應用[J].機電工程技術，2023，52（9）：118-122.

[24]TIRKOLAEEEB，GOLIA，MARDANIA.Anovel twoechelon hierarchical location-allocation-routing optimization for green energy-efficient logistics systems[J].Annals ofOperationsResearch，2023，324（1）：795-823.

作者簡介：

黃爍，男，199年生，在讀碩士研究生，主要研究方向：運籌優化與深度強化學習。E-mail：2112204091@mail2.gdut.edu.cn張學習，男，1978年生，博士研究生，副教授，主要研究方向：機器人與智能控制。E-mail：zxxnet@gdut.edu.cn謝興旺，男，2001年生，在讀碩士研究生，主要研究方向：運籌優化與深度強化學習。E-mail：1570475816@qq.com張濤，男，2004年生，在讀本科生，主要研究方向：運籌優化與深度強化學習。E-mail：2430515400@qq.com