动态拣货和配送问题（DPDP）是物流领域的一个基本问题，是NP难问题。目标是在多个站点之间动态调度车辆，以服务在线生成的订单，从而使总体运输成本最小化。DPDP的关键挑战是订单先验未知，即订单是实时动态生成的。为了解决这个问题，现有的方法通过缓存在线生成的订单并解决每个子问题，或者在此基础上利用预测的未来订单进一步优化每个子问题来将整个DPDP划分为固定大小的子问题。然而，这些方法的求解质量和效率都不令人满意，尤其是当问题规模非常大时。在本文中，我们提出了一种新的分层优化框架，以更好地解决大规模DPDP。具体而言，我们设计了一个上层代理，将DPDP动态地划分为一系列具有不同规模的子问题，以优化车辆路线，从而实现全球更好的解决方案。此外，通过将经典的基于运筹学的方法的优点与基于强化学习的策略相结合，设计了一个较低级别的代理来有效地解决每个子问题。为了验证拟议框架的有效性，从华为供应链业务部的订单调度系统收集真实历史数据，并用于构建功能模拟器。在工业订单调度系统上进行的大量离线模拟和在线测试证明了我们的框架优于现有基线。
动态提货和交货问题（DPDP）是一个重要的路由问题家族，通常包含三个关键要素：订单、货物和车辆，如图1所示。订单是实时生成的。不同的订单包含不同类型和数量的货物。许多车辆计划通过将所需货物从不同来源运输到不同目的地来满足订单。DPDP的目标是动态地将每个订单分配给最合适的车辆，以使总运输成本（例如总距离）最小化。DPDP广泛应用于供应链、快递服务和其他地方的订单调度系统。DPDP是旅行推销员问题（TSP）和车辆路径问题（VRP）的复杂变体，这两个问题都是NP难组合优化问题[25]。DPDP的主要困难来自于实时动态生成的订单，因此无法以离线方式预先做出订单调度决策。此外，与TSP和VRP相比，DPDP中还存在各种附加的复杂约束，如提货和交货约束、后进先出（LIFO）约束、时间窗口约束、分割需求约束等。DPDP的现有解决方案分为两类。第一类维护一个固定的缓冲区来缓存最近生成的订单，并以延迟模式定期调度所有缓存的订单。通过这种方式，整个动态问题被划分为一系列具有已知订单子集的静态子问题，即静态提货和交货问题（PDP）。然后，设计基于运筹学（OR）的方法[22，20]、启发式和元启发式方法[7，16，25，4，5，3，11，26，23，9]来解决每个子问题。然而，短视地优化每个静态子问题并不能保证从长期角度优化整个动态问题，因为分裂的子问题不是彼此独立的。主要原因是先前的订单分配结果将影响（1）要发送的剩余订单数量，（2）车辆的剩余容量，以及（3）与后续订单的相对位置。为了获得更好的解决方案，第二类方法[24，8，12]试图预测未来订单的分布，并在计算每个子问题的解决方案时考虑预测订单。然而，由于现实世界的高度不确定性，预测未来订单并不现实。不准确的预测将误导订单调度员和路线规划员，并导致解决方案质量不佳。基于学习的VRP方法。此外，传统OR和元启发式方法的一个常见缺陷是，它们的计算成本很高，通常无法在允许的时间内获得所需的解决方案。此外，它们的设计严重依赖于复杂的领域知识。为了提高解的计算效率并减轻算法设计的难度，最近提出了几种基于学习的方法[27，1，18，6，13]。这些方法证明，通过利用训练模型的泛化能力，可以显著提高解的计算效率。此外，与最先进的传统方法相比，他们可以获得具有竞争力的解决方案。尽管这些方法主要关注TSP或VRP，其中所有订单的信息都是预先知道的，与DPDP相比，考虑的约束要少得多，但基于学习的方法已显示出极大的潜力，有助于解决大规模DPDP并实现优异的性能。在本文中，我们提出了一种新的基于分层强化学习（RL）的优化框架来解决现实世界中的大规模DPDP。考虑到订单调度对总体优化目标具有长期影响，上层RL代理动态确定是否在每个时刻等待更长时间以缓存更多未来订单。通过这种方式，可以更灵活地将订单分配给车辆（因为每辆车将有更多的候选订单可供选择），并且可以优化车辆路线，以实现全球更好的解决方案。较低级别的RL代理负责通过顺序操纵启发式算子来将缓存的订单分配给最合适的车辆，以迭代地提高解决方案质量。为了验证框架的有效性，我们从华为供应链的订单调度系统中收集了真实的历史数据，并构建了一个模拟器来模拟订单调度和车辆运输过程。此外，我们在公司的供应链业务部门部署了我们的方法。广泛的离线模拟和在线测试表明了我们算法的优越性能。我们的主要贡献如下：
- We are the first to propose a practical hierarchical RL framework to efficiently and farsightedly compute superior solutions for the real-world large-scale DPDPs with complex constraints. •
- We design a simulator using real industrial data to be the experimental benchmark to verify the proposed method, which is available here for interested researchers. •
- We show that our approach considerably improves the optimization objectives compared with existing algorithms both in the offline evaluation and online testing. The ablation study indicates our approach can obtain high-quality solutions with fast running speed and has strong generalization ability
