🧩 Constraint Solving POTD:Problem of the Day: Vehicle Routing Problem with Time Windows (VRPTW)

[github-actions[bot]]

Problem Statement

The Vehicle Routing Problem with Time Windows (VRPTW) is a classic optimization problem that combines routing and scheduling constraints. You have:

• A depot (starting/ending location, usually index 0)
• A set of customers with known locations (latitude/longitude or distance matrix)
• Demand at each customer (units to deliver/pickup)
• Vehicle fleet with fixed capacity Q
• Service time at each customer
• Time windows [a_i, b_i] for each customer (arrive between a_i and b_i)
• Travel time between any two locations

Goal: Construct a set of routes, one per vehicle, that:

• Visit all customers exactly once
• Respect each customer's time window
• Don't exceed vehicle capacity
• Minimize total travel time (or vehicle count, or a combination)

Small Example

Suppose you have:

• 1 depot, 4 customers
• 2 vehicles with capacity 10 units
• Customer demands: [5, 3, 4, 2]
• Time windows: Customer 1 ∈ [8:00, 12:00], Customer 2 ∈ [9:00, 14:00], etc.
• Symmetric distance matrix (5 locations)

A solution might be: Vehicle 1 → Depot → Customer 1 → Customer 3 → Depot; Vehicle 2 → Depot → Customer 2 → Customer 4 → Depot, with cumulative travel time minimized.

---

Why It Matters

Last-mile delivery: Amazon, UPS, and DoorDash use VRPTW variants daily to route millions of packages while respecting delivery windows—a 1% improvement in travel distance saves millions annually.

Field service scheduling: Plumbers, electricians, and maintenance engineers must visit multiple sites within time windows (customer availability or technician shifts).

Humanitarian logistics: Disaster relief organizations use VRPTW to deliver aid across fragmented networks with strict access times.

---

Modeling Approaches

Approach 1: Mixed-Integer Programming (MIP)

Paradigm: Continuous relaxation with binary routing variables.

Variables:

• x_{ij}^k ∈ {0, 1}: Vehicle k travels directly from customer i to customer j
• t_i: Arrival time at customer i
• load_i: Load of vehicle upon arriving at customer i

Key constraints:

• Flow balance: Each customer visited exactly once by exactly one vehicle
• Time window: a_i ≤ t_i ≤ b_i for all customers
• Time consistency: t_i + service_i + travel_{ij} ≤ t_j + M(1 - x_{ij}^k) (if vehicle goes from i to j)
• Capacity: load_i + demand_j ≤ Q on feasible arcs

Trade-offs: Strong LP relaxation; standard solver (CPLEX, Gurobi) easily scales to 100+ customers; but big-M coefficients can weaken bounds.

Approach 2: Constraint Programming (CP)

Paradigm: Rich domains, global constraints, and search via labeling.

Variables:

• next[i]: Which customer (or depot) follows customer i in the route
• arrival[i]: Arrival time at customer i (integer domain)
• route_vehicle[i]: Which vehicle handles customer i

Key constraints:

• Circuit or Disjunctive: Ensure routes form valid paths (no cycles except depot)
• Element/reification: arrival[next[i]] = arrival[i] + service_i + travel[i, next[i]]
• Interval & cumulative: Optional task scheduling (vehicle presence on each arc)
• Time window: a_i ≤ arrival[i] ≤ b_i
• Capacity: Cumulative capacity tracking along each route

Trade-offs: More natural expression of time/sequence; propagation on global constraints (cumulative, circuit) is stronger than MIP; scales well to thousands of customers with good search heuristics; fewer numerical issues.

Example Model (OR-Tools / Python-MiniZinc style)

% MiniZinc-inspired pseudocode
int: n_customers;
array[1..n_customers] of int: demand, time_window_start, time_window_end;
array[0..n_customers, 0..n_customers] of int: travel_time;
int: capacity;
int: n_vehicles;

% Variables
array[0..n_customers] of var 0..n_customers: next;     % next customer in sequence
array[0..n_customers] of var 0..max_time: arrival;     % arrival time
array[1..n_customers] of var 1..n_vehicles: vehicle;   % which vehicle

% Constraints
constraint circuit(next);  % valid routes (one connected path per vehicle)

constraint forall(i in 1..n_customers)(
  arrival[i] >= time_window_start[i] /\ 
  arrival[i] <= time_window_end[i]
);

constraint forall(i in 1..n_customers where next[i] > 0)(
  arrival[next[i]] = arrival[i] + 1 + travel_time[i, next[i]]
);

constraint arrival[0] = 0;  % depot time

% Solve
minimize sum(i in 0..n_customers)(travel_time[i, next[i]]);

---

Key Techniques

1. Time-Window Propagation & Reachability

• Latest-start times: Work backward from each time window to reduce domains of predecessors
• Earliest-arrival times: Forward pass to tighten lower bounds
• Unreachability pruning: If no feasible arc can reach a customer within its window from a given predecessor, prune that arc

2. Local Search & Large Neighborhood Search (LNS)

• Lin-Kernighan moves (2-opt, 3-opt): Efficiently explore nearby routes
• DESTROY-REPAIR: Randomly remove a subset of customers and re-insert via cheapest-insertion
• Guided Local Search (GLS): Penalize frequently visited arc-time pairs to escape local optima
• Highly effective in practice (often within 1–5% of optimality for 1000+ customer instances)

3. Decomposition & Route Enumeration

• Shortest path subproblems: Column generation to price out profitable routes (Dantzig-Wolfe)
• Cluster-first, route-second: Use k-means or geographic partitioning to pre-assign customers to vehicles, then optimize routes within clusters
• Set partitioning formulation: Enumerate feasible routes, solve as MIP to select a minimal cover

---

Challenge Corner

Can you model VRPTW with asymmetric costs and precedence constraints?

In real logistics, travel time may differ by direction (one-way streets, fuel costs). Some customers have precedence (must pick up before delivery at another location). How would you extend the models above to handle these? What propagation rules become crucial for pruning infeasible precedence+time-window combinations?

---

References

1. Solomon, M. M. (1987). "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints." Operations Research, 35(2), 254–265.

   • The foundational benchmark and exact algorithm for VRPTW.

2. Bent, R., & Van Hentenryck, P. (2006). "A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows." Journal of Heuristics, 12(4-5), 309–330.

   • Exemplary hybrid CP+local-search approach.

3. Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2013). "Heuristics for Multi-Attribute Vehicle Routing Problems: A Survey and Synthesis." European Journal of Operational Research, 231(1), 1–21.

   • Comprehensive survey of modern approaches.

4. OR-Tools Routing Library (Google GitHub): Excellent open-source reference implementation with both MIP and CP engines.

---

Next problem will explore an emerging topic or a deeper scheduling variant!

Generated by 🧩 Constraint Solving — Problem of the Day · haiku45 29.9K · ◷

• expires on Jun 9, 2026, 12:41 PM UTC

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #36638.