Stochastic Vehicle Routing

In this variant, each customer requires service with a known probability, not certainty. The vehicle must plan a route before knowing which customers will actually need a visit that day.

• Mechanism: Modeled as a two-stage stochastic program with recourse. A planned a priori route is designed, and when a customer is revealed as absent, the vehicle simply skips that stop.
• Key Challenge: Balancing travel cost efficiency against the probability of serving many scattered customers.
• Application: Home appliance repair services where the technician only knows the probability of a breakdown call, not the exact set of daily jobs.

Customer demand quantities are treated as random variables with known probability distributions. The vehicle's actual load is only discovered upon arrival at each customer location.

• Route Failure: Occurs when the cumulative demand on a route exceeds the vehicle's remaining capacity, forcing a recourse action such as returning to the depot to restock.
• Solution Approach: A priori routes are designed to minimize the expected total cost, including the cost of potential route failures. This is often solved using stochastic programming with recourse or robust optimization.
• Example: A fuel delivery truck servicing gas stations where the exact gallons needed at each stop are unknown until the tank is measured on-site.

Travel times between locations are modeled as time-dependent random variables rather than fixed constants, capturing the inherent variability of real-world traffic and road conditions.

• Constraint Handling: Soft time windows are typically used, where late arrivals incur a penalty cost rather than being infeasible. The objective becomes minimizing expected total cost, including lateness penalties.
• Modeling: Often uses time-dependent probability distributions (e.g., log-normal for travel times) or scenario-based representations of traffic states.
• Critical Distinction: Unlike Time-Dependent VRP where travel times are deterministic functions of time, SVRPSTT treats them as genuinely random, requiring probabilistic constraint satisfaction.

The duration of service at each customer location is a random variable, introducing uncertainty into the route schedule and downstream arrival times.

• Propagation Effect: A long service time at one stop delays all subsequent stops, creating a cascading uncertainty that compounds along the route.
• Modeling Techniques: Service times are often modeled with phase-type distributions or gamma distributions to capture the positive-skewed nature of task durations.
• Industry Context: Critical in healthcare logistics where the duration of a nurse's home visit varies significantly by patient condition, or in field service where repair complexity is unknown before diagnosis.

A compound uncertainty variant where both travel times and service times are random, representing the most realistic but computationally demanding SVRP formulation.

• Joint Distribution: The two sources of uncertainty may be correlated (e.g., bad weather simultaneously increases travel times and slows outdoor service tasks).
• Solution Methods: Typically requires sample average approximation (SAA) or simulation-based optimization because analytical expected cost functions become intractable.
• Recourse Strategy: Optimal policies often involve dynamic re-optimization, where the remaining route is recomputed in real-time as actual travel and service times are realized, aligning with Model Predictive Control frameworks.

Instead of minimizing expected cost, this formulation enforces probabilistic constraints that guarantee a certain service level with a specified probability.

• Constraint Form: A typical constraint states that the probability of violating a time window or capacity limit must be below a threshold α (e.g., 5%).
• Deterministic Equivalent: Under specific distributional assumptions (e.g., normal travel times), chance constraints can be reformulated as deterministic linear constraints, enabling solution by standard MILP solvers.
• Use Case: Premium logistics contracts with strict Service Level Agreements (SLAs) where a 95% on-time delivery guarantee is contractually mandated, making expected value optimization insufficient.

The primary mathematical framework for SVR. Decisions are split into first-stage actions (planned routes dispatched before uncertainty is revealed) and second-stage recourse actions (corrective measures like returning to the depot or deploying a backup vehicle) taken after random variables like demand or travel time are realized. The objective is to minimize the sum of first-stage costs plus the expected cost of recourse.

An alternative SVR formulation where constraints are expressed probabilistically. Instead of modeling explicit recourse actions, a chance constraint ensures that a condition—such as meeting a delivery time window or not exceeding vehicle capacity—holds with at least a specified probability (e.g., 95%). This is particularly useful when the cost of failure is non-linear or catastrophic, and a safety buffer is preferred over a reactive fix.

A non-probabilistic approach to SVR that seeks solutions immunized against the worst-case realization of uncertain parameters within a defined uncertainty set. Unlike stochastic programming, it does not require a probability distribution. A robust VRP solution guarantees feasibility for any travel time or demand scenario within a bounded range, making it ideal for risk-averse logistics where a single failure is unacceptable.

The formal framework for dynamic SVR, where decisions are made sequentially as new information arrives. An MDP defines:

• State: Current vehicle locations, remaining demands, and realized random variables.
• Action: Which customer to visit next.
• Transition Probability: The likelihood of moving to a new state given an action.
• Reward: Negative cost incurred. Solving the MDP yields an optimal policy that maps any state to the best action.

A Monte Carlo simulation-based method for solving two-stage stochastic programs. Instead of evaluating the expected recourse cost over a continuous distribution, SAA generates a finite set of N scenarios by sampling from the probability distributions of random variables. The stochastic problem is then approximated as a large, deterministic Mixed-Integer Linear Program (MILP) and solved with solvers like Gurobi. Accuracy improves as N increases.

A dominant metaheuristic for large-scale SVR instances where exact methods are computationally intractable. ALNS iteratively destroys a portion of the current solution (e.g., removing random customers) and repairs it using a fast heuristic. An adaptive layer tracks the performance of each destroy/repair operator pair and dynamically selects the most effective ones. It is highly effective for dynamic and stochastic variants with many scenarios.