一种协作式的进化强化学习方法，用于应对动态的取货和送货挑战

《TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW》：A collaborative evolutionary reinforcement learning approach to dynamic pickup and delivery challenges

　　杨晓英|李艺然|崔天祥|白瑞彬
中国宁波诺丁汉大学计算机科学学院，浙江省宁波市泰康东路199号，315100

**摘要**
在当今全球物流的背景下，大规模高效地配送商品已成为当务之急。其中心问题是动态取货与配送问题（Dynamic Pickup and Delivery Problem，简称DPDP）。由于订单的随机性和实时性的要求，DPDP本质上是复杂的，而在某些受严格装载协议限制的供应链变体中，这一问题尤为严峻，例如航空货物和侧装车队中采用的后进先出（Last-In-First-Out，LIFO）规则。传统的启发式方法在这种严格的约束下往往难以跳出局部最优解，而标准的强化学习（Reinforcement Learning，简称RL）则面临奖励稀疏和高维动作空间的难题。为了解决这些问题，我们提出了Evo-RL，一种全面的进化强化学习框架。与分离的混合方法不同，Evo-RL建立了一个协同的闭环：RL代理作为战略规划者，捕捉潜在的时空依赖性并生成可行的初始分配方案；而基于种群的遗传算法（Genetic Algorithm，简称GA）则作为优化引擎，对分配序列进行优化并提供密集的反馈信号。这种协作机制使RL代理能够从多样化的进化种群中学习，从而克服奖励稀疏的问题。我们在ICAPS 2021比赛的真实世界大规模DPDP基准测试中评估了我们的方法。实证结果表明，Evo-RL在解决方案质量和收敛速度方面显著优于现有的启发式方法和深度RL基线，证明了其在处理动态约束和大规模复杂性方面的有效性。

**1. 引言**
电子商务和按需服务的扩展推动了高效配送需求的增长。为此，动态取货与配送问题（DPDP）成为了一个关键焦点，旨在提升路线优化、调度效率和资源管理（Peppel等人，2022年）。DPDP引起了学术界和行业领袖的广泛关注，其相关性覆盖了多个领域，包括电子商务、按需服务和供应链物流。 recent trends表明，最后一公里配送量的指数级增长对城市交通和环境可持续性构成了重大挑战（Thomas等人，2020年）。因此，制定有效的DPDP解决方案对企业至关重要，使它们能够在动态的市场环境中有效应对并满足不断变化的消费者期望。

DPDP的概念深深植根于20世纪中叶，其前身是车辆路径问题（Vehicle Routing Problem，简称VRP），在20世纪50年代吸引了大量研究。VRP被广泛应用于运输、物流和分销等多个行业。直到20世纪90年代末，才引入了取货与配送问题（Pickup and Delivery Problem，简称PDP），作为VRP的一个具体分支，旨在提高货物或乘客的取货和配送效率（Ge等人，2025年）。与动态的DPDP不同，PDP是在静态环境中设定的，货物由卡车从起点运输到目的地，不包含新的、不可预测的订单（Yang等人，2025年）。随着时间的推移，PDP引起了研究社区的兴趣，发展成为最深入研究的组合优化挑战之一，为动态路由和调度的理论基础奠定了基础（Hao等人，2022年）。静态PDP的应用已经非常广泛，用于机器人技术、运输系统和物流等领域，证明了其在科学和工业领域的多功能性和持久相关性（Osaba等人，2019年）。PDP的主要目标是优化车辆的使用并最小化行驶距离，同时满足不同位置的客户需求。PDP的复杂性体现在它被归类为NP难问题，强调了寻找最优解的固有挑战。历史上，该领域的大部分研究集中在静态PDP上（Liu等人，2021年）。相比之下，PDP的动态方面研究较少，针对这些更为流动、实时的挑战的研究相对较少（Cai等人，2023年）。在航空货物行业或结构严格的物流车队中，一个常见的挑战是静态PDP变体，专注于将标准单位装载设备从货运代理的仓库运输到地面处理设施。这种特定模型受到一系列约束的限制，包括但不限于容量限制、特定时间窗口、对接考虑以及后进先出（LIFO）装载策略（Bombelli和Fazi，2022年）。特别是LIFO约束，由于使用了侧装车辆和狭窄的存储空间，较早装载的货物在未卸载后续物品之前无法访问，这在逻辑上大大增加了难度，因为新取货的简单插入可能会违反现有货物的卸载顺序。然而，这样的静态模型可能无法反映实际行业条件的复杂性，因为取货和配送需求可能会不可预测地变化，不确定性是一个常数因素。为了解决这一差距，引入了DPDP。DPDP提供了一个强大的框架，能够适应这些不断变化的场景，从而为企业提供在动态配送和物流环境中高效导航所需的灵活性。

DPDP涉及为一系列任务和车队确定最优的取货和配送顺序，同时考虑任务可用性和车辆状态等动态因素。实际上，使用DPDP的企业必须管理一个不仅能够处理即时生成的订单，而且能够及时将它们从起点运输到目的地的车队。在执行配送过程中，公司面临为货物选择合适车辆的关键任务，确保每个物品都能高效地从取货点移动到配送点。新订单的到来需要重新调整现有的配送路线和计划，这一过程必须与正在进行的操作无缝集成，同时遵守LIFO原则等约束。DPDP已被广泛应用于各种场景，包括长途运输、多模式运输和少于整车装载的运输。对于一些全球最大的制造商，如亚马逊和华为来说，DPDP尤为重要，它们依赖数百家工厂每年分发数十亿产品。鉴于配送请求量的庞大，即使物流效率有小幅提升，也能带来显著的好处。因此，开发有效的订单调度和卡车路线规划方法至关重要。有效解决DPDP问题可以显著提高这些公司以及许多物流和分销行业的运营效率、降低成本和客户满意度。

基于传统优化技术的精确方法可以用来解决小型DPDP实例（Savelsbergh和Sol，1998年）。其思想是将DPDP分解为多个静态问题，并使用线性或混合整数规划的算法进行优化。然而，当处理大规模DPDP实例时，这种精确方法的局限性变得尤为明显。由于可能组合的数量随着任务和车辆数量的增加而呈指数级增长，因此在典型的重大物流运营中，使用精确方法是不切实际的。启发式和元启发式方法，如禁忌搜索（Tabu Search，简称TS）（Gendreau等人，2006年）、遗传算法（Genetic Algorithm，简称GA）（Sáez等人，2008年）和进化算法（Evolutionary Algorithm，简称EA）（Mu?oz-Carpintero等人，2015年），也可以在合理的时间内找到高质量的DPDP解决方案，但一旦问题条件稍有变化，就需要进行修订（Cai等人，2024年）。这些算法作为黑盒优化器非常有效，即用于解决具有复杂数学形式化的问题。然而，它们无法利用环境中可用的潜在动态反馈信号，这可能限制了它们在动态和复杂问题领域找到最优解的能力。由于制造过程和需求的不可预测性，DPDP中的大多数配送需求都无法提前预测。同时，动态变化需要实时决策和快速适应任务分配和调度的能力。因此，由于高度的不确定性，实际上很难部署启发式和元启发式方法。

最近，强化学习（Reinforcement Learning，简称RL）算法在顺序决策问题中已被证明是有效的，尤其是在存在不确定性的情况下（Cui等人，2023年；Cui等人，2024年；Jin等人，2023年；Zhang等人，2022年）。特别是，RL具有提升启发式和元启发式算法“视野短浅”的潜力（Kool等人，2019年）。然而，当应用于动态工业问题（如DPDP）时，RL方法遇到了固有的挑战，主要是探索-利用权衡、约束处理和奖励稀疏（Dulac-Arnold等人，2021年；Fruit等人，2018年）。虽然将RL与局部搜索策略（如自适应大邻域搜索Adaptive Large Neighborhood Search，简称ALNS）相结合的混合方法已经成熟，但它们通常依赖于单轨迹搜索机制。相比之下，基于种群的进化方法在这一方面具有明显的优势。与ALNS不同，进化方法（如GA）维护了多样化的解决方案种群。这种多样性为RL代理生成了丰富的探索数据流，有效缓解了奖励稀疏问题，并防止了在高维动作空间中的策略崩溃。

在ICAPS 2021比赛中，华为提高了动态DPDP挑战的真实性和复杂性（Hao等人，2022年）。该基准测试关注了一对一PDP的实际变体，包括车辆和订单信息等输入、容量、时间窗口、码头可用性和LIFO装载策略等约束、输出以及目标函数。在这项工作中，我们提出了应用于原始ICAPS 2021基准测试的进化强化学习（Evo-RL）框架。关键的是，我们改进了问题表述（Hao等人，2022年），以明确捕捉模拟器的固有动态。通过数学建模随机因素，特别是配送时间波动和行驶距离变化，我们弥合了理论问题与实际随机执行环境之间的差距。所提出的Evo-RL框架通过结合GA和RL的优势来应对这些独特挑战。具体而言，Evo-RL将DPDP分解为两个可管理的子问题：订单分配（由RL处理）和路线规划（由GA优化）。GA组件维护了一个多样化的解决方案种群，并使用进化操作广泛探索解决方案空间，有助于克服传统RL中的探索局限性和奖励稀疏问题。同时，RL代理利用基于我们修改问题表述的内在奖励函数，在动态条件下指导学习。

我们的主要贡献如下：
• 我们提出了一种Evo-RL方法，将GA与传统RL技术协同整合。所提出的方法利用GA通过迭代过程增强和细化RL最初生成的解决方案，同时通过进化操作确保进化后的解决方案仍然符合预定义的约束。
• 我们提出了一种数学模型，明确考虑随机配送时间和行驶距离，将这些不确定性整合到标准DPDP表述中。该模型支持了一个新颖的内在奖励函数，指导RL代理学习稳健的策略，确保在现实世界中的性能稳定性。
• 所提出的Evo-RL方法使用了2021年ICAPS比赛的真实世界基准测试进行了严格的实证测试。验证过程的结果表明，所提出的Evo-RL方法优于现有的启发式方法和传统DRL方法。

本文的其余部分组织如下：第2节提供了相关研究的文献回顾。第3节描述了问题并介绍了修改后的数学模型。第4节介绍了我们提出的Evo-RL框架。第5节报告了实验结果。第6节总结了本文。

**2. 相关工作**
本节回顾了PDP从其静态起源到动态变体的演变过程，随后详细分析了问题约束和方法论方法的全面回顾。

**2.1. 问题变体、约束和复杂性**
PDP一直是研究最广泛的网络物流挑战之一，在最近几十年受到了重大关注（Cai等人，2023年）。虽然早期的研究集中在静态环境中，但动态路径分配（DPDP）代表了处理实时操作的一个关键分支。DPDP通常被用于描述从多个起点到多个目的地的产品运输，在Psaraftis等人（2016年）的研究中有更详细的说明。DPDP在门到门运输服务和快递服务中具有实际应用价值。由于其复杂性较高，关于DPDP的研究不如传统车辆路径分配（VRP）的研究普遍（例如Bai等人，2023年；Jia等人，2021年）。为了更好地理解DPDP并全面分析其中固有的约束条件，应考虑以下约束和不确定因素：

- ** pickup and delivery constraint（取货和送货约束）**：该约束要求每件商品必须首先由同一辆车取走，然后再送到指定的目的地，以确保在运输过程中商品不会混淆或错放。
- ** Dock availability constraint（码头可用性约束）**：取货和送货地点的码头可用性会影响调度和运营效率，这模拟了算法必须安排码头设施以实现快速装卸的现实世界场景。
- ** Vehicles capacity constraint（车辆容量约束）**：该约束确保总负载不超过车辆的最大容量。
- ** Loading cost constraint（装载成本约束）**：该约束考虑了装载商品所需的时间，旨在最小化装载时间，这可能会根据商品的大小或复杂性而有所不同。
- ** Time windows constraint（时间窗口约束）**：时间窗口约束规定每个订单的完成时间不得超过承诺的最大服务时间，但在某些情况下可以放宽为软约束。
- ** Split demand constraint（拆分需求约束）**：当订单的需求超过单辆车的容量时，拆分需求约束要求将订单分成较小的单元（例如一个托盘），每个单元由不同的车辆负责运输，以适应容量限制。
- ** LIFO constraint（后进先出约束）**：在某些情况下，后进先出约束意味着最近取走的商品首先被送达，从而最小化装卸时间。
- ** Dynamic demand（动态需求）**：动态需求反映了由于客户行为或调度变化而导致的订单变化，需要采取适应性策略。
- ** Uncertain order（不确定订单）**：不确定订单约束处理在计划或调度时订单的未知可用性或特性，要求在资源分配和调度方面具有灵活性。
- ** Delivery time（交货时间）**：每个订单必须在规定的时间框架内送达，完成时间不得超过承诺的最大服务时间，以避免罚款或客户不满；因此，需要灵活的调度和路由策略来适应实时变化并优化交货时间。
- ** Delivery distance（交货距离）**：最后，最小化总交货距离对于减少燃料消耗、运输成本和环境影响至关重要，算法应根据不确定性不断更新路线，以实现高效且经济高效的交货操作。

表1总结了有关DPDP的相关研究，并将其与上述约束进行了比较。与之前仅解决这些挑战子集的研究不同，我们提出的工作旨在解决所有约束和不确定因素，展示了我们问题表述的全面性。

### 2.2 方法论方法
当前解决DPDP的方法可以大致分为传统优化（精确和启发式）、序贯决策制定（ADP和RL）以及混合方法。

#### 2.2.1 传统优化：精确和启发式方法
第一类方法通过将动态问题分解成一系列静态子问题来处理DPDP。Savelsbergh和Sol（1998年）引入了一种名为DRIVE的独立车辆动态路由算法。该算法使用当前的交付订单子集和滚动时域框架将目标问题分解为一系列静态优化问题。为了在动态环境中平衡解决方案的速度和质量，采用近似方法、不完整的优化方法以及复杂的列管理策略来解决静态优化问题。Swihart和Papastavrou（1999年）提出了一个基于泊松过程的DPDP随机和动态模型。最近，Wolfinger和Salazar-González（2021年）开发了一种用于拆分负载的分支剪枝方法，而Jeong和Moon（2024年）将精确优化应用于自主交付机器人。然而，这些方法由于其每个静态子问题都必须依次优化，因此计算复杂度较高。

为进一步平衡解决方案质量和计算时间，元启发式算法提供了另一种稳健的替代方案。这些方法可以大致分为单点方法和基于种群的方法。单点元启发式方法侧重于使用局部搜索、模拟退火和Tabu Search (TS) 等机制迭代改进单个候选解决方案。例如，Karami等人（Mitrovi?-Mini?等人，2004年）提出了一种基于滚动时域的方法，通过结合启发式和局部搜索来处理当天取货和送货请求。然而，由于缺乏完整的未来信息，滚动时域方法不能保证在整个时间范围内达到全局最优。Gendreau等人（2006年）开发了一种基于驱逐链的TS启发式方法来探索新解决方案。尽管这些方法对局部细化有效，但由于探索能力有限，它们有可能陷入局部最优解。相比之下，基于种群的元启发式方法（如遗传算法GA和粒子群优化PSO）维护了一组多样化的解决方案，以全局探索搜索空间（Omidvar等人，2021年）。这些方法利用选择、交叉和变异等操作在代际之间进化出更优的解决方案。基于种群的算法已在VRP领域得到了广泛的应用（Duan等人，2021年；Feng等人，2020年；Hu等人，2025b年；Jia等人，2021年；Xiao等人，2019年；Xue等人，2025年）。针对DPDP，最近的工作将进化框架与局部搜索机制结合起来。Mu?oz-Carpintero等人（2015年）提出了一种通过多目标优化调整参数的EA变体，以在性能和计算之间进行权衡。值得注意的是，Cai等人（2024年）提出了一种结合Tabu Search (MOEA/D-TS)的分解式多目标进化算法，以平衡多样性和收敛性。然而，尽管这些方法具有全局搜索能力，它们通常会为每个新事件从头开始重新优化，对即时需求反应迟缓，无法学习长期模式。

#### 2.2.2 顺序决策制定：从ADP到深度强化学习
为了解决DPDP的顺序性，研究人员将问题建模为马尔可夫决策过程（MDP）。近似动态规划（ADP）和强化学习（RL）都旨在通过近似未来奖励来解决这些MDP，以缓解“维度灾难”（Mes和Rivera，2017年）。尽管传统上是不同的领域，但它们越来越多地被视为等效的框架，其中ADP通常强调基于模型的价值近似，而RL侧重于数据驱动的学习。

在物流背景下，ADP已广泛应用于处理随机性。最近的研究证明了ADP在复杂场景中的有效性：Agussurja等人（2019年）利用状态聚合处理随机共享；Al-Kanj等人（2020年）将其应用于自主电动车队规划；Mousavi等人（2024年）开发了一个用于具有时空不确定性的群体配送的ADP框架。Chakrabarty等人（2020年）进一步建立了这种动态系统中安全近似的理论基础。在这个框架内，两种主要的近似策略是成本函数近似（CFA）和价值函数近似（VFA）。成本函数近似方法旨在隐式地处理约束或目标函数中的不确定性。例如，可以引入安全缓冲（Ulmer等人，2021年）到取货时间中以适应潜在的延迟。基于场景的方法也属于这一范畴，通过采样未来实现来优化当前决策。然而，这些方法通常面临实时模拟时间范围的计算负担。相反，价值函数近似（VFA）方法旨在显式估计当前状态的长期价值。正如Chen等人（2022年）所探讨的，VFA通过近似价值函数来指导决策，而无需进行全面的前瞻。VFA中的一个关键挑战是表示庞大的状态空间。传统上，这依赖于特定领域的特征工程，例如手动聚合车辆位置或需求密度。然而，为高度受限的DPDP设计有效的手动特征需要深厚的领域专业知识，并限制了可扩展性（Ghiani等人，2022年）。

为了自动化特征提取和策略学习，深度强化学习（DRL）作为一种强大的替代方案出现了（Kool等人，2019年）。基于注意力的模型（Xu等人，2021年）在捕捉长距离依赖性方面明显优于循环神经网络（RNNs）。基于这一架构，Tian等人（2025年）最近提出了一个基于Transformer Model的Actor-Critic算法，以加速近似最优解的计算。为了管理高维动作空间，研究人员采用了分层分解。Ma等人（2021年）提出了一个分离订单发布和路由的双层框架。这种分层原则也得到了最近进展的验证：Deng等人（2025年）在零售不确定性下应用了分层RL进行生产控制，而Hu等人（2025a）利用多智能体DRL进行多层级库存优化。在状态表示方面，图卷积网络（GCNs）已成为发现拓扑关系的标准方法。例如，Chen等人（2024年）使用GCNs进行特征预测以提高决策准确性。然而，大多数现有的基于图的方法将所有节点视为同质的。最近的研究表明，异构图注意力网络（Heterogeneous Graph Attention Networks）可以更好地捕捉DPDP中的不对称约束（Li等人，2021年）。尽管有这些潜力，但由于奖励稀疏和长计划时间范围内的信用分配困难，将纯RL应用于DPDP仍然具有挑战性。

#### 2.2.3 混合方法：结合学习和搜索
为了弥补单独使用RL的局限性，特别是奖励稀疏和在复杂环境中的探索效率低下（Guo等人，2025年），最近的研究探索了结合RL的学习能力和启发式局部细化的混合方法。一个常见的方向是将RL与单点搜索方法结合起来。例如，Zhang等人（2023年）提出了一种结合模型辅助RL和自适应大范围搜索（ALNS）的模型，用于同步运输。虽然这些方法对特定实例有效，但它们本质上依赖于单轨迹进化。它们迭代细化一个解决方案，当奖励景观具有欺骗性时可能会陷入局部最优解，并在大规模动态更新期间产生高计算成本。相比之下，将EA与RL结合（Evo-RL）提供了另一种解决探索-利用权衡的方法（Colas等人，2018年）。与单点混合方法不同，Evo-RL维护了多样化的策略或解决方案种群。进化操作符（选择、交叉、变异）作为全局探索机制，即使在RL代理基于梯度的学习因反馈稀疏而停滞时，也能发现高质量的“踏脚石”解决方案（Khadka和Tumer，2018年）。

虽然传统的RL方法在复杂的高维环境中经常面临探索困难，但Evo-RL有效地结合了RL的高效局部搜索能力和EA的全局探索机制，探索了更广泛的策略范围，可能会发现单独使用任一方法都可能无法发现的新颖和最优解决方案（Conti等人，2018年）。几种著名的框架验证了这种协同作用。进化强化学习（ERL）（Khadka和Tumer，2018年）结合了EA种群来为DRL训练生成多样化体验。深度进化强化学习（DERL）（Gupta等人，2021年）扩展了这一点，以共同优化代理形态和控制。然而，这些框架主要设计用于连续控制任务（例如，机器人运动）。由于问题的离散、组合性质以及严格的操作约束（如LIFO和时间窗口），它们直接应用于DPDP并不容易。此外，缺乏针对物流约束的特定适应机制限制了现有Evo-RL基准的通用性。为了解决这一差距，我们的工作提出了一个定制的Evo-RL框架，将基于种群的探索原则适应DPDP的特定离散约束，有效缓解了奖励稀疏问题，同时确保解决方案的可行性。

### 3. 问题描述
#### 3.1 问题定义
本节讨论了现实世界物流场景中的DPDP，特别是在像华为这样的大型企业中。这些企业必须建立庞大的运输网络，每年在数百个工厂内部转移数十亿件产品。然而，由于客户需求和相应生产过程的不确定性，大多数交付订单无法提前完全确定。这些交付订单包括取货和送货工厂、商品数量以及所需周转时间等信息，是根据实际运营数据随机选择的。为了履行这些订单，常规安排了一支统一的车辆车队。

图1将问题可视化为开放式DPDP，其中车辆路线不受返回码头的限制。该示例突出显示了一个受限环境，车辆从之前的结束点出发，工厂使用单个可用码头进行操作。

**下载：下载高分辨率图片（309KB）**
**下载：下载全尺寸图片**
图1.DPDP的简要情况可以描述如下：
1. 订单o1和订单o2被分配给工厂F1（橙色卡车）。卡车从F1出发，依次取货完成这两个订单（用↑表示）。取货完成后，橙色卡车离开F1前往F3交付订单o2（o2↓），并停留在F3（o1?）。然后卡车继续前往F4交付订单o1（o1↓），但由于绿色卡车正在F4的码头装载订单o3（o3↓）并取货订单o7（o7↓），所以必须等待。
2. 订单o3和订单o7被分配给工厂F4（绿色卡车）。卡车取货完成订单o3（↑）并交付订单o7（↓）。绿色卡车在F4完成操作后，前往F7取货订单o3（o3↑）。
3. 蓝色卡车（标记为S，开始）位于F2，处于等待状态，准备开始作业。订单o5和订单o6被分配给这辆卡车。它前往F4取货（o5↑, o6↑），然后分别将订单o5（o5↓）和订单o6（o6↓）交付到F4。
4. 货车行驶路线用彩色箭头表示：橙色卡车用虚线箭头，绿色卡车用实线箭头，蓝色卡车用虚线箭头。每个工厂的码头数量有限，当多辆车同时需要使用同一码头时，可能会出现冲突。（关于图例中颜色的解释，请参阅本文的网络版本。）

此外，DPDP受到多种约束的限制，包括取货和交付时间窗口、车辆容量、后进先出（LIFO）装载方式、装载成本、拆分需求以及码头可用性。每个工厂的码头数量有限，这意味着一旦所有码头都被占用，后续到达的车辆必须排队等待。码头限制会显著影响订单的延误情况，从而影响客户对服务的满意度。调度订单指定了要取货的商品数量、取货节点、装卸时间以及所需的时间窗口。工厂全天可以动态生成交付订单，每个设施既可以作为取货地点也可以作为交付地点。码头可用性和车辆移动涉及复杂的随机交互，这些由模拟器环境处理，模拟器环境类似于一个难以用静态线性约束完全描述的“黑盒”状态转换函数。因此，下面提供的数学模型主要用于描述目标和工作范围，并非用于精确求解的混合整数线性规划（MILP）模型。我们的目标是将每个订单分配给车队，以减少订单总体延误、降低车辆平均行驶距离、最小化运营成本并提高服务质量。为此，我们考虑了时间窗口、商品类型、车辆容量以及取货和交付节点等随机因素，并在决策过程中考虑了容量限制和转运地点。详细信息将在下一节中说明。

**3.2 数学模型**
由于该问题是在模拟环境中使用基于学习的方法解决的，我们提出了一个描述性模型来形式化优化目标和约束条件。

**3.2.1 输入和决策变量**
DPDP的通用输入包括：
- 一组工厂节点F={Fj∣j=1,2,?,J}，这些节点可以是取货节点也可以是交付节点。每个节点都有有限数量的码头Dj={D1,D2,?,DJ}用于装卸货物，以及允许的工作班次。如果所有码头都被占用，新到的车辆必须等待空位。货物装卸只能在特定的工作班次进行。
- 一个道路系统R=(F,A)，这是一个完整的有向图。F={Fj∣j=1,2,?,J}是工厂节点集合，A={(m,n)∣m,n∈Fj}是边集。每条边(m, n)都与运输时间tm,ntt和运输距离dm,ntt相关联。
- 一组随机生成的订单O={oi∣i=1,2,?,I}，每个订单包含以下信息：
- Fipn：取货工厂节点
- Fidn：交付工厂节点
- Qi：订单中的货物数量（Qistandard表示标准托盘数量，Qismall表示小托盘数量，Qibox表示箱子数量；注意两个小托盘等于一个标准托盘，两个箱子等于一个小托盘）
- tigt：订单到达时间
- ticct：订单的承诺完成时间
- 蓝色卡车（标记为S，开始）处于等待状态，准备开始作业。

**3.2.2 目标函数**
根据问题描述，核心决策变量是路线计划RP={rpk∣k=1,?,K}，其中每个rk,i(t)包含特定访问的详细操作信息（如取货或交付类型）。目标函数包括：
- **f1**：最小化所有订单的总延误时间（公式（1）
- **f2**：最小化车辆的平均行驶距离（公式（3）
- **f3**：同时考虑多个目标，如减少等待时间和行驶距离（公式（4）

**3.2.3 约束条件**
- **约束条件（5）**：确保所有订单得到有效处理
- **约束条件（6）**：时间窗口限制
- **约束条件（7）**：后进先出装载规则
- **约束条件（8）**：货物装载量限制
- **约束条件（9）**：动态资源限制
- **约束条件（10）**：模拟器验证规则

**3.2.4 不确定因素**
在实际交付过程中，客户偏好和订单时间窗口等不确定因素会增加车辆路线规划的难度（Zhou等，2020）。在现实中，需要考虑几个不确定性的来源，包括由于交通堵塞、恶劣天气和其他变量导致的不可预测的旅行时间，这些因素可能会引起延误，从而导致取货和交付失败。此外，车辆的行驶距离可能会出乎意料地比预期长，进而导致服务中断和计划路线的改变。这些不确定性会显著影响交货时间表，因此需要制定有效的策略来管理和缓解它们。在我们的模型中，我们将前面提到的因素合并为时间和距离的不确定性，并简化为两个参数Ψit和Ψid，这两个参数作为订单满意度水平的指标。

尽管存在上述不确定性来源，主要目标仍然是确保订单oi能够在预期的到达时间窗口[tiet??,tiet?+]内及时送达，该时间窗口具有下限和上限。因此，我们提出了一种基于原始模型的新模型，考虑了与预期订单到达时间tiet?的未知值和概率分布相关的不确定性。进一步分析是为了减轻不确定性对解决方案的影响。实际到达时间tift可以根据方程（2）计算得出。因此，在构建优化模型时，需要对前述方程进行相应的调整，如图2所示。具体来说，当车辆在tigt和ticct之间到达时，订单满意度为1；当车辆在ticct和tiet?+之间到达时，订单满意度会逐渐降低，降低的比例为1-(max(tiet,tiet?+)?ticct)；如果车辆在tiet?+之后到达，则订单满意度为-∞。这表明如果车辆在某个时间之后到达，则认为订单满意度极低，在优化过程中将会被丢弃。因此，在实际情况中，理论下的下限不会影响奖励函数。

下载：下载高清晰度图片（207KB）
下载：下载全尺寸图片
图2. 带满意度的订单交付时间线。

关于交付时间的订单满意度Ψit定义如下：
(11) Ψit = {1 如果 tigt ≤ tift ≤ ticct; ?(max(tiet,tiet?+) ? ticct) 如果 ticct < tift < tiet?+; ?∞ 如果 tiet ≥ tiet?+}

除了考虑到达时间外，减少车辆vk为订单oi行驶的距离di,ked也是DPDP问题的次要目标。预期的行驶距离窗口di,ked?可以表示为一个区间[dDi,ked??,di,ked?+]，具有下限和上限。为了考虑与预期行驶距离di,ked?的未知值和概率分布相关的不确定性，我们可以基于原始模型开发一个稳健的优化模型。为了处理这种不确定性，我们可以定义一个满意度函数Ψid（如方程（12）所示），它将实际行驶距离di,kad映射到订单满意度值。实际行驶距离di,kad可以根据方程（3）计算得出。然而，在存在不确定性的情况下，需要对这个方程进行修改，以确保实际行驶距离落在预期的行驶距离窗口内。具体来说，当车辆的行驶距离在di,ked??和di,ked?+之间时，订单满意度在（0,1）范围内；如果车辆的行驶距离大于di,ked?+，则订单满意度为-∞。

关于交付距离的订单满意度Ψid定义如下：
(12) Ψid = { (0,1) 如果 di,ked?? ≤ di,kad ≤ di,ked?+; ?∞ 如果 di,kad > di,ked?+ }

其中，di,ked??表示车辆v交付订单1时的最小行驶距离；di,ked?+表示车辆v交付多个订单i∈I时的最大行驶距离，其中i=1,...,n，di,ked?+ = dFkbn,F1bn + ∑i=1IdFibn,Fifn+∑i=1IdFifn,Fi+1bn。这里，Fkbn是车辆的起始位置，Fibn/Fifn分别对应于订单i或其后续订单的起点和终点。

通过量化订单满意度，我们可以将其纳入奖励函数。在这种情况下，我们为未完成的订单定义了一个惩罚值作为奖励函数的一部分，从而鼓励算法在规划过程中优先考虑订单满意度，这在第4.3.3.4节中有说明。

**提出的Evo-RL方法**

在本节中，我们首先简要概述所提出的Evo-RL框架，然后再介绍其组件的详细信息。

**4.1. 通用框架**

进化强化学习（Evo-RL）被提出作为一个整体混合框架，它结合了DRL的序列决策效率和GA的全局搜索能力。与分离的模块化方法不同，Evo-RL在两个组件之间建立了相互反馈的循环。RL代理作为策略驱动的初始化机制，提供可行的、高质量的解决方案种子，以限制和指导进化搜索。相反，GA作为一个基于种群的优化引擎，不仅改进了这些初始解决方案，还通过生成多样化的经验轨迹丰富了训练环境。这种循环整合特别解决了DPDP的固有复杂性：RL组件捕捉到潜在的时空依赖性，构建空间上连贯的订单批次，为后续的LIFO兼容排序奠定了基础，而GA利用其种群动态提供密集的中间反馈信号，从而缓解了奖励稀疏问题并稳定了RL训练。

Evo-RL的协同架构相比单独使用RL或元启发式算法具有明显优势。标准RL通常面临着DPDP中固有的奖励稀疏问题，其中反馈往往要等到路线完成才能获得，以及动作空间的巨大维度。Evo-RL通过利用进化种群生成中间评估，有效地增强了奖励信号。相比之下，传统的元启发式算法（如GA或ALNS）在严格的LIFO和时间窗口约束下往往难以找到可行的起点，导致算法在尝试修复无效解决方案时效率低下。在我们的框架中，RL代理捕捉到了订单的潜在时空依赖性，为GA提供了结构优化的初始簇。这有效地缩减了搜索空间，使进化组件能够专注于优化而非修复可行性。

图3展示了Evo-RL过程的实例化。工作流程从RL代理将高维状态观测（包括订单属性oi和车辆状态vk）映射到一个战略性的订单分配计划OA开始。这种分配有效地将全局问题划分为每个车辆的局部子问题。为了弥合RL的高层分配和特定的LIFO操作约束之间的差距，采用了启发式排序策略作为翻译层。这一层将RL的空间聚类转换为时间有效的序列ok,1,ok,2,...,ok,Lk，确保每个初始路线计划RP严格遵循承诺的完成时间和装载约束。

这些由RL生成的序列作为后续进化阶段的高质量种子种群。然后GA通过保持约束的交叉和变异操作进行更广泛的探索。这些操作执行双层次优化：它们不仅在单个路线内重新排序订单（路线内优化），还在不同车辆之间交换订单（路线间优化）。这使得GA能够纠正RL代理做出的次优分配决策，同时严格遵循复杂的约束。最后，GA生成的改进路线计划被反向映射到RL的动作空间（订单分配）。这些精细的分配及其适应度评估作为“伪奖励”来更新RL策略。通过让RL代理接触到GA发现的这些更好的变体，该框架闭合了学习循环，使RL代理能够逐渐生成更多符合进化要求的、全局最优的初始分配。

**4.2. DPDP的MDP建模**

在本节中，我们正式定义了问题环境和建模。马尔可夫决策过程（MDP）根据元组(S,A,P(·),Rt(·),γ)来表示。下面我们将详细说明这些为DPDP context量身定制的组件的定义。

**4.2.1. 环境动态**

我们的框架使用了华为ICAPS比赛提供的高保真DPDP模拟器，将提供结果检查方法来评估算法在规划范围内（例如一天）的性能。这个黑盒环境通过准确模拟车辆运动、码头操作和订单履行来维持严格的操作保真度，同时严格施加现实世界的约束，包括LIFO装载、时间窗口和容量限制。模拟器通过离散时间步骤运行，在每个时间间隔t提供可观察的状态信息，同时内部管理复杂的系统动态。转移概率核P(st+1∣st,at)表示在当前状态st执行动作后进入下一个状态st+1的概率。然而，由于复杂的不确定性，明确建模P是具有挑战性的。因此，我们的试错学习范式变得至关重要，因为系统的转移动态只能通过经验采样得出。

**4.2.2. 状态空间**

SS表示状态空间或状态集，它包括DPDP中订单、车辆和工厂的当前状态。具体来说，在每个时间步骤t，代理观察到{Oi,t,Ft,Vt}：
- 每个订单在时间t的观测由Oi,t={Fi,tfn,Fi,tbn,Qi,t,ti,tgt,tm,n,t,tk,p,m,tlt}表示，其中：
- Fi,tfn和Fi,tbn分别表示订单oi的目的地和起点工厂。
- Qi,t表示订单oi的货物数量。
- ti,tgt是订单oi的生成时间。
- tm,n,t指定工厂m和n之间的运输时间。
- tk,m,tlt表示车辆vk在节点m装载订单oi的时间。
- 时间t的工厂状态观测包括Ft={Dm,t,Nm,ttc}，其中：
- Dm,t表示工厂Fm的可用码头数量。
- Nm,ttc表示时间t工厂中的车辆数量。
- 每个车辆在时间t的观测由Vt={Fk,tcn,Fk,tdn,ti,k,tet,qk,ttc∣vk∈Vt}表示，其中：
- Fk,tcn是车辆vk当前或最近的出发工厂。
- Fk,tdn是车辆vk的下一个目的地工厂。
- ti,k,tet是当前订单在车辆vk上的预期到达时间。
- qk,ttc是分配给车辆vk在其估计路线上的总货物负载。

这种丰富的状态表示整合了关于订单、工厂操作和车辆物流的重要数据，为RL代理提供了推导出最佳车辆选择策略所需的信息。

**4.2.3. 行动空间**

在我们的混合框架中，我们区分了RL代理生成的决策行动和模拟器所需的执行行动。A表示RL代理的决策行动空间，它包括将车辆分配给订单。在每个时间步骤t，RL代理生成一个分配行动at∈At。行动at={vk1,?,vkn∣vki∈V}表示被分配给订单oi的具体车辆vk。这个行动空间是离散的，决定了订单的战略分组。由于模拟器需要一个具体的访问序列（路线计划RP）来执行物流操作，RL代理的分配at作为高级指令。这个指令通过一个确定性变换层（启发式排序 + GA优化）来生成最终的 executable路线计划RP。需要注意的是，虽然RL代理不直接输出路线序列，但Executable RP的质量从根本上受到RL的分配at的可行性的限制。如果RL代理将时空不兼容的订单分组在一起，那么任何下游排序或进化操作都无法恢复有效的路线。因此，MDP被建模为RL代理学习优化订单簇的潜在可行性，将后续的路线能力视为环境转移动态的一部分。

**4.2.4. 奖励结构**

DPDP的主要目标是通过最小化总超时、等待时间和行驶距离来维持高效的运输操作。正式地，环境根据路线计划的执行质量提供稀疏的反馈信号。我们定义了基本的目标函数（环境奖励）如下：
(13) Renv = ?[α·(∑?oimax(0,tift?ticct))+β·(∑kDistance(vk)]
其中α和β是权重系数。然而，对于RL代理来说，直接最大化这种稀疏奖励是困难的。因此，在后续的算法部分（第4.3节），我们设计了一个密集的、增强的奖励函数来指导训练过程。

**4.3. Evo-RL优化算法**

基于MDP的建模，我们采用Evo-RL算法来解决问题。本小节详细介绍了通过PPO进行的策略优化、通过GA进行的进化搜索以及它们的协作训练机制。

**4.3.1. RL策略优化和奖励塑造**

我们采用Proximal Policy Optimization (PPO)这种方法来解决MDP。为了评估策略π，我们定义了相应的动作价值函数（Q函数）Qπ:S×A→R和状态价值函数Vπ:S→R，如下所示：
(14) Qπ(s,a) = (1?γ)·E[∑t=0∞γt·Rt(st,at,st+1)∣s0=s,a0=a,at～π(·∣st),st+1～P(·∣st,at)],
(15) Vπ(s) = (1?γ)·E[∑t=0∞γt·Rt(st,at,st+1)∣s0=s,at～π(·∣st),st+1～P(·∣st,at)]。
优势函数Aπ(s, a)表示为
(16) Aπ(s, a) = Qπ(s,a) ? Vπ(s)

PPO在第m次迭代时的策略参数θ通过以下方式更新：
(17) θm+1 ? argmaxθE^[πθ(at∣st)πθm(at∣st)·Am(st,at)?β·KL(πθ(at∣st)∥πθm(at∣st)]

为了应对过拟合问题，我们使用带有截断目标的RPPO。这个简化的目标涉及到计算比率 ?t(θ)=πθ(at∣st)/πθm(at∣st)。为了克服环境奖励的稀疏性并强制执行可行性约束，我们为强化学习（RL）代理设计了一个复合奖励函数。该函数通过内在信号和惩罚项来增强真实环境奖励。用于更新策略的总奖励 rt 定义如下：

1. **内在效率奖励**：鼓励代理在每一步减少延迟和距离：
$$\text{intrinsic} = \lambda_1\left(\sum_{t=0}^T \min(\text{?t}(θ)\cdot A_m(st,at), \text{clip}(\text{?t}(θ), 1-\epsilon, 1+\epsilon)\cdot A_m(st,at)\right)$$

2. **可行性惩罚**：为了强制执行第4.2节中讨论的严格约束（后进先出（LIFO）和时间窗口），当RL的分配导致不可行路径时，我们应用惩罚 rfeasibility：
$$\text{feasibility} = \lambda_4\sum_{t=0}^T \left(\Yu_it^t + Yu_id^t\right)$$
其中 $\Yu_it^t$ 和 $\Yu_id^t$ 分别惩罚对时间窗口和行程限制的违反：
$$\begin{cases}
1 & \text{如果 } t_i \leq t_{icct} \leq t_{icct}, \\
0 & \text{其他情况}
\end{cases}$$

3. **协作反馈（伪奖励）**：利用Evo-RL框架，我们将遗传算法（GA）种群的相对性能纳入奖励中：
$$\text{rcollaborative} = \lambda_3\left(\psi_t - \rho_t\right)$$
其中 $\psi_t$ 和 $\rho_t$ 分别表示RL解决方案和最佳GA演化解决方案的得分。这项措施鼓励RL代理生成更合适的“种子”以用于演化过程。

4.3.2. 遗传算法（GA）用于路线规划
在这项工作中，我们选择GA而不是基于轨迹的元启发式方法来进行路线规划，以专门解决RL训练中奖励稀疏的问题。Evo-RL框架的有效性在于将多样化、高质量的解决方案数据反馈给RL代理作为重放缓冲区。基于种群的GA在每一代中并行生成多个多样化的候选解决方案。这些候选解决方案由高效评估器进行评估，产生“伪奖励”，为RL代理提供密集且丰富的反馈信号，这是单轨迹方法（如ALNS）难以提供的。GA在其搜索和优化过程中使用遗传操作符，通常包括交叉操作符和变异操作符。交叉操作符的目的是在给定状态空间内组合两个输入解决方案，从而生成新的路线计划。RL算法获得的输出被重新构建为每辆车的染色体，染色体包含每辆车的顺序列表：$H_k = o_k,1, o_k,2,\ldots, o_k,l$。此外，初始解决方案种群对于探索解决方案空间和算法的收敛速度至关重要。其中一个初始解决方案可以来自RL算法，由于RL能够学习和适应问题环境，因此可能代表一个高质量的起点。剩余的解决方案可以通过随机生成创建，确保初始种群中的遗传多样性。这种多样性很重要，因为它允许GA探索解决方案空间的不同区域，防止过早收敛到次优解决方案，并在整个演化过程中保持遗传多样性。对于每辆车，可以获得遵循LIFO原则的排序顺序序列：$o_k,1, o_k,2,\ldots, o_k,l$。

5. 实验结果
我们使用华为ICAPS 2021数据集来评估我们提出的Evo-RL算法在动态路径分配问题（DPDP）上的有效性。该数据集全面代表了现实世界的物流操作，包括配送订单、订单交易的动态、车辆约束以及64个基准案例中153家工厂的详细信息。配送订单的信息包括取货和送货工厂、货物数量和时间要求。这些订单随机发生，并由同类型的车辆车队定期服务，为测试我们的算法提供了一个真实且具有挑战性的环境。我们使用华为竞赛平台提供的具有内置结果验证的高保真模拟器。该模拟环境具有闭环交互机制，能够忠实复制现实世界的物流操作，同时严格遵守所有操作约束。标准化的模拟框架不仅确保了实验的有效性，还便于与其他基准算法进行直接的性能比较。

对于我们的实验，我们定义了八种不同的场景：
(1) 5辆车带有50个订单，
(2) 5辆车带有100个订单，
(3) 20辆车带有300个订单，
(4) 20辆车带有500个订单，
(5) 50辆车带有1000个订单，
(6) 50辆车带有2000个订单，
(7) 100辆车带有3000个订单，
(8) 100辆车带有4000个订单。
这些场景旨在评估Evo-RL算法在不同需求和车队规模下的可扩展性和适应性。为了确保公平比较，所有实验都采用了华为ICAPS 2021比赛基线的标准配置参数：（1）在目标函数（4）中，Λ1=10000，Λ2=1（源自华为物流配送系统内的估计值）；（2）每个工厂最多有6个码头；（3）车辆的最大载重量Q限制为15；（4）每个实例的运行时间限制为10分钟。图4直观地展示了涉及4000个订单的单日订单分布情况。这一插图突出了我们的Evo-RL算法在大型物流运营中能够解决的复杂性和时空挑战。下载：下载高分辨率图片（767KB）下载：下载全尺寸图片

图4. 一天内共153个工厂的交付需求的空间时间分布。每天被划分为144个等时的时间间隔。网格越深，表示该时间的交付需求越强。

5.2. 结果与讨论
为了严格评估我们Evo-RL框架的性能，我们选择了一系列不同的比较方法来解决DPDP问题，包括：
- 独立的RL组件，对应于不包含进化（Evo）模块的我们提出的框架，使用的是循环PPO（RPPO）算法（Pu等人，2023年）。这种RL方法有效地利用了问题的时间结构来增强策略学习。
- 层次启发式方法（Hier）（Du等人，2023年）：目前针对同一问题的最优技术。我们复现了这种在三种订单 dispatch 规则（紧急、搭便车、打包）之间切换的层次优化方法，以及符合LIFO规则的基于块的局部搜索。
- 来自ICAPS 2021比赛的前三名开源获胜启发式算法，这些算法以在DPDP问题上的有效性而闻名：
- 变邻域搜索（VNS），一种通过改变邻域结构系统地探索解空间的鲁棒元启发式方法，允许从局部最优解中逃脱。这种方法在比较结果中标记为W1。
- 一种特定领域的启发式方法，结合了手动设计原则和行业洞察，提供了针对DPDP细微差别的精细调整的解决方案。这种方法在比较结果中标记为W2。
- 带有智能邻域的局部搜索方法，通过新颖的邻域设计增强了传统的局部搜索策略，以有效导航复杂的解空间。这种方法在比较结果中标记为W3。
- ADP（Jiang等人，2023年）：我们实现了一个ADP框架，该框架使用基于神经网络的值函数近似来处理我们DPDP问题中固有的大规模状态-动作空间。该方法利用与环境互动后获得的决策后状态和贝尔曼方程更新来优化长期奖励期望。为了与我们的Evo-RL方法进行公平比较，我们保持了与RPPO基线相同的网络架构，同时故意省略了进化优化阶段，以单独评估ADP的核心性能。
- 遗传算法（GA），配置为遵守迭代时间限制，反映了一种适应DPDP上下文的经典进化计算策略。
- 华为提供的基线解决方案，这是一种直接的、穷尽的搜索方法，用于量化更复杂方法的效率提升。此基线采用最初为静态PDP（Savelsbergh和Sol，1998年）设计的插入方法，通过每次事件重新优化来适应动态上下文。具体来说，每当有新订单发布时，所有未完成的取货和交货节点都会被整合到可用车辆的当前路线中，以产生一个可行的解决方案，有效地将每个动态事件视为一个新的静态子问题。

我们的评估旨在确立所提出的Evo-RL算法在处理动态取货和交货场景中的竞争优势和卓越性能。表2展示了六种算法在各种测试案例中获得的平均分数，反映了每种方法在最小化问题定义的成本函数方面的效率和效果。表3显示了平均超时持续时间，表明了算法满足动态环境施加的时间约束的能力。在表中，每种类型的最佳算法结果以粗体标记，第二好的结果则用下划线标出。在涉及5辆车和50个订单的情景中，所提出的Evo-RL方法比表现最好的启发式方法（Hierarchical）提高了11%。随着问题规模的增加，这种性能提升更加明显；例如，在有5辆车和100个订单的案例中，我们的方法比次优的启发式方法（W2）提高了32%。GA遇到了可扩展性限制，在较大案例中未能在时间限制内产生结果，标记为Timeout。相比之下，所提出的Evo-RL方法展示了出色的可扩展性，成功计算了所有测试场景的解决方案。值得注意的是，在处理50辆车和2000个订单的情况下，所提方法的得分比表现最好的启发式方法高了77%。在最大的评估场景中，即有100辆车和4000个订单的情况下，所提方法的得分提升了20%。与基线方法相比，所提出的框架在得分上提高了86.5%，表明了运营效率的显著提升。虽然启发式方法对于较小和不太复杂的案例是可行的，但它们在处理大规模问题的动态复杂性和不确定性时会表现出收益递减。另一方面，所提出的Evo-RL算法始终表现出显著的鲁棒性和可扩展性，特别是在要求更高和更复杂的实例中。这种显著的性能提升归因于Evo-RL框架内进化策略和强化学习的协同整合，使算法能够在动态运输环境的复杂性中 consistently 提供高质量的解决方案。此外，传统的RL方法的性能随着问题规模的增加而迅速下降。例如，在最大的场景中，即有100辆车和4000个订单的情况下，所提出的Evo-RL方法的性能比传统RL方法提高了99.6%。这种明显的差异突显了Evo-RL框架内进化组件的有效性，使其能够在大规模和变化多端的问题环境中灵巧地优化。

表2. 不同案例的平均分数。
| 案例 | 分数 | 方法 |
|--------|------------|-------------------------|
| Evo-RL（我们的）| | |
| Hier | | |
| W1 | | |
| W2 | | |
| RL(RPPO)（Pu等人，2023年）| | |
| ADP（Jiang等人，2023年）| | |
| GA（Wang等人，2022年）| | |
| 基线 | | |

表3. 不同案例的平均超时持续时间。
| 案例 | 方法 | |
|--------|-------------------------|
| Evo-RL（我们的）| | |
| Hier | | |
| W1 | | |
| W2 | | |
| RL(RPPO)（Pu等人，2023年）| | |
| ADP（Jiang等人，2023年）| | |
| GA（Wang等人，2022年）| | |
| 基线 | | |

图5中的箱形图提供了管理4000个订单和100辆车辆的具有挑战性场景下，超时持续时间和相应车辆行驶距离分布的比较可视化。箱形图表明，所提出的方法实现了显著更低的平均超时持续时间，并保持了更紧凑的分布，表明其性能的稳定性和高效的订单分配策略。值得注意的是，其两个指标的四分位数范围（IQR）明显窄于竞争方法，强调了其在面对运营变动时的鲁棒性。虽然RL方法和ADP方法在超时持续时间上显示出更宽的范围和更高的中位数，表明它们的订单分配方法不太一致且可能效率较低。它们的分布重叠进一步表明，在这项任务领域中RL和ADP之间的性能差异有限。同样，启发式方法（W1-W3）在车辆行驶距离和超时持续时间上也表现出不一致的性能，其中W2在行驶距离上显示出明显的异常值，这是高订单量下路由决策不稳定的迹象。所提方法实现的行驶距离缩短以及方差的减小进一步证实了其方法的有效性。

图6展示了不同规模案例下订单超时持续时间在不同时间间隔的分布。这些图中的颜色强度对应于超时持续时间的长度，颜色越深表示延迟时间越长。在小规模案例（图6a）中，涉及5辆车和100个订单，我们的方法显示的超时实例很少，仅限于三个不同的时间间隔。相比之下，其他方法观察到的超时频率和程度更高。值得注意的是，ADP算法的超时模式与PPO类似，在高峰时段（例如10:00-12:00）的强度略高，反映了它们在这些方面的共同局限性。在大规模案例（图6b）中，涉及100辆车和4000个订单，20:00之后超时显著增加。这种激增归因于大部分订单在15:00至17:00之间放置，如图4所示，以及这些订单随后集中在少数几个工厂中。诸如有限数量的码头和较长的装载时间之类的限制导致了等待时间的增加。两种基于学习的方法（RL和ADP）显示出几乎相同的超时累积趋势，ADP在22:00之后显示出轻微的延迟缓解，这可能是由于其在高维动作空间中的收敛速度较慢。此外，一旦订单开始，调整任务目标的灵活性不足可能会导致次优的分配，从而加剧积压并导致超时时间延长。我们提出的Evo-RL方法采用了一种更加战略性的方法，有效缓解了累积的超时，如图中较浅的颜色阴影和更早的完成时间所示。这些结果突出了我们方法的卓越适应性和性能，特别是在处理复杂的大规模物流场景时。为了进一步分析，我们检查了在24:00至25:00高峰期间100辆车和4000个订单的订单执行情况。

图7展示了24:00至25:00高峰期间各方法的订单执行情况，提供了每个工厂的地理位置（蓝点）、正在进行的订单状态（实线灰色）以及过期订单的超时持续时间（彩色线）的可视化。彩色线的颜色强度对应于过期订单的延迟长度。对于所提出的算法，尽管高峰期具有挑战性，但累积的订单超时持续时间相对较短。相比之下，其他启发式方法显示出未完成的订单持续时间较长，这通常是由于未能有效处理拆分订单和未能及时处理各个部分所致。这导致了订单完成的累积超时时间延长。这种比较可以归因于算法能够迅速处理之前未完成的订单，确保了更高效的订单执行流程。

图8展示了所提方法在各种场景下的性能。特别是，图8a显示了5辆车车队在处理不同数量订单时的繁忙状态，具体比较了处理50个、75个和100个订单的情景。该图展示了车辆活动水平、订单生成间隔以及在这些间隔内的订单数量之间的强相关性。这种关系表明，所提出的Evo-RL算法能够有效地管理车队运营，以满足不断增长的需求。此外，我们算法的有效性不仅体现在其处理增加的订单数量的能力上，还体现在其根据每辆车进行调度的能力上。图8b详细展示了在100个订单分配给五辆车的情景中，每辆车正在进行的订单数量。该图反映了订单随时间分配给各个车辆的动态分配情况，表明了算法在更高运营负载下的负载平衡和时间管理能力。

5.3. 收敛性分析
本节分析了基线RL算法和所提出的Evo-RL框架在不同车队规模环境下的收敛行为。为了公平起见，我们在所有方法上应用了相同的训练预算和超参数，仅在Evo-RL中加入了进化操作。图9总结了四种车队规模场景的结果，其中垂直轴显示目标函数分数（分数越低表示性能越好），水平轴显示训练剧集的数量。实线曲线表示五个独立随机种子的平均得分；阴影带表示通过对单种子训练日志进行局部重采样扰动得到的95%置信区间。下载：下载高分辨率图像（318KB）下载：下载全尺寸图像 图9. 在四种车辆密度场景下，RL基线和提出的Evo-RL方法的学习曲线。实线代表五个独立随机种子的平均性能；阴影带表示通过局部重采样扰动单种子日志估计的95%置信区间。为了量化收敛性，我们将收敛 episode 定义为平滑目标（例如，使用50个episode的移动平均窗口）首次进入并保持在最终稳定值±δ区间内的episode。根据这个标准，Evo-RL的收敛速度更快，且达到的目标值更低：•5辆车：Evo-RL大约在80个episode时收敛，而RL需要200个episode。•20辆车：Evo-RL大约在900个episode时收敛，而RL需要1600个episode。•50辆车：Evo-RL大约在2400个episode时收敛，而RL需要7000个episode。•100辆车：Evo-RL大约在10,000个episode时收敛，而RL需要18,000个episode。这些结果表明Evo-RL有两个关键优势：(i) 通过遗传算法（GA）操作符进行种群级探索和解决方案改进，加速了收敛速度；(ii) 收敛时的目标分数更低，反映了更好的渐进性能。进化组件扩大了策略搜索范围，减轻了仅使用RL训练时常见的过早收敛问题，而RL组件则利用了GA识别的高质量候选解，从而产生了更优的最终解决方案。5.4. 基于种群的优势：与VNS-RL的比较 本节评估了结合基于种群的进化组件来解决DPDP问题的可行性和优势。为此，我们引入了VNS-RL，这是提出的Evo-RL框架的一个简化版本，它省略了进化种群。相反，VNS-RL将变量邻域搜索（VNS）程序与RL结合，以加速收敛到可行解。在控制性的消融实验中，VNS替换了GA组件，同时保持了整体架构：RL负责订单分配，搜索模块根据RL生成的分配进行路线规划。VNS针对动态DPDP环境进行了调整，支持实时插入新订单并强制执行LIFO装载约束。与为静态实例或连续域设计的传统VNS变体不同，我们的实现使用了动态邻域结构和灵活的解决方案表示，能够在严格的LIFO合规性下快速更新路线（即，最后加载的包裹首先交付）。新订单到达时，VNS通过专门的邻域（如订单插入、路线段交换和车辆重新分配）逐步调整现有解决方案，而不是重新开始搜索，从而快速生成可行的更新。这些邻域明确验证并调整了取货-交货顺序，以保持基于堆栈的装载顺序。RL代理进一步根据所学策略指导邻域选择，将VNS探索集中在搜索空间的有希望的区域。这种定制的协同作用使VNS-RL能够适应动态问题状态，同时遵守DPDP约束。我们比较了Evo-RL和VNS-RL，以量化基于种群组件对整体性能和可扩展性的贡献。表4总结了在不同车队规模和订单量下的平均目标分数和总超时情况。在最小情况下（5辆车，50个订单），Evo-RL的目标分数比VNS-RL低85.9%，表明解决方案质量显著提高；总超时时间减少了84.1%，反映了更高的效率。随着复杂性的增加，性能差距扩大：当车辆数量为20辆、订单量为500个时，Evo-RL的目标分数低95.7%，超时时间减少了82.9%，显示出有效的扩展性。在最大情况下（100辆车，4000个订单），Evo-RL的目标分数低93.1%，总超时时间减少了96.9%。这些实证结果一致强调了基于种群探索和改进的优势：Evo-RL收敛更快，达到的目标值更高，尤其是在大规模、高不确定性的情况下。表4. 不同情况下的平均分数。情况得分时间车辆订单数量Evo-RLVNS-RLEvo-RLVNS-RL55012408766432271451008534592,2173065445,3792030011772166,533416010,253205001086152,554,12735981210,398501000986333,118,64835424302,01150200021554748,752,053775408,846,4211003000135542092,684,0124878726,583,7171004000176473425,642,17663527920,384,5845.5. 计算成本表5报告了每种方法在测试期间每个决策周期（10分钟时间片）所需的平均墙钟时间。所有实验都在配备Intel Xeon Gold 5416S处理器、128GB RAM和24GB内存的NVIDIA A5000 GPU的工作站上进行。经典元启发式（GA、W1-W3）和基于模型的分层启发式呈超线性扩展：当订单数量从100增加到4000时，它们的运行时间增加了两到三个数量级。这种行为与理论预期一致，即随着问题规模的增加，局部改进和邻域探索例程访问的LIFO可行序列的数量呈指数级增长（Du等人，2023年）。基于RL的代理（RL、ADP、VNSRL和提出的Evo-RL）几乎表现出线性扩展：推理只是通过网络进行一次前向传递，然后是常数时间的动作选择步骤。因此，即使在最大的100个订单实例中，我们的Evo-RL策略平均也在2.5秒内决定车辆-订单分配，这比最好的竞争启发式（W2: 54秒）快两个数量级，比分层方法（268秒）快三个数量级。表5. 不同情况下不同方法的测试时间。订单 第二种方法Evo-RL（我们的）HierW1W2W3RLVNSRLADPGABaseline1001.64.217428781.71.62.35221045001.88.7208331411.81.92.673815220002.235231372063.12.74.6185121640002.5268412543843.83.54.72043295此外，由于Evo-RL产生了更高质量的决策，任何步骤未完成订单的累积数量较少；因此，每个决策周期必须处理的平均请求数量减少，进一步缩短了表中报告的墙钟时间。Evo-RL中嵌入的进化包装器仅增加了可以忽略不计的开销，与独立的RL基线相比，确认了遗传搜索是在训练期间离线执行的，不会影响实时操作。上述观察结果证实了提出的Evo-RL框架的关键优势：它继承了神经策略的亚秒级推理速度，同时仍然享受了进化增强训练带来的高质量解决方案。因此，在新订单每隔几秒到达的時間敏感的物流平台中，Evo-RL提供了一个可扩展且可部署的替代方案，传统启发式的延迟很快就会违反调度截止时间。6. 结论 我们提出了Evo-RL，这是一个旨在解决在严格LIFO约束下DPDP问题的高维和动态特性的协作框架。通过结合基于种群的GA和深度RL，我们建立了一个闭环系统，其中GA不仅作为局部优化器，还作为密集反馈信号的生成器。这种协同作用有效地缓解了动态物流环境中常见的奖励稀疏性问题，使RL代理能够学习出稳健的策略，尽管存在侧装载约束的复杂性。我们在ICAPS 2021基准测试上的实验结果表明，这种混合方法在收敛速度和解决方案质量方面显著优于单独的启发式和深度RL基线。更重要的是，将随机不确定性模型纳入内在奖励机制使代理能够预测潜在的延误，从而产生对现实世界变化具有抵抗力的路线计划。从更广泛的角度来看，这项工作表明，对于受刚性物理协议（如侧装载车辆）约束的组合问题，基于种群的RL相对于单轨迹搜索方法具有明显优势。通过将战略规划（由RL处理）与序列优化（由GA处理）分离，该框架避免了传统解决方案陷入的局部最优解。未来的研究将把这种方法扩展到异构车队和多目标优化，特别是旨在平衡大规模供应链中的运营效率和碳排放减少。未来的研究将探索将这种协作架构推广到其他受约束的组合问题，例如具有非线性充电功能的电动车辆路线问题。CRediT作者贡献声明杨晓英：撰写——原始草稿、可视化、验证、调查、形式分析、数据管理。李一然：撰写——原始草稿、可视化、验证、调查、形式分析。崔天祥：撰写——审阅与编辑、撰写——原始草稿、监督、资源管理、项目管理、方法论、资金获取、形式分析、概念化。 Bai瑞斌：撰写——审阅与编辑、监督、资金获取。