目录1.摘要2.学习辅助邻域搜索3.实验结果4.参考文献5.算法辅导·应用定制·读者交流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)hkRELU(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 ′ ss′更优奖励更高。搜索策略奖励衡量一次改进算子的即时效果扰动策略奖励衡量一次扰动是否带来更好后续局部最优。搜索策略从 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) yr(s,a,s)\gamma\max_{a\in A}Q_{\pi}(\hat{\Phi}(s),a|\theta_1^{-}) \tag{6}yr(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.5.算法辅导·应用定制·读者交流xx
