VRP with Time Windows

The VRPTW is the same problem that VRP with the additional restriction that in VRPTW a time window is associated with each customer ${v \in V}$, defining an interval ${\left[ e_{0}, l_{0} \right]}$ wherein the customer has to be supplied. The interval ${\left[ e_{0}, l_{0} \right]}$ at the depot is called the scheduling horizon. Here is a formal description of the problem:

Objective

The objective is to minimize the vehicle fleet and the sum of travel time and waiting time needed to supply all customers in their required hours.

Feasibility

The VRPTW is, regarding to VRP, 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 limit of the time window causes 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 widows, a later service does not affect the feasibility of the solution, but is penalized by adding a value to the objective function.

Formulation

Let ${b_{0}}$ denote the beginning of service at customer ${v}$. Now for a route ${R_{i} = (v_{0}, v_{1}, …, v_{m}, v_{m+1})}$ to be feasible it must additionally hold ${e_{v_{i}} \leq b_{v_{i}} \leq l_{v_{i}}}$, ${1 \leq i \leq m}$, and ${b_{v_{m}} + \delta_{v_{m}} + c{v_{m,0}} \leq l_{0}}$. Provided that a vehicle travels to the next customer as soon as it has finished service at the current customer, ${b_{v_{i}}}$ can be recursively computed as ${b_{v_{i}} = \max{(e_{v_{i}},b_{v_{i-1}}+\delta_{v_{i-1}}+c_{v_{i-1},v_{i}})}}$ with ${b_{0} = e_{0}}$ and ${\delta_{0} = 0}$. Thus, a waiting time ${w_{v_{i}} = \max{(0,b_{v_{i}}-b_{v_{i-1}}-\delta_{v_{i}}-c_{i-1,i})}}$ may be induced at customer ${v_{i}}$. The cost of route ${i}$ is now given by ${C_{VRPTW}(R_{i}) = \sum_{i=0}^{m} c_{i,i+1} + \sum_{i=1}^{m} \delta_{i} + \sum_{i=0}^{m} w_{v_{i}}}$. For a solution ${S}$ with routes ${R_{1}, …, R_{m}}$, the cost of ${S}$ is given by ${F_{VRPTW}(S) = \sum_{i=1}^{m}(C_{VRPTW}(R_{i})+M}$, where ${M}$ is a large constant. ${M}$ is added because minimization of the fleet size is considered to be the primary objective of the VRPTW. ${S}$ is said to be feasible if all routes belonging to ${S}$ are feasible and its 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 ${e_{0}}$. Having obtained a solution of the VRPTW, we adjust the depot departure time of each vehicle to eliminate any unnecessary waiting time.