基于深度强化学习的带聚类约束车辆路径问题(Clustered Vehicle Routing Problem, CluVRP)求解方法

《TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW》:Deep reinforcement learning approach to solving clustered vehicle routing problems

【字体: 大 中 小 】 时间:2026年02月13日 来源:TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW 8.8

编辑推荐:

  摘要:带聚类车辆路径问题(Clustered Vehicle Routing Problems, CluVRPs)是一类具有显著现实意义的复杂组合优化问题,是经典车辆路径问题(Vehicle Routing Problem, VRP)的扩展,引入了预定义客户聚

  
摘要:带聚类车辆路径问题(Clustered Vehicle Routing Problems, CluVRPs)是一类具有显著现实意义的复杂组合优化问题,是经典车辆路径问题(Vehicle Routing Problem, VRP)的扩展,引入了预定义客户聚类并在簇间与簇内均需进行高效路径规划。虽已有众多深度学习(Deep Learning, DL)方法用于标准VRP,但针对CluVRP的研究相对有限。本文提出一种深度强化学习(Deep Reinforcement Learning, DRL)方法求解CluVRP。研究人员在编码器(Encoder)中设计了聚类感知注意力模块(Cluster-aware Attention Module),并分别构建簇间(Inter-cluster)与簇内(Intra-cluster)解码器(Decoder)以专门化构造性策略(Constructive Policy)在簇间与簇内的决策;训练过程中采用对称数据增强(Symmetrical Data Augmentation)提升性能。在不同CluVRP变体上的实验结果表明,该DRL方法优于现有方法,对各规模算例均具优势。
论文解读:《Deep reinforcement learning approach to solving clustered vehicle routing problems》发表于《Transportation Research Part E-Logistics and Transportation Review》
一、研究背景与开展原因
车辆路径问题(Vehicle Routing Problem, VRP)是经典NP-hard组合优化问题,其中带聚类约束的车辆路径问题(Clustered VRP, CluVRP,含硬聚类Hard-clustered约束要求同一聚类内所有客户须由同一辆车连续访问)因需同时优化簇间排序(Inter-cluster Sequencing)与簇内路径(Intra-Cluster Routing)而更具复杂性,广泛见于垃圾清运、包裹配送及校车路径规划等实际场景。传统精确算法(如Branch and Price)仅适用于小规模算例,启发式算法(如变邻域搜索Variable Neighborhood Search, VNS、大邻域搜索Large Neighborhood Search, LNS)虽较有效但依赖大量人工设计的启发式算子且泛化性差。近年深度强化学习(Deep Reinforcement Learning, DRL)在求解TSP、容量限制VRP(Capacitated VRP, CVRP)等标准VRP上展现出潜力,但多假设各步骤决策同质(逐节点选择),未考虑CluVRP特有的聚类相关约束(Cluster-related Constraints),无法区分关键的入簇节点(Inbound Customer/Entry Node)选择与簇内顺序选择。为此,研究人员开展本研究,提出融合交互式马尔可夫决策过程(Interactive Markov Decision Processes, Interactive MDPs)与改进Encoder-Decoder架构的DRL方法,自动学习CluVRP及其变种(广义VRP、动态CluVRP、软聚类SoftCluVRP)的构造性策略。
二、主要关键技术方法
研究人员采用交互式MDP建模簇间序列决策与簇内路由决策的双智能体(Dual-Agent)顺序构造过程;设计含聚类感知注意力模块(Cluster-aware Cross-Attention,屏蔽同簇节点以捕捉异簇及簇—节点交互)的Encoder,结合独立参数的簇间解码器(上下文含上一访问簇嵌入与上一节点嵌入)与簇内解码器(上下文含簇内首访节点嵌入与上一节点嵌入)差异化两智能体策略;采用REINFORCE算法以路径总行程(欧氏距离)负值为奖励训练网络,基线(Baseline)取批次实例平均代价减方差;训练中应用8向几何对称数据增强(Symmetrical Data Augmentation)增强泛化;通过剩余车载容量与已服务/未服务聚类掩码(Masking)保证硬聚类及容量约束可行性;使用随机生成算例(K-Means聚类)及CVRPLIB改造基准集验证,对照CPLEX、LKH3、双层VNS(Two-level VNS)、混合遗传算法(Hybrid Genetic Algorithm, HGA)、传统构造启发式(最近邻、最远/最近插入)及DRL基准模型(Attention Model, AM; POMO)。
三、研究结果
3.1 实验设置(Experimental setup)
在N20C3(20名客户3簇)、N50C6、N100C12、N150C18四种合成算例上分别训练3000轮次,每轮10000实例,批次大小1000,Embedding维度dh=128,Encoder叠加L=6层Cluster-aware Attention Module,多头注意力头数H=8,Adam优化器初始学习率1e-4;测试用10000独立合成实例及Battarra等提供的CluVRP基准(CVRPLIB Set-X扩展)。
3.2 对比结果(Comparative results)
在合成数据集上,所提方法在N20C3至N150C18各规模均取得最低目标值(Obj.)与0.00% Gap(相对最优已知解),推理耗时仅0.2~9.8分钟/万例;Two-level VNS虽在N20C3持平但随规模增大Gap升至0.17%且耗时剧增(数小时);AM与POMO Gap约0.2%~1%;LKH3及HGA Gap更大;CPLEX无法在合理时间求解>20节点算例。表明该方法习得构造性策略显著优于传统精确/启发式解及现有DRL构造启发式。
3.3 消融实验(Ablation study)
在N20C3上去掉Cluster-aware Cross-Attention后性能下降最剧(差于POMO),去掉簇间解码器(Inter-cluster Decoder)或训练期对称数据增强亦致性能降低但影响较小,证实三组件均对捕获聚类结构及差异化决策有贡献。
3.4 基准测试结果(Benchmarking results)
直接将在N150C18训练模型用于CVRPLIB衍生基准实例(78~384客户,10~49簇),所提方法Obj.均低于POMO、Two-level VNS、HGA及LKH3;POMO在极大算例(X-N359-C45等)稍优于VNS但仍次于本文方法,证明聚类感知编码能有效迁移至异于训练分布的基准算例。
3.5 广义VRP(Generalized VRP)
仅需修改掩码(选定某簇一客户后屏蔽全簇其余客户,允许跨簇任意序访问),同架构适配广义VRP。在N20C7~N150C50上训练测试,本文方法在较大规模(N100C30、N150C50)取得最优Obj.与0 Gap,小规略逊于POMO但仍优于传统方法;用N100C30模型泛化测试N100C20/25/35/40,均获最优,展示良好跨簇数泛化性。
3.6 动态CluVRP(Dynamic CluVRP)
模拟客户需求按泊松过程实时到达,Metaheuristic不适用。相比传统构造启发式及AM、POMO,本文DRL构造策略获最低Obj.与Gap且推理快,适合动态实时顺序构造。
3.7 软聚类VRP(Soft-clustered VRP, SoftCluVRP)
去除簇间解码器,修改簇内解码器上下文为首访问节点嵌入(允许车辆离开再进入同簇)。对比两层遗传算法(Two-level GA)与模因搜索(Memetic Search),本文方法在N50C6、N100C12合成集及Golden基准集多数实例上Obj.最优且耗时远低于Metaheuristic,证明架构经少量调整可拓展至松弛聚类约束问题。
四、讨论与结论翻译
研究人员提出一种DRL方法,通过单一策略网络协同优化CluVRP的簇间排序与簇内路径。通过交互MDP建模双智能体交织决策,采用含聚类感知注意力(Cluster-aware Attention,含同簇屏蔽的跨注意力层以建模簇—节点交互)的Encoder及分设簇间/簇内Decoder差异化策略。该方法在经典CluVRP、动态CluVRP、广义VRP及软聚类VRP变体上验证有效,对不同规模与聚类数的各类算例具优势。此研究彰显了DRL方法在处理带聚类相关约束车辆路径优化中的潜力。
结论原文翻译:
我们提出了一种深度强化学习(DRL)方法来求解带聚类车辆路径问题(CluVRPs),其通过单一策略网络协同优化簇间排序与簇内路由。通过将CluVRPs建模为交互式马尔可夫决策过程(Interactive MDPs),我们有效捕获了两个智能体交织的决策动态,并采用基于编码器—解码器(Encoder-Decoder)的神经网络定制其各自策略。我们的方法在不同配置各类实例的经典CluVRP及其变体上得到验证。我们的贡献强调了DRL方法在解决车辆路径问题中聚类相关约束方面的潜力。未来将把该方法扩展至大规模问题及其他CluVRP变体,也将研究策略网络沿CluVRP各维度(需求分布、聚类数)的泛化行为,并旨在基于这些维度发展可解释策略。
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号