VRP Time Windows

318. 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.

On top of CVRP:

Let $𝑡_{𝑖}$ = service start time at customer $𝑖$ , $𝑠_{𝑖}$ = service duration, $𝑡_{𝑖 𝑗}$ = travel time from $𝑖$ to $𝑗$ .

Time window constraints:

𝑎_{𝑖} \leq 𝑡_{𝑖} \leq 𝑏_{𝑖}, \forall 𝑖

Time propagation:

𝑡_{𝑗} \geq 𝑡_{𝑖} + 𝑠_{𝑖} + 𝑡_{𝑖 𝑗} - 𝑀 (1 - 𝑥_{𝑖 𝑗 𝑘})

(If vehicle $𝑘$ goes $𝑖 \to 𝑗$ , then $𝑗$ is served at least $𝑡_{𝑖} + 𝑠_{𝑖} + 𝑡_{𝑖 𝑗}$ .)

Early arrival waiting is usually allowed: arrive before $𝑎_{𝑖}$ , wait, then serve at $𝑎_{𝑖}$ .

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

Tighter feasibility: many tours that fit capacity violate time windows
Sequence-dependent feasibility: $𝑖 \to 𝑗 \to 𝑘$ may be infeasible even if each pair $𝑖 \to 𝑗$ and $𝑗 \to 𝑘$ 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

Constructive:

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

Improvement:

Metaheuristics:

Exact: