Routing Under Uncertainty and Real-Time Disruption

Introduction

A route plan is normally constructed from forecasts: expected customer demand, nominal travel times, known vehicle capacities, and an assumed road network. In practice, each of these inputs can change after dispatch. Orders may be cancelled or added, congestion may increase travel time, storms may close roads, and a vehicle may become unavailable. Consequently, route planning is not only a problem of finding efficient routes; it is also a problem of making decisions that remain effective when information is incomplete and conditions evolve.

Uncertainty and disruption have different meanings. Uncertainty refers to variability or imperfect knowledge before a decision is made, such as uncertain demand or probabilistic travel time. A disruption is an realized event that materially changes the operating environment, such as a road closure or vehicle breakdown. A robust supply chain anticipates uncertainty, absorbs moderate deviations, and adapts rapidly when disruptions occur.

This chapter examines stochastic, robust, dynamic, and rolling-horizon approaches to routing. It also considers scenario analysis, real-time re-routing, implementation architecture, performance measurement, and governance. The central managerial challenge is to balance efficiency against resilience: a route that is optimal under one forecast may be inferior when flexibility and service reliability are valued.

Learning Objectives

By the end of this chapter, the reader should be able to:

1. Distinguish deterministic, stochastic, robust, dynamic, and rolling-horizon routing.
2. Formulate uncertain-demand and uncertain-travel-time models.
3. Compare expected-cost, risk-averse, and worst-case decision criteria.
4. Use scenario analysis to evaluate routes before execution.
5. Design a real-time re-routing process that respects operational stability.
6. Evaluate disruption responses using service, cost, resilience, and equity measures.
7. Identify technological, ethical, regulatory, and managerial limitations of automated routing.

1. Sources and Structure of Routing Uncertainty

1.1 Demand uncertainty

Customer demand may be uncertain in quantity, location, timing, or product composition. A retailer may know that a region will generate approximately 500 orders but not which households will order. A business-to-business customer may reduce an order after a production delay. Demand uncertainty affects vehicle capacity, stop sequence, depot inventory, labor requirements, and time-window feasibility.

Let D_i denote demand at customer i. A forecast supplies an estimate μ_i = E[D_i], while variability can be represented by σ_i² = Var(D_i). These statistics describe a distribution only partially; they do not establish that demand is normally distributed or independent across customers. Correlation is important. For example, hot weather may simultaneously increase demand for beverages at many locations.

1.2 Travel-time uncertainty

Travel time depends on congestion, incidents, weather, signal timing, loading conditions, and driver behavior. Let T_ij be travel time from node i to node j. A deterministic model uses one value, whereas a stochastic model may use a distribution or scenarios. Time-window service requires consideration of both expected arrival and the probability of lateness.

If a route contains legs 1,2,…,m, its total travel time is:

where T_k is travel time on leg k and S_k is service time at the associated stop. This expression is an identity for route duration. If the terms are random, route-duration variance is:

where the last summation covers every distinct pair of random components X_a and X_b. The simplified expression that omits covariance is valid only when the components are independent or covariances are negligible. Congestion often creates positive correlation, so simply adding individual standard deviations may understate risk.

1.3 Disruptions

Disruptions can be classified by origin and duration:

A disruption may be local or systemic. A single blocked street can be handled through local repair, whereas a regional storm may invalidate the assumptions of the entire plan.

2. Routing Models Under Uncertainty

2.1 Deterministic baseline

The vehicle-routing problem (VRP) assigns customers to vehicles and determines visit sequences subject to capacity, route duration, and possibly time-window constraints. A common binary variable is x_ijv, equal to 1 when vehicle v travels directly from node i to node j, and 0 otherwise. If c_ij is travel cost, a basic objective is:

Typical constraints require every customer to be visited once, preserve flow into and out of each customer, respect vehicle capacity, and eliminate subtours. This model is useful as a baseline, but its solution is optimal only for the specified data.

2.2 Stochastic programming

Stochastic programming represents uncertain inputs through scenarios. Let ω ∈ Ω denote a scenario with probability p_ω, and let x be decisions made before uncertainty is revealed. A two-stage model uses first-stage decisions for planned routes and second-stage decisions y_ω for scenario-specific recourse:

where cᵀx is planned cost and Q(x,ω) is the minimum recourse cost in scenario ω. Recourse may include late-delivery penalties, outsourced transport, vehicle reassignment, or customer cancellation costs.

The model assumes that scenario probabilities are meaningful and that recourse decisions can be made after the relevant uncertainty is observed. A route cannot use future information prematurely. This requirement is called non-anticipativity. Stochastic models are valuable when probability estimates are credible and the number of scenarios is manageable. They can become computationally expensive as the number of customers, vehicles, and scenarios grows.

2.3 Chance constraints

A chance constraint controls the probability of violating a service requirement. For example:

Here H is the maximum permitted route duration and α is the tolerated violation probability. If α = 0.05, the route should meet the duration limit in at least 95% of modeled conditions.

Chance constraints are meaningful only when the probability model is calibrated. They may also be difficult to evaluate for correlated or non-normal travel times. A normal approximation can be used only when justified by data and aggregation assumptions; it should not be applied automatically to skewed congestion or weather distributions.

2.4 Robust optimization

Robust optimization protects a solution against a specified uncertainty set rather than relying on probabilities. Let U be the set of plausible demand and travel-time realizations. A robust formulation is:

This worst-case objective is intentionally conservative. A less extreme approach minimizes nominal cost plus a protection term, or limits worst-case constraint violation. For example, capacity may be protected against demand increases within an uncertainty budget. Robustness is attractive when probability estimates are unreliable, but excessive conservatism can produce unnecessary empty capacity and long routes.

The quality of a robust model depends on the uncertainty set. If U is too narrow, protection is inadequate; if it is too broad, the plan may be expensive and operationally unrealistic. Historical percentiles, engineering limits, weather forecasts, and expert judgment can be combined to construct the set.

2.5 Risk measures

Expected cost alone may hide rare but severe failures. A risk-averse planner may use variance, a service-level penalty, or conditional value at risk (CVaR). For loss L, confidence level β, and threshold η, CVaR is the expected loss in the worst (1−β) fraction of cases:

where (z)^+ = max(z,0). CVaR is appropriate when tail outcomes such as missed delivery windows, spoiled products, or emergency transport are especially costly. It is not a substitute for specifying the correct loss function: a model that assigns no cost to customer harm will not protect customers merely because it uses CVaR.

3. Scenario Analysis and Model Design

Scenario analysis translates uncertain information into decision-relevant alternatives. A useful scenario set is diverse but not arbitrary. Scenarios may represent:

• normal traffic;
• severe congestion during a peak period;
• heavy rain or snow;
• a major road closure;
• higher-than-forecast demand;
• multiple simultaneous events.

Each scenario should specify affected arcs, travel times, demand, vehicle availability, and operational rules. Probabilities may be estimated from historical data, forecast systems, or expert elicitation. When probabilities are disputed, planners should report sensitivity rather than presenting a single probability as fact.

A route can be evaluated using expected cost:

where C_ω is the cost in scenario ω. If service reliability matters, report the probability of meeting all relevant time windows:

This ratio is a realized performance measure. A predicted reliability is a probability derived from the model and should be labeled as such.

Scenario analysis should compare alternatives, not merely produce a preferred route. For each route, managers should examine expected cost, worst-case cost, late stops, vehicle utilization, unserved demand, recovery time, and sensitivity to assumptions. A route with slightly higher expected cost may be preferable if its disruption performance is substantially better.

4. Dynamic Routing and Rolling-Horizon Optimization

4.1 Dynamic routing

In dynamic routing, information arrives during execution. New orders, traffic updates, weather alerts, and vehicle positions alter the state of the system. Let s_t represent the state at time t, including vehicle locations, remaining capacity, completed stops, outstanding orders, and network conditions. An action a_t is selected using current information, and the system evolves according to:

where w_t represents new information or disturbance. The objective is not necessarily to compute one complete route at the beginning; it is to select a sequence of actions that performs well as the state changes.

A fully dynamic optimization can be computationally difficult. Practical systems therefore use event-triggered re-optimization, heuristics, approximate dynamic programming, or model predictive control.

4.2 Rolling horizon

A rolling-horizon method repeatedly optimizes a forward planning window. At the current time, the system plans over a horizon, executes only the immediate portion, receives updated information, and then plans again. For example, a carrier may optimize the next six hours every 15 minutes but commit only stops that cannot realistically be changed.

The method can be represented as:

1. Observe current state and update forecasts.
2. Optimize over the future horizon.
3. Freeze decisions within a commitment interval.
4. Execute the next action or set of actions.
5. Advance time and repeat.

The commitment interval is essential. Replanning every minute without stability controls can cause route oscillation, driver confusion, and customer-service failures. A practical objective may include a route-change penalty:

where λ expresses the managerial value placed on plan stability. Change cost may include driver communication, additional handling, customer notification, and disruption to warehouse sequencing.

5. Real-Time Re-Routing Architecture

A real-time routing system requires more than an optimization algorithm. It needs a reliable data and decision architecture:

1. Data capture: GPS, telematics, order management, traffic feeds, weather services, and driver status.
2. Data validation: removal of impossible coordinates, stale timestamps, duplicate orders, and inconsistent vehicle states.
3. State estimation: reconciliation of planned and actual positions, service completion, capacity, and estimated arrival times.
4. Event detection: identification of threshold breaches, closures, cancellations, or high-risk delays.
5. Optimization and route repair: selection of a new route or local modification.
6. Human approval and communication: dispatchers and drivers receive interpretable instructions.
7. Execution monitoring: comparison of predicted and actual outcomes.
8. Learning: recalibration of travel-time and disruption models.

Re-routing may be local, changing only the affected segment, or global, re-optimizing all vehicles. Local repair is faster and more stable; global re-optimization may produce greater savings after a systemic disruption. The choice should depend on disruption scale, computational time, and the cost of changing committed work.

A common insertion heuristic evaluates where a new stop can be inserted. If insertion between nodes i and j adds distance, the incremental travel cost is:

where k is the new customer and c_a,b is the cost from node a to node b. The insertion is feasible only if capacity, time windows, driver rules, and product constraints remain satisfied. This formula measures direct route-cost increase; it does not by itself measure downstream lateness or risk.

6. Worked Example: Choosing a Route Under Travel-Time Risk

Consider two feasible routes for a temperature-sensitive delivery. Route A has an expected travel time of 52 minutes and a 20% probability of taking 80 minutes because of a congestion event. In the remaining 80% of cases, it takes 45 minutes. Route B takes 60 minutes with certainty. The delivery deadline is 60 minutes. Late delivery costs £120, and operating cost is £1 per minute of travel.

For Route A, expected travel time is:

E[T_A] = 0.20(80) + 0.80(45) = 52 minutes.

Its expected operating cost is £52. Because the congestion scenario exceeds the deadline, expected lateness penalty is 0.20 × £120 = £24. Thus expected total cost is £76. Route B has operating cost £60 and no lateness penalty, giving expected total cost £60.

Route B is preferred under expected total cost, despite having a longer nominal travel time than Route A’s non-congested outcome. Route A, however, may be acceptable if the lateness cost is much lower, if the deadline is flexible, or if Route B has other risks not included in the example.

This example illustrates three principles. First, expected travel time alone is not sufficient when penalties are nonlinear. Second, a low-probability event can determine the preferred route. Third, the decision depends on the cost and severity assigned to failure. The calculation assumes the stated probabilities are valid, the two travel-time outcomes are exhaustive, and no other costs or capacity effects exist.

7. Illustrative Case: Urban Grocery Delivery During a Storm

Background

This illustrative case concerns a grocery distributor serving 1,200 home-delivery orders from one urban depot. Vehicles are refrigerated, customer time windows are two hours, and many orders contain chilled products. The normal planning system uses predicted travel times and assigns routes the evening before dispatch.

Problem

A severe-weather warning predicts intense rain during the afternoon. At dispatch, 20 orders are cancelled, 35 urgent orders are added, and a bridge on a major corridor is closed. Historical travel-time distributions are no longer representative. A purely deterministic plan would send several vehicles toward the closed bridge and would leave insufficient capacity for urgent orders.

Analysis

The operations team creates three scenarios: moderate rain, severe rain with the bridge closed, and severe rain with an additional highway incident. It estimates travel times using current traffic data and assigns higher penalties to missed windows for chilled products. The team also identifies customers with vulnerable-service requirements and marks routes with low spare capacity.

A stochastic model is used for pre-dispatch planning, while a robust constraint reserves capacity for urgent orders and likely cancellations. The rolling-horizon system re-optimizes every 20 minutes, but it freezes stops within 30 minutes of arrival to prevent continuous changes. A local repair rule first attempts to bypass the bridge. If a vehicle’s predicted arrival exceeds a time-window threshold, the system considers transferring selected stops to another vehicle.

Approach and solution

The dispatcher approves a revised plan rather than allowing fully autonomous changes. Two vehicles are held at the depot as recovery capacity. The system inserts urgent orders into routes with sufficient capacity and geographic compatibility. Drivers receive updated sequences and explanations: bridge closure, revised arrival estimate, and customer-notification requirement. Customers affected by substantial changes receive revised delivery windows before the driver arrives.

Outcome

The revised plan increases planned kilometres by 7% and uses 9% more labor time than the original plan. However, it reduces projected late deliveries from 14% to 5%, avoids refrigerated-product exposure, and preserves service for 96% of urgent orders. The two reserve vehicles are not both needed; one handles a transferred route and the other remains available for a later breakdown.

Learning points

The case demonstrates that resilience has a cost. The best response was not the route with minimum kilometres but the plan that combined scenario analysis, spare capacity, controlled re-optimization, and communication. It also demonstrates why data quality and human authority matter: a route optimizer cannot infer a bridge closure reliably if the event feed is stale, and it should not silently change a customer commitment without governance.

8. Performance Measurement and Managerial Trade-Offs

A disruption-aware routing program should use a balanced set of measures:

Trade-offs should be made explicit. Extra vehicle capacity can reduce late deliveries but increase emissions and cost. Aggressive re-routing may improve aggregate performance while disadvantaging neighborhoods with poor data coverage or lower commercial priority. Managers should distinguish a system that performs well on average from one that is dependable under stress.

9. Technology, AI, and Human Governance

Modern routing platforms combine optimization, cloud computing, telematics, machine-learning forecasts, and external data feeds. Machine learning can estimate travel times, cancellation probabilities, or demand; mathematical optimization can then use those estimates subject to operational constraints. Prediction and optimization should not be confused. A highly accurate forecast does not guarantee a feasible or fair route, and an excellent optimizer cannot correct systematically biased data.

AI-enabled systems require:

• documented data provenance and update frequency;
• monitoring for forecast drift;
• explainable route changes for dispatchers and drivers;
• fallback procedures when feeds fail;
• access controls for customer and driver data;
• testing under rare but consequential scenarios;
• human override and audit logs.

Location data may reveal employee movements and customer habits. Collection should be limited to legitimate operational purposes, retained only as long as necessary, and protected against unauthorized access. Automated prioritization should not systematically reduce service to remote, low-income, disabled, or linguistically marginalized customers. Safety rules, driving-hour regulations, hazardous-material requirements, and contractual delivery commitments remain binding even when an algorithm recommends a different action.

10. Limitations and Best Practices

No uncertainty model is complete. Scenario probabilities may be wrong, correlations may be omitted, and rare events may not appear in historical records. Robust optimization can become too conservative, while stochastic optimization can create false precision. Real-time data can be delayed or contradictory. Re-optimization can also undermine driver trust if plans change too frequently.

Best practices include:

1. Establish a deterministic baseline before adding complexity.
2. Separate forecast uncertainty from realized disruption response.
3. Calibrate travel-time and demand models using out-of-sample data.
4. Model correlation where common weather or congestion affects multiple routes.
5. Use scenario stress tests, including compound disruptions.
6. Penalize lateness, cancellation, product loss, and route changes realistically.
7. Set commitment intervals and explicit dispatcher override rules.
8. Maintain reserve capacity according to measured disruption exposure.
9. Compare local repair with global re-optimization.
10. Audit performance by customer group, geography, driver, and event type.
11. Review forecasts and decisions after every major disruption.
12. Design manual fallback processes for system outages.

Chapter Summary

Routing under uncertainty treats demand, travel time, capacity, and network availability as variable rather than fixed. Stochastic programming uses probability-weighted scenarios and recourse; robust optimization protects against an explicitly defined uncertainty set; chance constraints control violation probability; and risk measures such as CVaR address severe tail outcomes. Dynamic routing updates decisions as the system state changes, while rolling-horizon optimization repeatedly plans ahead but executes only a controlled portion of the plan.

Effective real-time re-routing depends on validated data, state estimation, event detection, feasible route repair, communication, and learning. Scenario analysis helps managers compare expected cost, reliability, worst-case exposure, flexibility, and stability. The illustrative grocery case shows that resilience often requires reserve capacity and moderate additional cost. Finally, technology and AI must operate within safety, privacy, fairness, regulatory, and human-governance requirements. The advanced practitioner’s task is therefore not to eliminate uncertainty, but to design routes and decision processes that remain economically and operationally credible when conditions change.

Key Terms

Uncertainty: Imperfect knowledge or variability in future conditions.

Disruption: An event that materially changes planned operations.

Stochastic routing: Routing that represents uncertain inputs probabilistically.

Robust optimization: Optimization designed to remain feasible across a specified uncertainty set.

Scenario: A structured possible realization of uncertain conditions.

Recourse: Corrective action available after uncertainty is observed.

Non-anticipativity: The requirement that decisions cannot use information unavailable at their decision time.

Chance constraint: A constraint requiring a specified probability of feasibility.

CVaR: Expected loss in the worst selected tail of a loss distribution.

Dynamic routing: Routing in which decisions and system states evolve during execution.

Rolling horizon: Repeated optimization over a moving future planning window.

Commitment interval: The period of planned work that is protected from routine changes.

Route repair: A local modification that restores feasibility after an event.

Uncertainty set: The defined collection of plausible parameter realizations.

Travel-time correlation: Dependence among travel times caused by common conditions.

Reserve capacity: Deliberately unused vehicle, labor, or time capacity held for recovery.

Service reliability: The probability or realized proportion of deliveries meeting requirements.

Route stability: The degree to which planned routes remain unchanged.

State estimation: Reconstruction of current operational conditions from imperfect data.

Nonlinear penalty: A cost that increases disproportionately when a service or operational threshold is violated.

Review Questions

5 Short Answer Questions

1. Distinguish uncertainty from disruption in route planning.
2. What is the purpose of a chance constraint?
3. Why is non-anticipativity important in stochastic programming?
4. State two reasons why route changes should be controlled in a rolling-horizon system.
5. Identify three data sources used in real-time routing.

5 Long Answer Questions

1. Compare stochastic programming and robust optimization, including their assumptions, advantages, and limitations.
2. Explain how travel-time correlation can affect route-risk estimates.
3. Describe a complete architecture for real-time re-routing from data capture through post-event learning.
4. Discuss the managerial trade-off between route efficiency, resilience, and stability.
5. Explain how AI can support routing while remaining subject to safety, privacy, fairness, and regulatory governance.

3 Analytical / Application Questions

1. A carrier must choose between a short route with a 15% probability of severe delay and a longer route with reliable travel time. Design a scenario analysis and specify the cost and service data needed to select the route.
2. A bridge closure occurs after vehicles have departed. Propose criteria for deciding between local route repair and global re-optimization.
3. Design a rolling-horizon policy for a same-day delivery operation. Specify the planning horizon, commitment interval, event triggers, route-change penalty, and performance measures.

Multiple Choice Questions with Answers

Question 1

Which method protects a route against realizations within a specified uncertainty set rather than requiring reliable scenario probabilities?

A. Robust optimization

B. Deterministic shortest path

C. Descriptive forecasting

D. First-come-first-served dispatching

Correct Answer: A. Robust optimization

Question 2

In a two-stage stochastic routing model, what does recourse represent?

A. Decisions made before uncertainty is known

B. Corrective decisions made after a scenario is observed

C. A constraint eliminating all vehicle capacity

D. A method for measuring fuel consumption only

Correct Answer: B. Corrective decisions made after a scenario is observed

Question 3

A route has travel times of 80 minutes with probability 0.20 and 45 minutes with probability 0.80. What is its expected travel time?

A. 45 minutes

B. 52 minutes

C. 62 minutes

D. 80 minutes

Correct Answer: B. 52 minutes

Question 4

What is the principal purpose of a commitment interval in rolling-horizon routing?

A. To prevent every customer from receiving service

B. To ensure all routes are permanently fixed

C. To limit instability caused by excessive route changes

D. To remove the need for updated information

Correct Answer: C. To limit instability caused by excessive route changes

Question 5

In the insertion-cost expression ∆c = c_i,k + c_k,j − c_i,j, what does customer k represent?

A. The depot that is being closed

B. The new stop being inserted between i and j

C. The vehicle’s maximum capacity

D. The probability of congestion

Correct Answer: B. The new stop being inserted between i and j

Question 6

Which measure focuses specifically on severe outcomes in the tail of a loss distribution?

A. Mean travel distance

B. Median stop count

C. Conditional value at risk

D. Nominal vehicle capacity

Correct Answer: C. Conditional value at risk

Question 7

Why can omitting covariance understate route-duration risk?

A. Travel-time components may be positively correlated by common congestion or weather

B. Vehicle capacity is always normally distributed

C. Service times are never observed

D. All routes necessarily have identical lengths

Correct Answer: A. Travel-time components may be positively correlated by common congestion or weather

Question 8

Which action is an example of recourse after a vehicle breakdown?

A. Using a substitute vehicle to transfer the remaining stops

B. Ignoring the breakdown until the end of the day

C. Deleting all historical travel-time data

D. Increasing the original vehicle’s physical capacity

Correct Answer: A. Using a substitute vehicle to transfer the remaining stops

Question 9

Which performance measure most directly evaluates how quickly operations return to planned service after disruption?

A. Recovery time

B. Average customer distance from the depot

C. Number of product categories

D. Nominal route length

Correct Answer: A. Recovery time

Question 10

A route has an expected operating cost of £52 and a 20% probability of a £120 late-delivery penalty. Assuming no other costs, what is its expected total cost?

A. £52

B. £60

C. £72

D. £76

Correct Answer: D. £76