🧩 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) asks: given a depot, a set of customers with demands and time windows (earliest and latest service times), and a fleet of homogeneous vehicles with limited capacity, find a set of routes that:

1. Service all customers exactly once
2. Respect vehicle capacity constraints
3. Arrive at each customer within its time window
4. Minimize total travel time or the number of vehicles

Concrete Instance (5-node example):

• Depot at (0, 0), open from 0 to 1000 minutes
• Customer 1: location (10, 5), demand 2 units, time window [50, 150]
• Customer 2: location (15, 20), demand 3 units, time window [100, 200]
• Customer 3: location (5, 15), demand 1 unit, time window [60, 120]
• Customer 4: location (20, 10), demand 2 units, time window [120, 250]
• Customer 5: location (12, 25), demand 2 units, time window [80, 180]
• Vehicle capacity: 5 units
• One route: Depot → C3 (arrive 20, leave 21) → C1 (arrive 45, leave 46) → C5 (arrive 65, leave 66) → C2 (arrive 85, wait, serve at 100, leave 101) → Depot (arrive 120)

This route respects capacity (1+2+2+3 = 8, exceeds—so infeasible; try Depot → C1 → C4 → Depot instead).

Input: Locations, demands, time windows, vehicle capacity, travel-time matrix.
Output: Assignment of customers to routes, arrival/departure times at each stop, or "infeasible" if no solution exists.

---

Why It Matters

• Last-Mile Delivery: E-commerce, food delivery (DoorDash, Uber Eats) rely on VRPTW to meet customer time-window commitments while minimizing fleet cost.
• Parcel Services: DHL, UPS, FedEx solve VRPTW variants daily to route millions of shipments across geographic regions.
• Dial-a-Ride & Paratransit: Public transportation for elderly and disabled passengers must respect passenger pickup/dropoff windows and vehicle capacity.
• Field Service: Technician scheduling for maintenance, repairs, and installations must honor time windows while balancing workload across technicians.

---

Modeling Approaches

Approach 1: Mixed-Integer Programming (MIP)

Paradigm: Linear constraints over binary and continuous variables.

Decision Variables:

• x_{i,j,k} ∈ {0,1}: vehicle k travels directly from customer i to customer j
• t_{i,k} ≥ 0: arrival time at customer i using vehicle k
• load_{k} ≥ 0: vehicle k's load at any point

Key Constraints:

• Flow conservation: Each customer visited by exactly one vehicle: ∑_k ∑_j x_{i,j,k} = 1 ∀i ∈ Customers
• Time windows: a_i ≤ t_{i,k} ≤ b_i ∀i,k (where a_i, b_i are earliest/latest times)
• Timing propagation: t_{j,k} ≥ t_{i,k} + service_i + dist(i,j) − M(1 − x_{i,j,k}) (big-M constraint)
• Capacity: ∑_{i ∈ route_k} demand_i ≤ capacity ∀k
• No subtours: Subtour elimination constraints (e.g., Miller–Tucker–Zemlin)

Trade-offs:

• ✅ Optimal solutions: Exact solvers (CPLEX, Gurobi) prove optimality or find gaps.
• ❌ Scalability: Large instances (100+ customers) may time out; big-M coefficients can weaken LP relaxations.
• ✅ Standard form: Familiar to operations researchers; extensive software support.

Approach 2: Constraint Programming (CP)

Paradigm: Rich global constraints, domain propagation, backtracking search.

Decision Variables:

• succ[i] ∈ Customers ∪ {Depot}: successor of customer i in its route
• vehicle[i] ∈ {1..k}: vehicle assigned to customer i
• arrival[i] ∈ [0, horizon]: arrival time at customer i

Key Constraints:

• Cumulative: circuit(succ) ensures routes form valid cycles
• Disjunctive: all_different(vehicle) distributed across routes; or use table constraint for allowed sequences
• Timing: arrival[j] ≥ arrival[i] + service_i + dist(i, j) where succ[i] = j
• Time windows: a_i ≤ arrival[i] ≤ b_i
• Capacity: cumul(succ, demand) ≤ capacity using cumulative/lex_chain global constraint

Trade-offs:

• ✅ Expressiveness: Non-linear constraints, complex domain interactions handled naturally.
• ✅ Propagation: Arc-consistency and specialized algorithms (e.g., cumulative constraint) prune aggressively.
• ❌ Proving optimality: CP solvers typically find good feasible solutions but may not guarantee optimality without extensive search.
• ✅ Scalability: Often faster on highly constrained instances (100–500 customers).

---

Key Techniques

1. Time-Based Constraint Propagation

Time windows couple arrival times across the route. The cumulative constraint and its variants (e.g., circuit with time) efficiently propagate:

• If customer i must be serviced by time b_i, and travel to i takes d_min time, then predecessor j must leave by b_i − d_min − service_i.
• Propagation detects infeasibilities early, pruning large portions of the search space.

2. Vehicle Routing Heuristics & Local Search

For large instances, exact methods are often impractical. Metaheuristics are essential:

• Savings algorithm: Merge routes based on travel-distance savings; quick feasible solution.
• Simulated annealing, Tabu search: Explore the neighborhood of a current solution by relocating customers or swapping route segments (2-opt, 3-opt moves).
• Large neighborhood search (LNS): Fix most of the solution, re-optimize a subset of routes.

3. Symmetry Breaking & Search Strategy

Routes are inherently symmetric (Depot → A → B → Depot ≡ Depot → B → A → Depot with reversed directions). Symmetry-breaking constraints can reduce search:

• Enforce canonical orderings (e.g., vehicle k must serve at least one customer with lower ID than vehicle k+1).
• Intelligent variable ordering: Branch on time-constrained or high-demand customers first; use fail-first heuristics (variables with smallest domain).

---

Challenge Corner

Open Questions for You:

1. Model Reduction: Can you reformulate VRPTW with fewer variables (e.g., only succ[i] and arrival[i], deriving vehicle assignment implicitly) without losing propagation strength? What trade-offs emerge?

2. Symmetry & Canonical Solutions: In a VRPTW with multiple identical vehicles, k! route permutations represent the same solution. Propose three symmetry-breaking constraints that do NOT artificially limit optimal solutions.

3. Hybrid Strategies: How would you combine CP (for time-window propagation and feasibility finding) with Mixed-Integer Programming (for final optimization)? Sketch a Benders' decomposition or column-generation approach.

4. Practical Extensions: Real-world VRPTW adds:

   • Soft time windows (penalty for lateness) instead of hard constraints
   • Multiple depots or heterogeneous vehicle types
   • Dynamic orders (customers arrive throughout the day)

   Which extension would you tackle first, and why?

---

References

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

   • Seminal work; introduces the Solomon benchmark instances (100-customer problems still used today).

2. Hooker, J. N. (2005). "Planning and Scheduling by Logic-Based Benders Decomposition." Operations Research, 55(3), 588–602.

   • Shows how to integrate CP and MIP for VRPTW; strong practical results.

3. Shaw, P. (1998). "Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems." CP-98 Principles and Practice, LNCS 1520.

   • Pioneering hybrid CP + local search approach; introduced LNS.

4. OR-Tools Vehicle Routing Library (Google). [(developers.google.com/redacted)(developers.google.com/redacted)

   • Production-grade, open-source solver with time windows, capacity, and pickup-delivery constraints.

---

Happy problem-solving! Whether you reach for MIP, CP, or a hybrid approach, VRPTW offers a rich playground for optimization techniques. 🚚

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 7.47 AIC · ⌖ 6.15 AIC · ⊞ 6.2K · ◷

• expires on Sep 16, 2026, 3:34 AM UTC-08:00

[github-actions[bot]]

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

A newer discussion is available at Discussion #59949.