Vehicle Routing Problem with Time Windows

The Vehicle Routing Problem with Time Windows extends the CVRP: each customer must be served within a time window, and serving it takes a given service time. A vehicle that arrives early waits until the window opens, and every route must return to the depot before the depot closes. The goal is to minimize the total distance or, in some sets, the number of routes first and then the total distance.

Mathematical Definition

Let $V = \{0, 1, \dots, n\}$ be the set of vertices, where $0$ is the depot and $V_+ = V \setminus \{0\}$ are the customers. Each customer $i$ has a demand $q_i$, a service time $s_i$ and a time window $[a_i, b_i]$; the depot has the window $[a_0, b_0]$ and $s_0 = 0$. Travelling from $i$ to $j$ costs $c_{ij}$ and takes the same time, and the vehicles have capacity $Q$. For a route $r = (0, i_1, \dots, i_p, 0)$ of distinct customers, the service start times are $T_0 = a_0$ and

$$ T_{i_k} = \max\left(a_{i_k},\ T_{i_{k-1}} + s_{i_{k-1}} + c_{i_{k-1} i_k}\right), \qquad k = 1, \dots, p. $$

The route is feasible when $\sum_{k=1}^{p} q_{i_k} \le Q$, $T_{i_k} \le b_{i_k}$ for every $k$, and $T_{i_p} + s_{i_p} + c_{i_p 0} \le b_0$. A solution is a set $R$ of feasible routes in which every customer belongs to exactly one route, and its cost is the total distance of its routes.

Instance sets differ in how $c_{ij}$ is computed and rounded, in how the number of routes $|R|$ is limited, and in the objective: either the total distance alone, or the number of routes first and then the total distance. The table of instance sets below gives the conventions of each set.