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 [last updated: May 10, 2021]

Information is summarized on this webpage, but the CVRP Track document is the definitive source for complete information.

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. Evaluation will take place in two stages. In Phase 1, 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 five top-scoring solvers will be invited to proceed to Phase 2 which will take place on competition machines.

The competition is open to any person or group, but it will be necessary to register. (Details on registration will be posted here when they are available.)

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 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. All 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. 

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.

Contributing New Instances: Although we do not necessarily need additional CVRP instances, we welcome contribution of interesting instances, particularly those derived from real applications. If you have instances you would like to contribute, please contact the organizers. A few additional contributed instances may be added before the next stage of the Challenge begins. If so, those instances will also be available at CVRPLIB.

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

CVRP Organizer(s)

Eduardo Uchoa (lead)

Questions

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

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.