基于深度强化学习的前置仓模式配送优化策略研究

《Systems》:Research on Distribution Optimization Strategy of Front Warehouse Model Based on Deep Reinforcement Learning Jiaqing Chen, Ming Jiang and Guorong Chen

【字体: 大 中 小 】 时间:2026年03月04日 来源:Systems 3.8

编辑推荐:

  多仓车辆路径问题与软时间窗(MDVRPSTW,Multi-depot Vehicle Routing Problem with Soft Time Windows)长期以来一直是学术界与工业界共同关注的重点问题。本文提出了一种深度强化学习(DRL,Deep R

  
多仓车辆路径问题与软时间窗(MDVRPSTW,Multi-depot Vehicle Routing Problem with Soft Time Windows)长期以来一直是学术界与工业界共同关注的重点问题。本文提出了一种深度强化学习(DRL,Deep Reinforcement Learning)框架,旨在提升MDVRPSTW求解的效率与质量,以应对传统启发式算法在大规模复杂场景中的局限性。该框架首先通过马尔可夫决策过程(MDP,Markov Decision Process)将数学模型转化为序列决策问题,随后基于注意力机制(Attention Mechanism)与图神经网络(GNN,Graph Neural Network)的编码器—解码器(Encoder–Decoder)架构提取路径选择策略,并采用无监督强化学习进行模型训练。Solomon基准数据集上的测试结果表明,对于小规模问题(N = 20),该方法相较于对比算法将求解时间缩短超过96%,且其目标函数值与广义变邻域搜索(GVNS,Generalized Variable Neighborhood Search)的差异小于9%。对于中大规模问题(N = 50/100),该方法相较于GVNS实现了27.7%至96.3%的改进,并将求解时间稳定维持在3至10 s之间。与精确算法及元启发式方法相比,该方法在展现出对仓库数量与车辆数量变化较强适应性的同时,将计算成本降低了2–3个数量级。总体而言,该方法在解的质量与计算效率两方面均显著优于基线模型,为复杂场景下MDVRPSTW提供了一种高效的端到端(End-to-End)求解方案。
该文发表于《Systems》,研究聚焦于生鲜电商前置仓场景下的配送优化问题,其核心对象是带软时间窗的多仓车辆路径问题(MDVRPSTW,Multi-depot Vehicle Routing Problem with Soft Time Windows)。前置仓即时配送模式已逐渐成为生鲜电商物流组织的重要形态,但生鲜商品具有保鲜周期短、易腐损、冷链依赖强等属性,使配送系统同时面临时效性、履约稳定性与成本控制的多重压力。路径规划作为前置仓配送优化的关键环节,直接影响车辆调度效率、订单履约水平以及整体运营成本。既有研究在车辆路径问题(VRP,Vehicle Routing Problem)及其扩展模型上已积累了丰富成果,尤其是在精确算法、启发式算法与元启发式算法方面形成了较成熟的方法体系。然而,针对MDVRPSTW这一同时包含多仓、多车与软时间窗约束的复杂组合优化问题,现有研究仍较为有限。已有相关工作多依赖启发式或元启发式方法,而应用深度强化学习(DRL,Deep Reinforcement Learning)求解VRP的研究又常常忽略时间窗约束,这使得现有方法在复杂实际场景中的适配性和实时性仍存在不足。因此,开展面向MDVRPSTW的深度强化学习研究,不仅具有算法创新价值,也具有服务前置仓配送实际需求的重要意义。

围绕上述问题,研究人员构建了一个面向MDVRPSTW的端到端深度强化学习求解框架。研究首先将配送优化问题抽象为马尔可夫决策过程(MDP,Markov Decision Process),把原本的数学规划问题转化为多车辆同步路径选择的序列决策问题,并系统定义了状态空间、动作空间、状态转移规则和奖励函数。在此基础上,研究人员设计了结合注意力机制与图神经网络(GNN,Graph Neural Network)的编码器—解码器神经网络结构,通过对节点特征、拓扑结构及车辆动态状态进行联合建模,实现多仓多车场景下的路径生成。模型采用无监督强化学习训练,以策略梯度(Policy Gradient)优化路径选择策略,并以总配送时间成本的负值作为奖励信号。实验结果表明,该模型在小规模实例上能够以极短时间获得接近高质量启发式算法的解,而在中大规模实例上则在目标值与求解时间两方面均表现出明显优势。研究结论显示,该框架有效弥补了传统算法在复杂场景中的效率瓶颈,也填补了深度强化学习应用于MDVRPSTW问题的研究空白。

从方法层面看,研究主要采用了以下关键技术。其一,将MDVRPSTW建模为马尔可夫决策过程(MDP),以全局静态状态与车辆动态状态联合表示配送环境,并通过同步动作机制实现多车辆决策。其二,在神经网络架构上采用编码器—解码器(Encoder–Decoder)框架,其中节点编码器利用多头注意力(Multi-head Attention)提取客户节点空间位置、需求与时间窗等属性关联,图编码器利用图神经网络(GNN)刻画仓库与客户之间的图结构关系。其三,在解码阶段通过容量掩码(capacity mask)与全局节点掩码(global node mask)实现约束过滤,再结合采样搜索与贪婪搜索完成路径输出。其四,训练数据由随机分布生成,测试则基于Solomon(1987)数据集经多仓扩展和约束适配后完成,用于验证模型的求解性能、泛化能力与参数敏感性。

以下结合论文主体结构,对研究结果进行凝练解读。

在“Problem Definition”部分,研究人员首先明确了前置仓配送优化可抽象为连接图G = (V, E)上的MDVRPSTW问题。配送区域包含多个配送中心,每个中心配置若干车辆,车辆具有额定载重Q;客户具有需求量qi与时间窗[Ei, Li]。若车辆早到或迟到,则通过惩罚项计入时间成本。研究的优化目标是在给定客户位置、仓库位置、车辆容量和车辆数量条件下,最小化总配送时间成本。随后,论文建立了11项数学约束,以保证车辆容量、节点唯一访问、仓库发车车辆数量等条件得到满足。进一步地,研究将该问题映射为MDP:全局静态状态Sg包含节点坐标、需求、时间窗、车容量、仓库数、车辆数、路网代价及惩罚因子α与β;车辆动态状态Sd记录每辆车在各时刻准备访问的节点及剩余载重;动作空间at对应于每一步为每辆车分配下一访问节点;状态转移函数τ在保证约束合法性的前提下同步更新所有车辆状态;奖励函数则定义为目标函数的相反数,即最小化行驶距离与时间惩罚之和。这一建模使复杂配送决策转化为可学习的时序控制过程。

在“Theory”部分,论文提出了用于求解MDVRPSTW的深度强化学习框架。研究人员强调,该框架围绕“特征选择—特征融合—约束过滤—概率决策—状态更新”这一链条展开。特征选择阶段保留与优化目标紧密相关的地理坐标、客户需求、时间窗、行驶成本与车辆载重等信息;特征融合阶段通过多头注意力提取节点之间的相关性,通过图神经网络识别仓库与客户的拓扑关系;约束过滤阶段由解码器借助掩码机制排除超载、重复服务等非法决策;概率决策阶段依据策略网络输出节点选择分布;状态更新阶段严格遵循MDP规则同步推进车辆路径。该结构体现出较强的可解释性,因为输出概率可直接对应当前条件下不同客户节点的服务优先级。

在“Encoder Architecture”部分,研究分别设计了节点编码器与图编码器。节点编码器首先将节点的坐标、需求和时间窗特征拼接后,经可学习线性映射生成初始嵌入h(0)i。在后续层中,多头注意力(MHA,Multi-head Attention)通过查询(Q)、键(K)和值(V)机制计算节点间相关性,再经残差连接、前馈网络与批归一化(BN,Batch Normalization)获得更新后的节点表示。图编码器则通过图神经网络聚合邻接节点的上下文信息,以可训练参数λ调整节点自信息与邻域信息的权重,最终形成图嵌入Hct。由此,模型能够同时获取节点属性层面的细粒度表示和图结构层面的全局关联信息。

在“Decoder Architecture”部分,研究人员说明了解码器如何基于编码特征生成路径。解码输入包括图嵌入Hct、前一时刻所选节点的嵌入hπt?1以及车辆剩余载重Dm,t,这些信息共同构成上下文向量hct。随后,解码器通过单头注意力计算上下文与候选节点嵌入之间的匹配得分ut,并经softmax函数转化为节点选择概率pt。在训练阶段,模型使用基于概率分布的采样解码,以增强探索能力;在测试阶段,则采用贪婪解码选择概率最高的节点,以获得稳定解。该设计使模型能够在满足多种约束条件的同时,逐步生成完整配送路径,直至所有客户完成服务。

在“Training Strategy”部分,研究采用策略梯度方法训练模型,以期望奖励L(θ|s)为优化目标。训练过程中设置策略网络与基线网络,前者负责输出动作概率并评估采样路径的总代价,后者用于提供基线回报RBL(s),从而降低梯度估计方差并稳定训练。参数更新使用Adam优化器完成。算法流程表明,模型在每个训练批次中不断采样动作、计算奖励、更新状态,并将采样回报与基线回报比较后反向传播更新参数。整个训练过程体现出典型的“离线训练—在线决策”范式,这是后续实现快速推理的重要基础。

在“Experiment”部分,研究人员构建了完整的实验验证体系。训练数据采用随机生成方式,仓库与客户均匀分布,时间窗与需求按照预设规则分配;测试则基于Solomon(1987)经典数据集,经样本筛选、坐标归一化、多仓扩展和约束适配处理后形成适用于MDVRPSTW的实例。实验按N = 20、50、100划分为小、中、大三种规模,并考虑2个或3个仓库、每仓2辆或3辆车等配置。模型训练使用PyTorch 2.7.1,在NVIDIA GeForce RTX 3090与Xeon Platinum 8255C平台上完成,隐藏层维度设为128,注意力头数为8,模型层数为3。对比基线包括精确算法VRPSolverEasy和元启发式算法GVNS。前者通过分解策略适配多仓问题,用于评估小规模全局最优边界及中大规模时间代价;后者通过“先分配、后优化”两阶段策略扩展到多车多仓场景,用于衡量本文方法在复杂约束下的竞争力。

在“Results”部分,论文给出了核心实验结果。首先,模型在总体目标值与时间表现上展现出明显优势。对于N = 20的小规模问题,深度强化学习模型虽然在目标值上与GVNS仍存在一定差距,但差异控制在较低水平,同时求解时间相比对比方法缩短超过96%,显示出强实用性。对于N = 50和N = 100的中大规模问题,模型表现出更显著的优势:相较GVNS,目标值分别降低27.7%和96.3%;相较VRPSolverEasy,也在目标值和时间上表现更优。论文指出,DRL模型在所有场景下的平均执行时间仅为GVNS的0.19%、VRPSolverEasy的0.67%,且时间稳定性良好。其次,在配置适应性方面,随着仓库和车辆数量变化,DRL模型的目标函数响应更敏感,表现出更强的多仓多车适应能力。

在“6.1. Generalization Experiments”部分,研究进一步验证了模型的泛化性能。考虑到实际配送中客户数量和车辆载重并非固定不变,研究将已在20、50、100节点规模上训练得到的模型用于不同规模或不同配置问题的求解。结果表明,训练后的模型在面对客户规模调整时仍能保持快速求解能力,说明该方法并非仅对固定规模实例有效,而具备一定跨规模迁移和部署潜力。这一结果对于前置仓即时配送的动态运营场景具有直接意义。

在“6.2. Parameter Sensitivity Analysis”部分,研究考察了图神经网络层数、注意力头数与编码器层数对模型性能的影响。结果表明,增加GNN层数对收敛效果提升并不明显,说明模型对该参数敏感性较低;增加注意力头数会带来参数量和计算量增加,但对效果提升不明显,甚至轻微削弱收敛表现;编码器层数则影响相对更显著,其中1层结构过浅,不利于训练与最终求解质量,3层时模型收敛更快且解质量较优,进一步增加到5层只带来有限改善。因此,论文最终采用3层编码器作为训练性能与计算复杂度之间的折中选择。

在“Discussion”部分,论文对结果进行了归纳。研究人员指出,该DRL模型呈现出明显的“规模依赖型性能反转”特征:在小规模问题上,与强基线相比主要体现为求解时间优势;在中大规模问题上,则同时取得目标值与效率的全面领先。这一现象说明,随着解空间复杂度提升,传统精确算法与元启发式算法的局限逐渐暴露,而基于图结构学习与注意力融合的DRL框架能够更有效地捕获仓库—客户之间的拓扑关系及多车辆同步决策规律。论文同时强调,MDP建模中全局静态状态与车辆动态状态的结合,为处理多仓、多车、软时间窗等复杂约束提供了有效机制;而“离线训练—在线决策”范式则使该方法特别适用于对响应速度要求极高的生鲜前置仓配送场景。研究意义不仅体现在算法性能提升上,也体现为为企业降低配送成本、缩短决策响应时间提供了可落地的技术路径。

论文“Conclusions”部分可译述如下:本文提出的深度强化学习模型在前置仓模式下求解MDVRPSTW问题时表现出优异性能。对于小规模问题(N = 20),该模型保持了较强竞争力,求解时间较GVNS和VRPSolverEasy分别缩短96.8%和96.2%,且与GVNS的目标值仅相差8.9%。对于中大规模问题(N = 50/100),该模型在解的质量与求解效率上均表现出全面优势,相较基线算法实现了27.7%至96.3%的目标值降低,并将求解时间稳定控制在3至10 s之间,有效避免了传统算法随规模扩大而出现的指数式增长。该模型还对复杂配置展现出显著适应性:随着仓库数量和车辆数量增加,目标值持续下降,最大降幅达到28.99%,且求解时间未出现指数增长,能够满足前置仓配送多样化配置需求。总体而言,该DRL模型较好地平衡了解的质量与求解效率,为生鲜电商前置仓配送优化提供了新的技术路径,填补了深度强化学习应用于MDVRPSTW的研究空白,并为未来研究更复杂车辆路径问题奠定了基础。与此同时,论文也指出,由于研究中对车辆时间变化进行了简化,模型与现实场景仍存在差异,后续工作可进一步引入动态需求约束、优化节点间距离—时间转换关系,并发展轻量化模型架构,以降低训练资源消耗并推动边缘设备部署。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

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

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号