CVRP Competition Updates: View Results & Updates.
CVRP Problem Statement
Among VRP variants, the CVRP is the most central and is the one from which many others derive. Input to the CVRP consists of n locations (a depot and a set of n−1 customers), an n×n symmetric matrix D specifying the distance (or some other cost) 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.
A feasible solution to the CVRP consists of a set of routes that begin and end at the depot, such that each customer is visited on exactly one route and the total demand by the customers assigned to a route does not exceed the vehicle capacity Q. An optimal solution for CVRP is a feasible solution that minimizes the total combined distance of the routes. In the CVRP competition, it will be assumed that there are no restrictions to the number of routes in a solution.
Full Details for the CVRP Challenge
The most complete and up-to-date information for the CVRP competition is contained in the following document:
CVRP Track Details & Rules [Finalized: December 1, 2021]
Information is summarized on this webpage, but the CVRP Track document is the definitive source for complete information. It provides considerably more detail on algorithm evaluation.
CVRP Algorithm Evaluation
CVRP is a well-studied and mature variant, so we aim for the algorithm evaluation to be structured to provide a fair and accurate picture of the current state of the art with respect to both running time and solution quality.
Evaluation will take place in two stages.In Phase One, all testing will be performed on the participant's own computer, which should be running 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 will score 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 resulting output files should be submitted through the Submissions page.
The top-scoring solvers will be invited to proceed to Phase Two which will take place on competition machines. At least five competitors (the finalists) will advance to Phase Two. Finalists will be instructed to install their code on a competition machine, and Phase Two runs will be performed by the organizers. 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.
The competition is open to any person or group, but it will be necessary to register using the button on either the participation page or at the bottom of the main page. Registration entails providing names and affiliations for team members, choosing a competitor ID, and a solver ID. To complete registration for CVRP, it is also necessary to install the Controller on the machines (up to three) where runs will be performed and send a sample output to the organizers. Registration must be completed by December 8, 2021.
The CVRP Controller executable code and all instances are available on github: https://github.com/laser-ufpb/CVRPController. The associated "readme" contains instructions on installation and usage.
CVRP Instances
CVRP is a well-studied variant with many instances appearing in the literature. Recently, a large and diversified set of benchmark instances was proposed in Uchoa et al [UPP+17]. These so-called X-instances were generated by systematically varying attributes like depot positioning (central, eccentric or random), customer positioning (random, clustered, random-clustered), demand distribution (seven possibilities) and average route size (five distinct ranges). The X instance set contains 100 instances, ranging from 100 to 1000 customers. These instances plus additional instances from the literature, as well as several new instances, will be used in CVRP algorithm evaluation.
Phase 1 Instances: All instances can be found in CVRPLIB. The selected CVRP instances are also available on github. Unless stated otherwise, instances use Euclidean distance in two dimensions computed from the node coordinates.
- E-n101-k8 and E-n101-k14 (in set E in CVRPLIB), proposed in Christofides and Eilon [CE69]. Many authors assumed that the number of routes in a solution for those instances should be fixed to 8 and 14, respectively. However, in this competition it will be assumed that no such restriction exists for any instance. For example, solutions for E-n101-k8 having 9 routes will be accepted as feasible.
- CMT4 and CMT5, proposed in Christofides et al. [CMT79], use EUC 2D distances that are not rounded. These are listed under Christofides, Mingozzi, and Toth (1979) but are not in Set M.
- F-n135-k7 (in set F in CVRPLIB), proposed in Fisher [F94].
- P-n101-k4 (in set P in CVRPLIB), proposed in Augerat et al. [ABB+95].
- tai385 proposed in Rochat and Taillard [RT95] uses EUC_2D distances that are not rounded.
- Golden9-Golden20, proposed in Golden et al. [GWKC98], includes 12 instances having from 240 to 480 customers. The EUC_2D distances are not rounded in these instances.
- Antwerp1, Antwerp2, Brussels1, Brussels2, Flanders1, Flanders2, Ghent1, Ghent2, Leuven1, and Leuven2 are 10 very large instances (having from 3,000 to 30,000 customers) proposed in Arnold et al. [AGS19]. These instances are listed under Arnold, Gendreau and Sorensen (2017) in CVRPLIB. We note that some of those instances are so large that only storing the EUC 2D distances as a full matrix may already cause an out-of-memory error in a typical machine. Solvers should avoid doing that for those huge instances.
- X instances [UPP+17] include 100 instances from 100 to 1000 customers as described above. They are listed under Uchoa et al. (2014) in CVRPLIB.
- Loggi instances, kindly contributed by Loggi, were extracted from a large data set of real vehicle routing and facility locations instances in some of Brazil's largest cities—Belém, Brasília, and Rio de Janeiro. The six Loggi instances (in the DIMACS set in CVRPLIB) are Loggi-n401-k23, Loggi-n501-k24, Loggi-n601-k19, Loggi-n601-k42, Loggi-n901-k42, and Loggi-n1001-k31. Each instance name links to an associated map. Distances are explicitly given in the instance files.
- ORTEC instaces, kindly contributed by Wouter Kool of ORTEC, are derived from a real US-based grocery delivery service, with distances corresponding to real driving times (in seconds). The six ORTEC instances (in the DIMACS set in CVRPLIB) are ORTEC-n242-k12, ORTEC-n323-k21, ORTEC-n405-k18, ORTEC-n455-k41, ORTEC-n510-k23, and ORTEC-n701-k64. Distances are explicitly given in the instance files.
In all, there are 141 instances for Phase One. All are available in CVRPLIB.
Phase 2 Instances: Phase Two of the competition will use 100 new instances (unknown to the competitors before the results are presented) statistically similar to the X instances, obtained by the same random generator using a different seed.
New Instances: Two new sets of six instances have been added for Phase One of the Challenge. These instances are derived from real applications and are available in the DIMACS (2021) set in CVRPLIB. These instances were kindly contributed by Loggi and by Wouter Kool of ORTEC.
Input File Format
CVRP instances will given in the TSPLIB95 format, detailed specifications for which are available here. This is the format used in CVRPLIB.
Here is a sample instance with 5 costumers in TSPLIB95 format:
NAME : toy.vrp
COMMENT : toy instance>
TYPE : CVRP
DIMENSION : 6
EDGE_WEIGHT_TYPE : EUC_2D
CAPACITY : 30
NODE_COORD_SECTION
1 38 46
2 59 46
3 96 42
4 47 61
5 26 15
6 66 6
DEMAND_SECTION
1 0
2 16
3 18
4 1
5 13
6 8
DEPOT_SECTION
1
-1
EOF
Output File Format
Solutions should be represented in the CVRPLIB format which partitions the customers among routes. For example, the optimal solution to toy.vrp is:
Route #1: 1 4
Route #2: 3 2 5
Cost 265
Submission
When you are ready to submit either your 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.
CVRP Organizer(s)
Eduardo Uchoa (lead)
References
[AGS19] F. Arnold, M. Gendreau, and K. Sörensen, Efficiently solving very large-scale routing problems, Computers & Operations Research, 107:32–42, 2019.
[ABB+95] P. Augerat, J. Belenguer, E. Benavent, A. Corberán, D. Naddef, and G. Rinaldi., Computational results with a branch and cut code for the capacitated vehicle routing problem, Technical Report 949-M, Université Joseph Fourier, Grenoble, France, 1995.
[B13] T. Berthold, Measuring the impact of primal heuristics, Operations Research Letters, 41(6):611–614, 2013.
[CE69] N. Christofides and S. Eilon, An algorithm for the vehicle-dispatching problem, Journal of the Operational Research Society, 20(3):309–318, 1969.
[CMT79] N. Christofides, A. Mingozzi, and P. Toth, The vehicle routing problem, in N. Christofides, A. Mingozzi, P. Toth, and C. Sandi, editors, Combinatorial Optimization, volume 1, pages 315–338. Wiley Interscience, 1979.
[F94] M. Fisher, Optimal solution of vehicle routing problem using minimum k-trees, Operations Research, 42:626–642, 1994.
[GWKC98] B. Golden, E. Wasil, J. Kelly, and I. Chao, The impact of metaheuristics on solving the vehicle routing problem: algorithms, problem sets, and computational results, in Fleet Management and Logistics, pages 33–56. Springer, 1998.
[RT95] Y. Rochat and É. D. Taillard, Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics, 1(1):147–167, 1995.
[UPP+17] E. Uchoa, D. Pecin, A. Pessoa, M. Poggi, T. Vidal, and A. Subramanian (2017). New benchmark instances for the Capacitated Vehicle Routing Problem. European Journal of Operational Research, 257, 845–858.