VRP with Time Windows (VRPTW)

The VRPTW is the same problem that VRP with the additional restriction that in VRPTW a time window is associated with each customer , defining an interval wherein the customer has to be supplied. The interval 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 denote the beginning of service at customer . Now for a route to be feasible it must additionally hold , , and . Provided that a vehicle travels to the next customer as soon as it has finished service at the current customer, can be recursively computed as with and . Thus, a waiting time may be induced at customer . The cost of route is now given by . For a solution with routes , the cost of is given by , 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. is said to be feasible if all routes belonging to 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 . Having obtained a solution of the VRPTW, we adjust the depot departure time of each vehicle to eliminate any unnecessary waiting time.

In the figure below we can see a graph representing an instance for solving with VRPTW. There, blue and white bars are representing the time window (i.e. business hours), where white area represents when we can make a delivery at that customer. By other side, the red line shows when is the delivery made for this particular solution.