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

[github-actions[bot]]

Today's constraint solving problem explores one of the most practically important combinatorial optimization problems in logistics and operations research.

---

Problem Statement

You manage a fleet of delivery vehicles based at a central depot. Each vehicle must serve a set of customers, returning to the depot when done. The twist: every customer has a time window [e_i, l_i] during which service must begin, and each customer requires d_i units of cargo. Each vehicle has capacity Q.

Goal: Find routes for the minimum number of vehicles (primary) with minimum total travel distance (secondary) such that:

• Every customer is visited exactly once
• Vehicle capacity is not exceeded on any route
• Service at customer i begins within [e_i, l_i]
• Vehicles may arrive early and wait, but cannot arrive after l_i

Small Concrete Instance

5 customers, 2 vehicles, depot at node 0, capacity Q = 15:

Node	x	y	Demand	Window	Service time
0 (depot)	5	5	0	[0, 100]	0
1	1	2	4	[10, 30]	5
2	8	1	6	[20, 50]	5
3	9	8	5	[15, 40]	5
4	2	9	3	[5, 25]	5
5	6	6	7	[30, 60]	5

One feasible solution:

• Vehicle 1: depot → 4 → 1 → 2 → depot (load = 13 ✓)
• Vehicle 2: depot → 3 → 5 → depot (load = 12 ✓)

---

Why It Matters

Parcel delivery & e-commerce — Every major courier network (UPS, FedEx, Amazon Logistics) solves millions of VRPTW instances daily; shaving 1% off total distance saves millions in fuel.

Healthcare & home services — Scheduling nurse visits, medical equipment deliveries, and meal services for elderly patients all have hard time-window constraints driven by patient needs and medication schedules.

Field service management — Telecom technicians, HVAC repair crews, and cable installers must arrive within promised windows, making VRPTW the backbone of field service optimization platforms.

---

Modeling Approaches

Approach 1: Constraint Programming (CP)

Decision variables:

• route[v][p] — customer served at position p in vehicle v's route (∈ {0..n}, 0 = depot)
• start[v][p] — time service begins at position p in vehicle v's route
• load[v][p] — cumulative load at position p

Key constraints:

// Every customer visited exactly once
alldifferent_except_zero(flatten(route))
∀ c ∈ {1..n}: count(flatten(route), c) = 1

// Time propagation (travel + service + wait)
start[v][p+1] >= start[v][p] + service[route[v][p]] + dist(route[v][p], route[v][p+1])

// Time window enforcement
e[route[v][p]] <= start[v][p] <= l[route[v][p]]

// Capacity
load[v][p+1] = load[v][p] + demand[route[v][p+1]]
load[v][p] <= Q
```

**Trade-offs:** CP's *cumulative* and *element* global constraints propagate tightly, but the position-based model suffers from large search spaces and symmetry (permutations of routes).

---

#### Approach 2: Mixed-Integer Programming (MIP) — 3-Index Arc Flow

**Decision variables:**
- `x[i,j,v] ∈ {0,1}` — vehicle `v` travels arc `(i→j)`
- `s[i,v] ≥ 0` — start time of service at customer `i` by vehicle `v`

**Key constraints:**
```
// Flow conservation at each customer
∀ i ∈ C, v: Σ_j x[i,j,v] = Σ_j x[j,i,v]

// Each customer visited exactly once
∀ i ∈ C: Σ_v Σ_j x[i,j,v] = 1

// Time window & subtour elimination (via big-M or valid inequalities)
s[i,v] + service_i + t[i,j] - M(1 - x[i,j,v]) <= s[j,v]
e_i <= s[i,v] <= l_i

// Capacity
Σ_i demand_i * Σ_j x[i,j,v] <= Q

Trade-offs: MIP benefits from mature LP relaxations and powerful branching heuristics (branch-and-cut). The 3-index formulation has O(n² · V) binary variables — expensive for large instances, but strong LP bounds. The big-M time linking constraints weaken the LP relaxation.

---

Approach 3: Large Neighbourhood Search (LNS) / Metaheuristic

For large real-world instances (hundreds to thousands of customers), exact methods are impractical. LNS iteratively:

1. Destroys part of the current solution (remove 5–30 customers using a destroy operator: random, worst-removal, or related-removal)
2. Repairs by reinserting removed customers greedily or via a small CP/MIP sub-problem

Trade-offs: Finds high-quality solutions quickly; no optimality guarantees. Shaw's Related Removal operator (remove customers close in space/time) is particularly effective at escaping local optima.

Example CP Model Snippet (OR-Tools Python)

from ortools.constraint_solver import routing_enums_pb2, pywrapcp

manager = pywrapcp.RoutingIndexManager(num_nodes, num_vehicles, depot=0)
routing = pywrapcp.RoutingModel(manager)

# Travel time callback
def time_callback(from_idx, to_idx):
    i = manager.IndexToNode(from_idx)
    j = manager.IndexToNode(to_idx)
    return travel_time[i][j] + service_time[i]

transit_id = routing.RegisterTransitCallback(time_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_id)

# Time window dimension
routing.AddDimension(transit_id, max_wait=100, max_time=200,
                     fix_start_cumul_to_zero=False, name="Time")
time_dim = routing.GetDimensionOrDie("Time")
for i, (early, late) in enumerate(time_windows):
    idx = manager.NodeToIndex(i)
    time_dim.CumulVar(idx).SetRange(early, late)

# Capacity dimension
def demand_callback(idx):
    return demands[manager.IndexToNode(idx)]
demand_id = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(demand_id, 0, [capacity]*num_vehicles,
                                        fix_start_cumul_to_zero=True, name="Capacity")

params = pywrapcp.DefaultRoutingSearchParameters()
params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
params.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
params.time_limit.seconds = 30

solution = routing.SolveWithParameters(params)

---

Key Techniques

1. Time-Window Propagation & Temporal Reasoning

The time dimension in OR-Tools (and similar CP solvers) maintains a lower bound earliest[i] and upper bound latest[i] for each node visit, propagating reductions forward and backward through the route graph. This is essentially a shortest/longest-path computation on a time-expanded DAG — tighter than generic arc consistency.

Forward pass: earliest[j] = max(e_j, earliest[i] + t_{ij} + s_i)
Backward pass: latest[i] = min(l_i, latest[j] - t_{ij} - s_i)

Any node where earliest[i] > latest[i] triggers a domain wipe-out.

2. Symmetry Breaking

The fleet of identical vehicles creates massive symmetry: permuting which vehicle handles which route gives equivalent solutions. Break this with:

• Lexicographic ordering: enforce load[1] >= load[2] >= ... >= load[V]
• First-departure ordering: vehicle v departs depot no earlier than vehicle v-1

Without symmetry breaking, solvers waste effort proving many equivalent optima infeasible.

3. Column Generation (for exact solvers)

Large VRPTW instances are solved optimally via branch-and-price: the LP relaxation of a set-partitioning formulation is solved by column generation, where each column represents a feasible route. The pricing sub-problem is an Elementary Shortest Path Problem with Resource Constraints (ESPPRC) — itself NP-hard but tractable via dynamic programming with dominance rules (Irnich & Desaulniers, 2005).

---

Challenge Corner

Open question: The standard VRPTW assumes deterministic travel times. In practice, traffic congestion makes travel times stochastic.

🤔 How would you model the Stochastic VRPTW? What changes in the constraint formulation when travel times are drawn from probability distributions? Can you guarantee time-window feasibility with high probability (a chance-constrained approach), or must you optimize expected cost?

Bonus: Consider the online variant where customer requests arrive dynamically while vehicles are already en route. How does the re-optimization strategy change?

---

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 definitive benchmark instances, still in use today.)

2. Cordeau, J.-F., Desaulniers, G., Desrosiers, J., Solomon, M.M., & Soumis, F. (2002). "VRP with Time Windows." In The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics. (Comprehensive survey of exact and heuristic methods.)

3. Shaw, P. (1998). "Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems." CP 1998, LNCS 1520. (Introduced the Related Removal operator for LNS.)

4. Google OR-Tools Routing Documentation — [developers.google.com/optimization/routing]((developers.google.com/redacted) (Practical guide with VRPTW examples, actively maintained.)

---

What solver or approach have you used for VRPTW in practice? Share your experience below! 👇

Generated by Constraint Solving — Problem of the Day · ● 180.7K · ◷

• expires on Apr 13, 2026, 12:56 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 #25088.