A two-stage stochastic optimization model for synchronized two-echelon routing problems

技术摘要：用于同步两阶段两级路径规划问题的两阶段随机优化模型

问题定义
本研究探讨了城市物流中的不确定性复杂性，特别关注集成水陆运输（IWLT）系统。核心问题是带卫星同步的两阶段多路径车辆路径问题（2E-MVRP-SS）。在该系统中，轻型电动货运车（LEFV）在第一阶段（街道）运行，负责从客户处收集货物并将其转移至卫星节点（第二阶段）的船舶上。该系统在卫星处不具备存储选项，因此要求 LEFV 与船舶之间实现严格的时空同步。

研究解决的主要挑战是由于卫星处转运前置时间（lead times）的不确定性所导致的延迟传播。这些不确定性源于区域性因素（如交通拥堵或运营波动），可能破坏同步操作，导致客户延迟、运营成本增加以及可靠性降低。本研究专门针对逆向物流场景（例如废物收集、退货），在这些场景中，及时的服务对于最小化库存成本和客户不便至关重要。

方法论
作者提出了一个带有混合整数补救问题的两阶段随机优化框架，以管理这些不确定性。

1. 两阶段建模：

   • 第一阶段（主问题）： 在延迟实现之前，做出关于 LEFV 路径以及向卫星分配转运任务的决策。此阶段优先考虑取货服务的可靠服务时间。模型假设 LEFV 初始近似访问最近的卫星。
   • 第二阶段（补救/子问题）： 一旦特定的延迟情景被实现，则采取纠正措施。这包括将转运操作重新分配到不同的卫星，并重新规划船舶路径以减轻延迟影响。为履行承诺时间，LEFV 的客户服务计划保持固定，但水路物流环节将被重新优化。

2. 算法方法：

   • 为了处理第二阶段成本函数的非凸性和问题的混合整数性质，作者采用了结合**组合 Benders 切割（combinatorial Benders cuts）**的 L-shaped 方法。
   • 算法在松弛主问题与针对每个情景的子问题之间进行迭代。
   • **可行性切割（Feasibility cuts）**确保第一阶段的决策能够允许第二阶段的可行解。
   • **最优性切割（Optimality cuts）**用于近似期望的第二阶段成本。
   • 采用基于情景的采样方法来表示区域不确定性。卫星处的延迟被建模为正态分布变量，并离散化为有限的情景集（$N$），以在保持稳定性的同时确保计算的可处理性。

3. 实验设置：

   • 模型在由修改后的 Solomon VRPTW 实例衍生的规模较小的网络实例（10 个取货节点，4 个卫星）上进行了测试。
   • 对比了两种系统设计：2E-Flexible（船舶作为移动仓库，与 LEFV 同步）和 2E-Stationary（固定船舶位置）。
   • 性能评估基于确定性（无延迟）基准和两阶段随机优化方法。

核心贡献

• 创新的同步建模： 这是首个研究在无存储容量的两阶段系统中，探讨卫星延迟对车辆同步影响的研究，该场景对时空协调要求极高。
• 随机补救框架： 本文为 2E-MVRP-SS 提出了一个带有混合整数补救的两阶段随机规划模型。它利用枚举法中的组合 Benders 切割来处理第二阶段的非凸性。
• 灵活性的比较分析： 研究通过定量比较了不确定性下的灵活运输系统（移动船舶）与固定系统，证明了灵活性在缓解延迟传播方面的价值。

结果

• 成本降低： 与假设无延迟的确定性方法相比，所提出的随机规划模型在所有实例中降低了 37% 的期望总成本。
• 情景稳定性： 情景生成方法展示了稳定性；随着情景数量的增加，样本内的情景方差逐渐减小，并在 30 个情景左右趋于稳定。
• 网络拓扑的影响：
  • 对于**聚类型（C）**需求网络，集成系统在不确定性下仍能保持高效，成本增加极小（接近 0%）。
  • 对于**随机型（R）**网络，随机优化方法相比确定性策略实现了最显著的节省，通过更好地定位对延迟敏感的取货位置，在特定实例中将期望成本降低了高达 43%。
• 系统性能（灵活型 vs. 固定型）：
  • 2E-Flexible 系统在可靠性和模态份额（modal share）方面显著优于 2E-Stationary 系统。
  • 在不确定性下，固定系统经历了街道行驶时间增加和延迟加剧（例如，RC 实例中的延迟增加到 26 个时间单位），而灵活系统则保持了较低的延迟（9 个时间单位），并维持了更平衡的公路与水路运输模态份额。
  • 灵活系统有效地缓解了街道运输成本增加的风险，表明重新定位存储单元（或在此案例中为转运点）无法在应对拥堵和可靠性方面达到灵活航行服务（flexible sailing services）的表现。

意义与主张
本文主张，将不确定性纳入离线规划对于多式联运城市物流的可靠性和成本效益至关重要，特别是在城市空间竞争限制了存储选项的背景下。研究表明，灵活系统（即船舶作为与 LEFV 同步的移动仓库）相比于固定位置系统，在应对转运延迟方面具有更强的韧性。

作者得出结论，虽然所提模型计算量较大，但观察到的小规模实例中的收益表明，随机优化可以显著提高服务可靠性，并减少城市物流中“绿色”模态（道路使用）的比例。他们指出，未来的工作可以利用所提出的枚举与定价框架来开发大规模问题的启发式算法，但目前的研究重点在于验证理论框架以及灵活性对小规模可解网络的益处。