315. VRP Time Windows

VRP with Time Windows (VRPTW): each customer specifies a time window during which service must begin.

The most common real-world VRP variant. Models meal delivery, parcel logistics, home services, dialysis transport, etc.

315.1. Formulation additions

On top of CVRP:

Let = service start time at customer , = service duration, = travel time from to .

Time window constraints:

Time propagation:

(If vehicle goes , then is served at least .)

Early arrival waiting is usually allowed: arrive before , wait, then serve at .

315.2. Hard vs soft windows

• Hard windows: strict — infeasibility if violated
• Soft windows: penalty for arriving outside the window, but feasible
• Multiple windows: a customer has several acceptable service intervals

Soft windows are easier to solve (relaxes infeasibility); hard windows model real commitments.

315.3. Why VRPTW is much harder than CVRP

• Tighter feasibility: many tours that fit capacity violate time windows
• Sequence-dependent feasibility: may be infeasible even if each pair and is feasible alone
• Larger LP relaxations: more constraints, more weakening of bounds
• Column generation (the standard exact method) needs Resource-Constrained Shortest Path sub-problems — themselves NP-hard

315.4. Solution methods

Constructive:

• Solomon’s insertion heuristic (I1): build routes by inserting customers based on a parameterized “insertion cost”
• Time-oriented nearest neighbor

Improvement:

• 2-opt-star: 2-opt that respects time windows
• Or-opt: move chains of 1-3 customers
• Cross-exchange: swap segments between routes

Metaheuristics:

• ALNS (Adaptive Large Neighborhood Search) — typically best in benchmarks
• Tabu search

Exact:

• Branch-and-price-and-cut with elementary RCSP sub-problems
• Solomon benchmark instances (): solved to optimality

315.5. Applications

• Food delivery (DoorDash, Uber Eats): tight 30-60 min windows
• Parcel last-mile (FedEx, UPS): standard 9-5 windows, dense urban routing
• Healthcare logistics: dialysis pickup, home nursing
• Cash-in-transit: armored car pickups
• Field service (HVAC, telecom): morning / afternoon appointment windows

315.6. See also

• VRP — without time windows
• TSP — single-vehicle ancestor
• Clarke-Wright — initial routes