The initial version of this benchmark was written by Vít Knobloch.
Data files were downloaded from CVRPLIB. Set XML was omitted because it is too large. Currently, the benchmark is not able to parse sets D and E (for the same reason as some TSP benchmarks).
Knows solutions (also from CVRPLIB) can be found in the directory known-solutions. Note that the node numbers in the solution files are shifted by 1. In the input files, node one is the depot. In the solution files, node one does not appear at all (it is implicitly the first and last node of every route). Instead, node one in the solution file is node two from the input file.
Thibaut Vidal: Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood
--nbVehicles <number> Number of vehicles
--objective <makespan|path> Objective function
--checkTriangularInequality Warn if triangular inequality is not respected
--visitDuration <number> Duration of each visit (the default is 0)
--forceCeil Round up during distance computation
--checkDirectionSymmetry Warn if the directions are not symmetrical
--breakDirectionSymmetry Break the direction symmetry of the solution
--breakVehicleSymmetry Order vehicles by the maximum city visited
See below for more details.
The number of vehicles is not given in the input files, but often, it is part of the instance name after k. For example, instance A-n32-k5.vrp has five vehicles. By default, the benchmark tries to decode the number of vehicles from the file name. The command line parameter --nbVehicles can directly set the number of vehicles.
Many benchmark instances do not fulfill triangular inequality due to rounding errors (distances computed by EUC_2D). It causes the same issues as in
TSP benchmark, see more details there. Therefore, the CVRP benchmark also supports command-line options
--checkTriangularInequality, --visitDuration, and --forceCeil from the TSP benchmark.
Known optimal solutions are using rounding errors to get to some nodes faster. Let us consider the instance A-n32-k5. The optimal solution is using the following two shortcuts (node numbers are shifted by 1 as usual in the solutions):
31 -> 19 -> 17: 5 + 2 < 8
16 -> 30 -> 0: 9 + 16 < 26
Here are the results of OptalCP with different options to compensate for the triangular inequality:
- Without
--forceCeiland without--visitDuration, the optimal solution is found. However, its length is computed as 786. - With
--forceCeil, OptalCP says that the optimal length is 807. - With
--visitDuration 1, the optimal solution is found, and its length is 784.
The default objective is to minimize the total length of the routes. However, there is also an option --objective makespan to minimize the length of the longest route. In this case, we compute when the last vehicle returns to the depot.
Note that the makespan objective includes the lengths of the visits as given by --visitDuration. In contrast, the default objective "path" deduces the visits' durations from the routes' total durations.
CVRP is a highly symmetrical problem. There are two main symmetries: direction symmetry and route order symmetry.
Symmetry breaking implemented in the benchmark is partially inspired by the following paper:
Maryam Darvish, Leandro C. Coelho, Raf Jans: Comparison of Symmetry Breaking and Input Ordering Techniques for Routing Problems
In general, symmetry breaking is helpful for FDS search but may slow down LNS search.
In the input files, all the transition matrixes are symmetrical (could be checked by --checkDirectionSymmetry), as described in TSP benchmark. Therefore, reversing the order of nodes in a route leads to the equivalent solution. To break it, use the command-line parameter --breakDirectionSymmetry.
Changing the order of the vehicles/routes also leads to an equivalent solution. To break it, use the command-line parameter --breakVehicleSymmetry.