VRP Variants

VRP with Time Windows (VRPTW)

The VRPTW is the same problem as the VRP with the additional restriction that a time window is associated with each customer $[a_i, b_i]$ , defining an interval $[a_i, b_i]$ within which the customer has to be supplied. The interval $[a_0, b_0]$ at the depot is called the scheduling horizon.

Formal description

Objective: minimize the vehicle fleet and the sum of the travel time and waiting time needed to supply all customers within their required hours.
Feasibility: with respect to the VRP, the VRPTW is characterized by the following additional restrictions:
- a solution becomes infeasible if a customer is supplied after the upper bound of its time window;
- a vehicle arriving before the lower bound of a time window incurs additional waiting time on the route;
- each route must start and end within the time window associated with the depot;
- in the case of soft time windows, late service does not make the solution infeasible but is penalized by adding a value to the objective function.
Formulation: let $s_k$ denote the beginning of service at customer $k$ . For a route $R_i = (x0, x1, …, x_{m+1})$ to be feasible it must additionally hold that $a_k ≤ s_k ≤ b_k$ , $depot window bound$ and $precedence of service times along the route$ . Provided that a vehicle travels to the next customer as soon as it has finished service at the current one, $s_k$ can be computed recursively as $s_k = max{a_k, s_{k−1} + δ_{k−1} + t_{k−1,k}}$ , with $initial condition$ and $x_0 = 0$ . Thus, a waiting time $w_k = max{0, a_k − arrival_k}$ may be induced at customer $v_k$ .
The cost of route $i$ is now given by $F(R_i) = travel + service + waiting time$ . For a solution $S$ with routes ${R_1, …, R_m}$ , the cost of $S$ is given by $F_VRPTW(S) =$ $M · m$ $+ sum of F(R_i)$ , where M is a large constant. M is added because minimizing the fleet size is considered the primary objective of the VRPTW. $S$ is feasible if all its routes are feasible and each customer is served by exactly one route.

As described by Solomon [Solomon 1995], we assume that initially all vehicles leave the depot at the earliest possible time $a_0$ . Once a solution has been obtained, the depot departure time of each vehicle is adjusted to eliminate any unnecessary waiting time.

The figure below shows a graph representing a VRPTW instance and a solution. The blue and white bars represent the time windows (i.e. business hours), the white area being when a delivery can be made at that customer, while the red line shows when the delivery is actually made in this particular solution.

VRPTW instance and solution: customer time windows shown as bars, actual delivery times as red marks — Figure 1: A VRPTW instance with its time windows and the delivery times of a particular solution.