VRPTW Competion Updates: View Results & Updates.
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 distance (which will also be 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 begin. 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 begin 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. Note that the competition adopts the convention of minimizing only the total distance. Thus, a solution must respect the constraint on the maximum number of vehicles, V, but there is no bonus for using fewer vehicles.
Full Details for the VRPTW Challenge
The most complete and up-to-date information for the VRPTW competition is contained in the following document:
VRPTW Track Details & Rules [Finalized: December 1, 2021]
Information is summarized on this webpage, but the VRPTW Track document is the definitive source for complete information. It provides considerably more detail on algorithm evaluation.
VRPTW Algorithm Evaluation
Evaluation will take place in two stages. In Phase One, all testing will be performed on the participant's own computer, under a Unix/Linux OS. The organizers will provide a Controller executable code that will run the competitor's solver. The Controller will read each solution (through a Unix pipeline), check its feasibility, and record the corresponding elapsed time. The Controller will kill the job when the solver's time limit is reached, and it scores the solver's performance on each instance using the “primal integral” of Berthold [B13]. The primal integral folds in both solution quality and timing to assign a single “score” for the instance. The score enables competitors to be ranked on each instance and then these ranks can produce an overall score for the competition.
The top-scoring solvers will be invited to proceed to Phase Two which will be run by the organizers on a competition machine with different instances. At least three competitors (the finalists) will advance to Phase Two. Finalists will be invited to present at the concluding workshop, provided that their solver is adequately described in an associated extended abstract. (Failure to provide this document will result in disqualification.) Phase Two results will be revealed at the workshop.
Participation is open to any person or group, but each group/solver is required to register in advance.
VRPTW Instances
Algorithm evaluation will be conducted using two classic sets of instances:
- The 56 instances of Solomon [Sol87], each containing 100 customers.
- The 300 instances of Homberger and Gehring [HG99] ranging from 200 to 1,000 customers.
The VRPTW Controller executable code and all instances are available on github: https://github.com/laser-ufpb/ VRPTWController/archive/refs/heads/master.zip. The associated "README" contains instructions on installation and usage.
The Solomon and Hombeger-Gehring instances are used extensively in the VRPTW literature. Yet, different conventions are found, making direct comparisons harder. The competition will adopt the following two conventions:
- The objective is to minimize only the total distance (as noted in the Problem Statement).
- The matrix D of inter-node distances (which are also the travel times) is the Euclidean distance obtained from the location coordinates and then truncated to one decimal place.
Phase Two of the competition will use 300 new instances (unknown to the competitors before the results are presented), that will be obtained from the Hombeger-Gehring instances by only changing the coordinates of the depot. The new depot location will be random, but subject to the constraint that the resulting instance is feasible.
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): 
- 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 truncated to 1 decimal place.
Output File Format
The output file format will be the same as for the CVRP, consisting of a list of the routes in the solution (numbered sequentially) 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
Submission
When you are ready to submit either your solver output package (a zipped file) or your Challenge paper, you may do so from the Submissions page (which is part of the navigation menu on the right-hand side of this page).
Outputs are due January 16, 2022 and must be received by 23:59 Pacific Standard Time (UTC -8).
Questions
If you have questions, please email the organizers using this link.
Acknowledgements
Several people have provided valuable assistance during algorithm evaluation. We thank Bruno Passeti (Universidade Federal da Paraíba), Eduardo Queiroga (INRIA Bordeaux), and Rodrigo Ramalho (Universidade Federal da Paraíba) for their work on the Controller used in Phase One testing. We thank João Marcos Silva (Universidade Federal Fluminense) for his work in analyzing results and Walter Morris (DIMACS) for setting up machines for Phase Two testing.
VRPTW Organizer(s)
Eduardo Uchoa (lead)
References
[B13] T. Berthold, Measuring the impact of primal heuristics, Operations Research Letters, 41(6):611–614, 2013.
[HG99] J. Homberger and H. Gehring, "Two evolutionary metaheuristics for the vehicle routing problem with time windows," INFOR: Information Systems and Operational Research, 37(3):297–318, 1999.
[Sol87] M. M. Solomon, "Algorithms for the vehicle routing and scheduling problems with time window constraints," Operations Research, 35(2):254–265, 1987.