VRP with Time Windows


VRPTW Problem Statement

The Vehicle Routing Problem with Time Windows (VRPTW) is a more constrained variant of the CVRP in which each customer requires delivery within a specified interval of time called its "time window".

Like CVRP, input to VRPTW consists of n locations (a depot and a set of n−1 customers), a matrix D specifying the time to travel between each pair of locations, a quantity qi that specifies the demand for some resource by each customer i, and the maximum quantity, Q, of the resource that a vehicle can carry. In addition, each node i is specified with a length of time si denoting the time it takes to serve customer i and a time window [ti, Ti], where ti < Ti, within which delivery must occur. A vehicle is allowed to arrive at a customer location before the beginning of the time window, but it must wait for the window to "open" to make the delivery. A delivery cannot be made after the time window closes. In this way, the Implementation Challenge considers the time-window constraints to be hard constraints. Finally, there is a limit V on the number of available vehicles.

A feasible solution to VRPTW consists of a set of V or fewer routes that begin and end at the depot, such that each customer is visited on exactly one route within its specified time window and the total demand assigned to a route does not exceed the vehicle capacity Q

An optimal solution for VRPTW is a feasible solution that minimizes the total combined distance of all routes.

VRPTW Algorithm Evaluation

Detailed information and rules for the VRPTW track competition will be posted soon.

Competition rules for this track will be modeled on those of the CVRP track. It will involve a Controller executable code that is run the competitor's solver in the first phase and a second phase for top competitors that is run on a competition machine with different instances.

VRPTW Instances

Algorithm evaluation will be conducted using two classic sets of instances:

  • The 56 classic instances of Solomon [Sol87], each containing 100 customers.
  • The 300 instances of Gehring and Homberger [GH02] ranging from 200 to 1,000 customers.

Download the zipped VRPTW instances.

We welcome contribution of new instances for use in the competition, particularly those derived from real applications. If you have instances you would like to contribute, please contact the organizers.

Input File Format

Instances for VRPTW are given in what has become the de facto standard for this variant. Each instance is in a separate file. The files adhere to the following conventions.

Line 1: Name of the instance.

Line 5: V   Q,  where V is the number of vehicles and Q is the vehicle capacity.

Lines 10 and beyond each contain the following six parameters corresponding to the depot (in line 10) and customer locations (in line 11 and beyond): InputFormat.JPG

  • node number
  • x coordinate
  • y coordinate
  • demand, qi
  • time window opening, ti
  • time window closing, Ti
  • service time, si

The beginning portion of the input file for the R108 Solomon instance is shown as an example.

The travel time dij on a link is taken to be the Euclidean rounded to 1 decimal place.

Output File Format

The output file format will be the same as for the CVRP, consisting of a the list of routes in the solution followed by its objective value. As an example, of the specific formatting, below is the output associated with a solution of instance R108.

Route #1: 53
Route #2: 70  30  20  66  65  71  35  34  78  77  28
Route #3: 92  98  91  44  14  38  86  16  61  85 100  37
Route #4: 2  57  15  43  42  87  97  95  94  13  58
Route #5: 73  22  41  23  67  39  56  75  74  72  21  40
Route #6: 52  88  62  19  11  64  63  90  32  10  31
Route #7: 6  96  59  99  93  5  84  17  45  83  60  89
Route #8: 26  12  80  68  29  24  55  4  25  54
Route #9: 27  69  76  3  79  9  51  81  33  50  1
Route #10: 7 18  82  8  46  36  49  47  48
Cost 940.3

VRPTW Organizer(s)

Eduardo Uchoa (lead)

Questions

If you have questions, please email the organizers using this link.

References

[GH02] H. Gehring and J. Homberger, "Parallelization of a two-phase metaheuristic for routing problems with time windows," Journal of Heuristics, 8, pp. 251-276, 2002.

[Sol87] M. M. Solomon, "Algorithms for the vehicle routing and scheduling problems with time window constraints," Operations Research, 35(2), pp. 254-265, 1987.