Time-Dependent Vehicle Routing

Unlike static VRP, TDVRP models travel time between nodes as a step function or continuous function of the departure time. This is often represented by a travel time profile that varies across the planning horizon.

• Peak-hour penalties: Travel times increase significantly during morning and evening rush hours.
• FIFO property: Most models enforce the First-In-First-Out property, ensuring that leaving later never results in an earlier arrival, which maintains physical realism.
• Data source: Functions are derived from historical GPS probe data, road sensor networks, or third-party traffic APIs.

A core decision variable in TDVRP is not just the sequence of visits, but the optimal departure time from each node. Waiting at a customer location or depot can be a valid strategy to avoid a high-cost travel period.

• Strategic waiting: The solver may intentionally delay a vehicle's departure to let a congestion peak pass, reducing total route duration.
• Temporal constraints: This must be balanced against hard service time windows at customer locations.
• Computational impact: Adding a temporal dimension to the decision space significantly increases the problem's complexity, often requiring advanced metaheuristics like ALNS or Tabu Search.

TDVRP can be implemented in two distinct operational modes:

• Static TDVRP: Uses historically predicted time-dependent travel times to generate a fixed plan at the start of the day. This is a proactive, offline optimization.
• Dynamic TDVRP: Continuously re-optimizes routes in real-time as new traffic information, disruptions, or orders arrive. This reactive approach often uses Model Predictive Control (MPC) to solve a rolling horizon problem, applying only the next immediate decision before re-solving.

Efficiently solving TDVRP requires specialized graph structures. A static graph is insufficient because edge weights are time-variant.

• Time-expanded networks: The physical network is duplicated across discrete time steps, transforming the time-dependent problem into a larger, static one that can be solved with modified versions of Dijkstra's Algorithm.
• Contraction Hierarchies (CH): Preprocessing techniques like CH are adapted for time-dependent graphs to enable millisecond-fast shortest-path queries during iterative optimization.
• Isochrones: Time-dependent isochrones are used to visualize and constrain the service area, showing reachable locations within a specific time budget given the current traffic conditions.

TDVRP engines are a critical component of a Supply Chain Digital Twin. The twin provides the real-time traffic feed and network state, while the TDVRP solver acts as the decision-making brain.

• What-if simulation: Planners can simulate the impact of a major traffic incident by injecting it into the time-dependent travel time matrix and re-solving to see the cascading effects on ETA and cost.
• Real-time state mirroring: Vehicle positions from GPS are map-matched to the digital graph, providing the solver with accurate starting positions for re-optimization.
• Predictive ETAs: The combination provides highly accurate, continuously updated Estimated Time of Arrival calculations for customers.

The objective function in TDVRP extends beyond simple distance minimization to capture real-world operational costs that are time-sensitive.

• Fuel and emissions: Fuel consumption and carbon footprint are non-linear functions of speed, which varies with time-dependent congestion. Minimizing time often directly minimizes emissions.
• Driver wages: Total route duration, including waiting time, directly impacts labor costs, making the trade-off between waiting and driving through congestion a key economic decision.
• Service level: The primary goal is often to maximize the number of deliveries completed within their service time windows, turning the problem into a multi-objective optimization challenge.

The mathematical core of TDVRP. Instead of a scalar value, each road segment is assigned a time-dependent travel time function that maps a departure time to a traversal duration. Common models include:

• Step functions: Discrete time buckets (e.g., rush hour vs. off-peak)
• Continuous piecewise linear functions: Smooth transitions between periods
• Speed-based profiles: Historical average speeds per 5-minute interval These functions must satisfy the First-In-First-Out (FIFO) property to prevent paradoxical situations where leaving later results in arriving earlier.

A critical consistency constraint for time-dependent travel time models. The First-In-First-Out property states that if vehicle A departs a link before vehicle B, vehicle A must arrive before vehicle B. Mathematically, the arrival time function must be strictly monotonically increasing. Without FIFO, the model permits non-physical behavior where waiting at a node becomes beneficial. Enforcing FIFO ensures the time-expanded graph remains acyclic and that standard shortest-path algorithms can be correctly applied.