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

Technical Summary: A Two-Stage Stochastic Optimization Model for Synchronized Two-Echelon Routing Problems

Problem Definition
This study addresses the complexity of uncertainty within city logistics, specifically focusing on Integrated Water- and Land-based Transportation (IWLT) systems. The core problem is the Two-echelon Multi-trip Vehicle Routing Problem with Satellite Synchronization (2E-MVRP-SS). In this system, Light Electric Freight Vehicles (LEFVs) operate on the first echelon (streets) to collect goods from customers and transfer them to vessels (second echelon) at satellite nodes. The system operates without storage options at satellites, requiring strict spatiotemporal synchronization between LEFVs and vessels.

The primary challenge addressed is the propagation of delays caused by uncertain transshipment lead times at satellites. These uncertainties, stemming from regional factors like traffic congestion or operational variations, can disrupt synchronized operations, leading to customer lateness, increased operational costs, and reduced reliability. The study specifically targets reverse logistics scenarios (e.g., waste collection, returns) where timely service is critical to minimize inventory costs and customer inconvenience.

Methodology
The authors propose a two-stage stochastic optimization framework with a mixed-integer recourse problem to manage these uncertainties.

1. Two-Stage Formulation:

   • First Stage (Master Problem): Decisions are made regarding LEFV routes and the assignment of transfer tasks to satellites before the realization of delays. This stage prioritizes reliable service times for pickups. The model assumes LEFVs visit the closest satellite as an initial approximation.
   • Second Stage (Recourse/Subproblem): Once specific delay scenarios are realized, corrective actions are taken. This involves re-allocating transshipment operations to different satellites and re-routing vessels to mitigate the impact of delays. LEFV schedules for customer service remain fixed to honor promised times, but the water-level logistics are re-optimized.

2. Algorithmic Approach:

   • To handle the non-convexity of the second-stage cost function and the mixed-integer nature of the problem, the authors employ an L-shaped method adapted with combinatorial Benders cuts.
   • The algorithm iterates between a relaxed master problem and subproblems for each scenario.
   • Feasibility cuts ensure that first-stage decisions allow for feasible second-stage solutions.
   • Optimality cuts approximate the expected second-stage cost.
   • A scenario-based sampling approach is used to represent regional uncertainties. Delays at satellites are modeled as normally distributed variables, discretized into a finite set of scenarios ($N$) to ensure computational tractability while maintaining stability.

3. Experimental Setup:

   • The model was tested on small network instances (10 pickup nodes, 4 satellites) derived from modified Solomon VRPTW instances.
   • Two system designs were compared: 2E-Flexible (vessels act as mobile depots, synchronized with LEFVs) and 2E-Stationary (fixed vessel locations).
   • Performance was evaluated against a deterministic (no-delay) baseline and a two-stage stochastic approach.

Key Contributions

• Novel Modeling of Synchronization: This is the first study to address the impacts of satellite delays on vehicle synchronization in a two-echelon system with no storage capacity, a scenario requiring high spatiotemporal coordination.
• Stochastic Recourse Framework: The paper proposes a two-stage stochastic programming model with mixed-integer recourse specifically for 2E-MVRP-SS. It utilizes combinatorial Benders cuts within an enumeration method to handle the non-convexity of the second stage.
• Comparative Analysis of Flexibility: The study provides a quantitative comparison between flexible transport systems (mobile vessels) and stationary systems under uncertainty, demonstrating the value of flexibility in mitigating delay propagation.

Results

• Cost Reduction: The proposed stochastic programming model reduced the expected total costs by 37% across all instances compared to a deterministic approach that assumes no delays.
• Scenario Stability: The scenario generation approach demonstrated stability; the variance of scenarios within the sample decreased as the number of scenarios increased, stabilizing around 30 scenarios.
• Impact of Network Topology:
  • For Clustered (C) demand networks, the integrated system maintained efficiency with minimal cost increase (near 0%) under uncertainty.
  • For Random (R) networks, the stochastic approach achieved the most significant savings compared to deterministic strategies, reducing expected costs by up to 43% in specific instances by better locating delay-sensitive pickup locations.
• System Performance (Flexible vs. Stationary):
  • The 2E-Flexible system significantly outperformed the 2E-Stationary system in terms of reliability and modal share.
  • Under uncertainty, the stationary system experienced a sharp increase in street travel times and lateness (e.g., lateness increased to 26 time units in RC instances), whereas the flexible system kept lateness low (9 time units) and maintained a more balanced modal share between road and water transport.
  • The flexible system effectively mitigated the risk of increased street travel costs, demonstrating that relocating storage units (or in this case, transshipment points) cannot match the performance of flexible sailing services in terms of congestion and reliability.

Significance and Claims
The paper claims that incorporating uncertainty into offline planning is essential for the reliability and cost-effectiveness of multimodal city logistics, particularly in contexts where urban space competition limits storage options. The study demonstrates that flexible systems, where vessels act as mobile depots synchronized with LEFVs, offer superior resilience against transshipment delays compared to fixed-location systems.

The authors conclude that while the proposed model is computationally intensive, the gains observed in small instances suggest that stochastic optimization can significantly improve service reliability and reduce the "green" modal share (road usage) in city logistics. They note that future work could utilize the proposed enumeration and pricing framework to develop heuristics for large-scale problems, but the current study focuses on validating the theoretical framework and the benefits of flexibility on small, solvable networks.