一种用于具有随机需求的时间依赖型车辆路径问题的两阶段随机规划方法：动态时空网络视角

《TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW》：A two-stage stochastic programming approach for the time-dependent vehicle routing problem with stochastic demands: a dynamic space–time network perspective

　　摘要：城市配送作业日益面临随机客户需求与时间依赖型交通状况带来的双重不确定性，这对传统车辆路径规划模型的适用性提出了挑战。本研究通过构建与现实道路拓扑结构相对应的动态时空网络，解决了具有服务时间窗的随机需求时间依赖型车辆路径问题。研究人员设计了两阶段随机规划模型，结合预防性与反应性策略来应对需求不确定情况下的容量不足问题，同时充分考虑了路径规划及往返调度过程中的时间依赖型行驶时间、服务时间窗、车辆等待时间和服务时长等因素。为求解该问题，研究者采用了改进的整数L形方法，将预期需求下的路径规划与特定场景下的调度策略分开处理，并将本德斯割直接嵌入分支定界法中，在分支过程中动态生成割集。在基准测试案例以及京东的实际应用案例中的计算实验表明，所提出的方法能够生成具备适应性且成本效益较高的路径，最优解与实际最优解的差距平均仅为2.98%，相比商业求解器及传统分解技术，不仅运行时间减少了39.0%-88.9%，最优解差距也缩小了34.1%-84.8%。此外，研究还对问题规模、需求分布、交通状况恶化程度以及服务时间窗等因素进行了敏感性分析，为管理者提供了有益的参考。这项工作首次尝试将时空建模、随机需求、混合时空调度策略以及精确分解方法结合用于解决随机需求时间依赖型车辆路径问题，为在不确定性环境下实现城市物流的稳健且可扩展的解决方案提供了框架。

引言：随着电子商务的兴起，城市配送已成为现代物流体系的核心组成部分，直接影响着服务质量和运营效率。运输成本在物流总成本中占比超过一半（Sun等人，2015），这凸显了有效路径优化的重要性。然而，现实世界中的各种不确定性以及不断变化的交通状况，如难以预测的客户需求和高峰时段的交通拥堵，极大地限制了传统确定性模型的应用效果。这些挑战促使人们开发出了诸如随机车辆路径问题（SVRP）（Bastian和Rinnooy Kan，1992）以及时间依赖型车辆路径问题（TDVRP）（Malandraki和Daskin，1992）等专门模型。SVRP主要用于处理客户需求、服务时间或行驶时间等要素的不确定性。而随机需求车辆路径问题（VRPSD）则是其重要变体，重点研究在需求量不确定条件下的路径规划问题（Stewart和Golden，1983）。需求的波动可能导致客户数量超出车辆承载能力，进而引发配送失败、路径调整以及额外的运营成本。规划者必须预判由此产生的连锁反应，并采取相应策略来管理车辆容量和服务时间窗，这进一步增加了问题的计算复杂性。与此同时，城市环境中的行驶时间本身具有时间依赖性，会因交通拥堵、天气状况以及其他动态因素而随出发时间发生变化。因此，同一路段在不同时间段的行驶时长可能存在显著差异（Castellucci等人，2025）。这种时间变化性再加上随机客户需求，使得路径规划决策及调度策略的制定更加复杂。以往的研究提出了多种应对VRPSD中需求不确定性的调度机制。早期研究采用纯粹的反应性策略，即只有当车辆容量耗尽后才会返回仓库（Gendreau等人，1995）。后续研究则提出了预防性策略，通过主动调整路径来降低容量风险（Louveaux和Salazar-González，2018），此后又出现了旨在平衡稳健性与灵活性的混合策略。近期的研究还纳入了更多现实因素，如客户的服务时间窗（Zhang等人，2023）、车辆的等待时间和服务时长（Reusken等人，2024），以及取货和送货要求（Ojeda Rios和Xavier，2025）。不过，现有模型往往忽视了时间依赖型行驶时间、时空补给决策以及底层交通网络拓扑结构。如果不考虑车辆返回仓库对后续配送的影响，那么在交通拥堵的城市环境中就可能出现次优的配送结果，还会影响路径规划的可行性（Liu等人，2020）。尽管有一些研究考虑了随机或相关的行驶条件（Rostami等人，2021），但很少有研究能将随机需求、动态变化的交通状况、客户服务时间窗以及时空调度策略整合到一个统一的优化框架中。本研究正是为填补这一空白而展开的，它研究了具有随机需求的时间依赖型车辆路径问题（TD-VRPSD），该问题综合考虑了上述各类因素，并且是在底层道路网络拓扑结构的基础上进行定义的。此外，由于VRPSD属于NP难问题，大量研究依赖于启发式或元启发式方法，而能够处理这些相互关联因素的精确分解方法仍然较为有限。这些限制很大程度上源于传统的空间网络建模方式。为了体现现实世界的运营情况，传统建模方法通常需要大量的辅助变量和资源扩展函数（Zhao等人，2025），这就导致了高度耦合的结构，从而阻碍了高效精确优化，尤其是在随机环境下。在TD-VRPSD问题中，这类建模方法必须明确考虑客户服务、流量守恒、消除子回路、服务时间窗、路径长度、车辆容量、车队规模以及与调度相关的约束条件。相比之下，时空网络将时间维度直接融入网络结构中，从而将与时间相关的约束内化，便于问题的分解（Mahmoudi和Zhou，2016）。其单向的时间发展特性可以自然避免子回路的出现，同时也允许车辆多次访问同一个节点，这对于体现随机需求下因补给需要而进行的重复访问非常有用。虽然这种表示方式会增加时空节点和边的数量，但它能更清晰、更准确地模拟基于底层交通拓扑结构的 time依赖型路径规划及调度决策，这也是人们倾向于使用基于分解的求解方法的原因。在VRPSD的求解方法方面，由于其在大规模问题上的有效性，大多数研究都采用启发式和元启发式方法，包括基于种群规模的算法（如Wang等人，2023）、基于轨迹的搜索算法（如Ma等人，2023）以及基于学习的算法（如Zhou等人，2023）。而那些利用问题结构特征的精确算法则相对发展较少。现有的研究主要集中在基于分解的框架上，比如用于列生成型问题的分支定价法（如Florio等人，2021）以及用于两阶段随机模型的本德斯分解法。值得注意的是，L形方法及其整数扩展形式（如Laporte和Louveaux，1993）为解决随机路径规划问题奠定了基础，但它们在更复杂的场景中的应用仍然有限，尤其是那些涉及时间依赖动态和时空网络表示的场景。最近的进展，如分支-本德斯-割方法（如Hooker，2019），试图通过在分支定界过程中集成割集生成来提高效率，但其在VRPSD问题中的应用仍然较少。因此，本文在时空网络背景下，为TD-VRPSD问题开发了一种基于结构特征的精确本德斯分解算法，并将其纳入分支定界框架中，从而实现了对该两阶段随机模型的高效求解。迄今为止，大多数关于VRPSD的研究都无法充分体现现实交通系统的高维特性，尤其是由交通拥堵导致的时间依赖型行驶时间，以及在城市物流中至关重要的底层拓扑结构。此外，客户服务时间窗、车辆服务时间（即为服务一名客户所需的时间）以及车辆等待时间（因服务时间窗限制或交通状况变化而处于闲置状态的时间）等实际因素往往被忽视，而且现有的调度策略在灵活性方面也存在不足。与此同时，基于时空网络的结构建模方法以及以分解为导向的精确算法也鲜有研究关注。正是出于对这些不足的考虑，我们开发了一种基于时空网络的建模框架，用于解决具有随机需求的时间依赖型车辆路径问题（TD-VRPSD），该框架能够清晰地体现随机需求变化与基于底层交通拓扑结构的时空补给行为之间的相互作用。我们将该问题表述为一个两阶段随机规划问题，即在需求确定后，通过基于不同场景的调度策略来调整第一阶段的路径规划方案。该模型涵盖了诸多关键运营要素，包括时间依赖型行驶时间、服务时间窗、混合调度策略、驾驶员等待时间、车辆容量和路径长度约束，以及补给行程所带来的后续影响。为了解决该模型，我们设计了一种改进的整数L形算法，并将其嵌入分支定界框架中，由于主问题只需求解一次，因此无需反复迭代。本研究的主要贡献如下：（1）模型构建：我们提出了一种基于场景的两阶段整数线性规划模型，用于解决具有随机需求的时间依赖型车辆路径问题（TD-VRPSD），该模型建立在基于真实交通网络生成的时空网络之上。该模型整合了时间依赖型行驶时间、服务时间窗、混合（反应性和预防性）时空调度策略、车辆等待时间和服务时长等信息，而且车辆调度也需考虑时间依赖型行驶时间的影响。据我们所知，这是首次将时空网络框架应用于TD-VRPSD问题。（2）算法开发：我们设计了一种改进的整数L形分解方法，将该模型划分为第一阶段路径规划主问题和第二阶段调度子问题。通过将本德斯割嵌入主问题の分支定界树中，该算法不仅加快了收敛速度，还显著提升了计算效率。（3）实验验证：我们通过在基准测试案例（8节点城市道路网络、24节点苏福尔斯城际网络）以及京东的实际应用案例中开展实验，评估了所提框架的可行性和性能。实验结果表明，无论是在解决方案的质量还是计算效率方面，我们的方法都优于商业求解器Gurobi以及传统的本德斯分解方法。此外，我们还针对问题规模、需求不确定性、交通状况恶化程度以及服务时间窗等因素进行了敏感性分析，为管理者提供了更多有价值的参考信息。本文的其余部分结构如下：第2节回顾相关文献；第3节阐述问题定义、构建时空网络，并给出基于边的混合整数线性规划模型；第4节介绍改进的整数L形分解方法；第5节展示计算结果及敏感性分析结果；第6节总结全文并指出未来研究方向。