当前位置：首页 > news >正文

2025年IEEE TPAMI，面向车辆路径问题的学习辅助邻域搜索

news 2026/7/13 7:30:09

1.摘要

针对传统邻域搜索按固定顺序穷举导致效率低下的问题，本文提出在线学习辅助邻域搜索算法（LaNS），利用多智能体强化学习（MARL）构建自适应算子选择机制，通过两个高层智能体协同从底层启发式算子库中选择扰动与改进算子，从而动态引导搜索方向。同时，将空间路径结构转化为图像张量，利用 CNN 提取特征。在CVRP、MDVRP等多种复杂VRP基准测试中的评估结果表明，LaNS在求解质量和效率上均优于现有经典邻域搜索及学习引导算法。

2.学习辅助邻域搜索

LaNS 每轮包含扰动阶段、局部搜索阶段和策略学习阶段。若连续若干轮无改进，shaking policy 选择扰动算子跳出局部最优； search policy 选择改进算子做局部搜索。两类经验被存入回放池，并在线更新两个策略网络。

初始化，扰动策略π ( ⋅ ∣ θ 1 ) \pi(\cdot|\theta_1)π(⋅∣θ1)与搜索策略μ ( ⋅ ∣ θ 2 ) \mu(\cdot|\theta_2)μ(⋅∣θ2)随机生成。搜索策略负责选择能最大化局部改进的算子；扰动策略负责选择能把搜索带到更有潜力区域的算子。

状态特征由多通道张量构成，位置特征L i j L_{ij}Lij为客户i , j i,ji,j距离；邻接特征A d i j ( s ) Ad_{ij}(s)Adij(s)表示当前路线中i , j i,ji,j是否相邻；需求特征D i j ( s ) D_{ij}(s)Dij(s)表示沿当前路线经过边时累计需求；容量特征C i j ( s ) C_{ij}(s)Cij(s)表示剩余容量；若有能量约束，则B i j ( s ) B_{ij}(s)Bij(s)表示剩余电量。张量：

Φ ( s ) = L ⊕ A d ( s ) ⊕ D ( s ) ⊕ C ( s ) ⊕ B ( s ) \Phi(s)=L\oplus Ad(s)\oplus D(s)\oplus C(s)\oplus B(s)Φ(s)=L⊕Ad(s)⊕D(s)⊕C(s)⊕B(s)

CNN 提取空间特征：

h k = RELU ⁡ ( ConV2D ⁡ ( W k , Φ ) + b k ) h_k=\operatorname{RELU}\left(\operatorname{ConV2D}(W_k,\Phi)+b_k\right)hk=RELU(ConV2D(Wk,Φ)+bk)

RELU ⁡ ( x ) = max ⁡ ( 0 , x ) \operatorname{RELU}(x)=\max(0,x)RELU(x)=max(0,x)

随后经自适应平均池化，并与当前目标值、上次动作、客户数、车辆数等宏观特征拼接输入全连接网络。

低层启发式构成动作空间，含 intra-route 与 inter-route 两类。前者在同一路线内移动客户，后者在不同路线间移动客户。局部搜索时，给定当前解s ss和算子a aa，算法枚举邻域N a ( s ) N_a(s)Na(s)中的解并接受最优改进；扰动阶段则随机采样邻域解作为新起点，以跳出局部最优。

算子选择建模为 MDP⟨ S , A , P , R ⟩ \langle S,A,P,R\rangle⟨S,A,P,R⟩。状态为Φ ( s ) \Phi(s)Φ(s)，动作为空间中的低层启发式。基于 Q 值轮盘赌选择动作：

P ( a ) = Q ( Φ ( s ) , a ) ∑ a ∈ A Q ( Φ ( s ) , a ) , ∀ a ∈ A P(a)=\frac{Q(\Phi(s),a)}{\sum_{a\in A}Q(\Phi(s),a)},\quad \forall a\in AP(a)=∑a∈AQ(Φ(s),a)Q(Φ(s),a),∀a∈A

搜索策略的转移为对当前解执行所选局部搜索并得到最佳邻居；扰动策略的转移为先扰动局部最优，再经过一系列局部搜索到达下一局部最优。两类策略统一奖励为改进比例：

r ( s , a , s ′ ) = C o s t ( s ) − C o s t ( s ′ ) C o s t ( s ) r(s,a,s')=\frac{Cost(s)-Cost(s')}{Cost(s)}r(s,a,s′)=Cost(s)Cost(s)−Cost(s′)

若s ′ s's′更优，奖励更高。搜索策略奖励衡量一次改进算子的即时效果；扰动策略奖励衡量一次扰动是否带来更好后续局部最优。

搜索策略从 Q 函数蒸馏出动作分布：

ω ( s ) = exp ⁡ ( Q μ ( Φ ( s ) , a ∣ θ 2 ) ) ∑ a ′ ∈ A exp ⁡ ( Q μ ( Φ ( s ) , a ′ ∣ θ 2 ) ) (4) \omega(s)=\frac{\exp\left(Q_{\mu}(\Phi(s),a|\theta_2)\right)}{\sum_{a'\in A}\exp\left(Q_{\mu}(\Phi(s),a'|\theta_2)\right)} \tag{4}ω(s)=∑a′∈Aexp(Qμ(Φ(s),a′∣θ2))exp(Qμ(Φ(s),a∣θ2))(4)

扰动策略不只使用Φ ( s ) \Phi(s)Φ(s)，还拼接搜索策略分布：

Φ ^ ( s ) = Φ ( s ) ∥ ω ( s ) \hat{\Phi}(s)=\Phi(s)\Vert\omega(s)Φ^(s)=Φ(s)∥ω(s)

扰动策略通过 DQN 损失更新：

θ 1 ∗ = arg ⁡ min ⁡ θ 1 E U ( D π ) [ ( y − Q π ( Φ ^ ( s ) , a ∣ θ 1 ) ) 2 ] (5) \theta_1^{*}=\arg\min_{\theta_1}\mathbb{E}_{U(\mathcal{D}_{\pi})}\left[\left(y-Q_{\pi}(\hat{\Phi}(s),a|\theta_1)\right)^2\right] \tag{5}θ1∗=argθ1minEU(Dπ)[(y−Qπ(Φ^(s),a∣θ1))2](5)

y = r ( s , a , s ′ ) + γ max ⁡ a ′ ∈ A Q π ( Φ ^ ( s ′ ) , a ′ ∣ θ 1 − ) (6) y=r(s,a,s')+\gamma\max_{a'\in A}Q_{\pi}(\hat{\Phi}(s'),a'|\theta_1^{-}) \tag{6}y=r(s,a,s′)+γa′∈AmaxQπ(Φ^(s′),a′∣θ1−)(6)

其中，θ 1 − \theta_1^{-}θ1−为延迟目标网络参数，γ \gammaγ为折扣因子。

3.实验结果

实验包含 CVRP、MDVRP 与 cum-MDVRP-E。CVRP 使用标准容量约束基准，MDVRP 使用标准多仓库基准，cum-MDVRP-E 使用救援物流基准，目标为最小化客户到达时间总和，并加入载重相关能耗约束。客户分布包括随机、聚类和混合类型。CVRP 对比 HGS、UHGS、ALNS、KGLS*；MDVRP 对比 CoEA、MDALNS、VNSALS；救援物流对比 POPMUSIC、PLS、VND-TSH、DMMAS。

与 PPO、DQN 等学习型 AOS 比较，LaNS 在大多数实例上更好。若保持 PPO/DQN 原特征但改用 LaNS 多智能体框架，性能提升，说明 MARL 同时指导扰动和改进优于单智能体。若给 PPO/DQN 换成 LaNS 特征张量，也普遍提升，说明路线结构特征比单纯宏观特征更有信息量。

4.参考文献

Guo T, Mei Y, Zhang M, et al. Learning-aided neighborhood search for vehicle routing problems[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2025.