Vehicle Routing with Time Windows

VRPTW · CANONICAL FORMULATION

Logistics · Transportation · Operational

The Vehicle Routing Problem with Time Windows (VRPTW) extends the CVRP with the requirement that service at customer $i$ must begin within a hard time window $[e_i, l_i]$. A vehicle arriving before $e_i$ waits; arrival after $l_i$ makes the route infeasible. Introduced and benchmarked by Solomon (1987), VRPTW is the most widely applied VRP variant in practice — parcel delivery, home healthcare, technician dispatch, grocery e-commerce, and food distribution all live here.

Why VRPTW matters

Three anchor facts

Strongly NP-hard
VRPTW strictly generalises CVRP — even determining feasibility (does a feasible routing exist?) is NP-complete.
Savelsbergh (1985) · doi:10.1016/0377-2217(85)90284-3
56 benchmarks
Solomon's (1987) benchmark set — three geography classes (C/R/RC) × two time-window tightness levels × small variations — remains the standard 35 years later.
Solomon (1987) · doi:10.1287/opre.35.2.254
Primary use case
last-mile delivery and home-service dispatch both map exactly to VRPTW — this is the VRP variant most logistics software actually solves.
Desaulniers, Desrosiers & Solomon (2005).

Mathematical formulation

Three-index MILP · after Desaulniers-Desrosiers-Solomon (2005)

Notation

SymbolMeaning
$V = \{0,1,\ldots,n\}$nodes; $0$ is the depot, $V'$ the customers
$K$set of vehicles, each with capacity $Q$
$c_{ij}, t_{ij}$travel cost and travel time on edge $(i,j)$
$q_i, s_i$demand and service duration at customer $i$
$[e_i, l_i]$time window at customer $i$; $e_0, l_0$ = depot horizon
$x_{ij}^k \in \{0,1\}$1 if vehicle $k$ traverses edge $(i,j)$
$w_i^k$service start time at customer $i$ if visited by vehicle $k$

Objective

Minimise total travel cost
$$\min \; \sum_{k \in K} \sum_{i \in V} \sum_{j \in V,\, j \ne i} c_{ij}\, x_{ij}^k$$

Constraints

(1) Assignment — each customer visited by exactly one vehicle
$$\sum_{k \in K} \sum_{j \in V,\, j \ne i} x_{ij}^k = 1 \quad \forall i \in V'$$
(2) Flow — every vehicle entering visits
$$\sum_{i \in V,\, i \ne h} x_{ih}^k - \sum_{j \in V,\, j \ne h} x_{hj}^k = 0 \quad \forall h \in V',\, k \in K$$
(3) Depot start/end exactly once per vehicle
$$\sum_{j \in V'} x_{0j}^k = 1, \qquad \sum_{i \in V'} x_{i0}^k = 1 \quad \forall k \in K$$
(4) Capacity — per vehicle
$$\sum_{i \in V'} q_i \sum_{j \in V,\, j \ne i} x_{ij}^k \le Q \quad \forall k \in K$$
(5) Time-window linking (big-M, $M = l_0$)
$$x_{ij}^k = 1 \Rightarrow w_j^k \ge w_i^k + s_i + t_{ij}$$ $$\Leftrightarrow \; w_j^k \ge w_i^k + s_i + t_{ij} - M(1 - x_{ij}^k) \quad \forall i,j \in V,\, i \ne j,\, k \in K$$
(6) Time windows
$$e_i \le w_i^k \le l_i \quad \forall i \in V,\, k \in K$$
(7) Binary
$$x_{ij}^k \in \{0,1\}$$

State-of-the-art exact methods use a set-partitioning master with routes as columns and a resource-constrained elementary shortest-path sub-problem priced by bidirectional labelling (Righini & Salani 2006) plus subset-row cuts (Jepsen et al. 2008). The VRPSolver framework (Pessoa et al. 2020) routinely solves Solomon 100-customer instances to optimality.

State-of-the-art heuristics. The Solomon I1 insertion (1987) remains a competitive constructive method; modern metaheuristics are dominated by HGS-VRPTW (Vidal et al. 2013), large-neighbourhood search (Shaw 1998; Pisinger & Røpke 2007), and Solomon Split variants.

Key references

DOIs & permanent URLs

Solomon, M. M. (1987).
“Algorithms for the vehicle routing and scheduling problems with time window constraints.”
Operations Research, 35(2), 254–265. doi:10.1287/opre.35.2.254
Savelsbergh, M. W. P. (1985).
“Local search in routing problems with time windows.”
Annals of Operations Research, 4, 285–305. doi:10.1007/BF02022044
Desrochers, M., Desrosiers, J., & Solomon, M. (1992).
“A new optimization algorithm for the vehicle routing problem with time windows.”
Operations Research, 40(2), 342–354. doi:10.1287/opre.40.2.342
Desaulniers, G., Desrosiers, J., & Solomon, M. M. (Eds.) (2005).
Column Generation.
Springer. doi:10.1007/b135457
Righini, G., & Salani, M. (2006).
“Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints.”
Discrete Optimization, 3(3), 255–273. doi:10.1016/j.disopt.2006.05.007
Jepsen, M., Petersen, B., Spoorendonk, S., & Pisinger, D. (2008).
“Subset-row inequalities applied to the vehicle-routing problem with time windows.”
Operations Research, 56(2), 497–511. doi:10.1287/opre.1070.0449
Pisinger, D., & Røpke, S. (2007).
“A general heuristic for vehicle routing problems.”
Computers & Operations Research, 34(8), 2403–2435. doi:10.1016/j.cor.2005.09.012
Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2013).
“A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows.”
Computers & Operations Research, 40(1), 475–489. doi:10.1016/j.cor.2012.07.018
Pessoa, A., Sadykov, R., Uchoa, E., & Vanderbeck, F. (2020).
“A generic exact solver for vehicle routing and related problems.”
Mathematical Programming, 183, 483–523. doi:10.1007/s10107-020-01523-z
Solomon benchmark instances.
“C1/C2/R1/R2/RC1/RC2 Solomon VRPTW instances.”
Widely hosted mirror: web.cba.neu.edu/~msolomon

Time windows breaking your routes?
Let's talk about moving from constraint-violations to feasibility.

Get in Touch
Data and numerical examples are illustrative. Pages on this site are educational tools, not production software.