Benchmarks

All computations done on a machine using an Intel Xeon E5-1620 CPU @ 3.50GHz, 4c/8t.

CVRP

CVRPLIB

CVRPLIB is a set of benchmark instances for single-depot CVRP. We use all instances described using euclidean distance (EDGE_WEIGHT_TYPE = EUC_2D), from classes A, B, E, F, M, P and X.

All required instances and scripts are available to reproduce results.

Benchmark description

• 189 instances
• Sizes ranging from 15 to 1,000 jobs
• Average size around 240 jobs
• Number of vehicles ranging from 2 to 207
• Average capacity tightness (total job demand / total vehicle capacity): 0.95

Global indicators

Using v1.2.0.

Exploration level	0 (fastest)	5 (best)
Median computing time	87ms	1019ms
Longest computing time	9.1s	254.3s
Jobs assigned	99.67%	99.88%
Solutions with all jobs	162 (85.7%)	171 (90.5%)
Best known solutions	8 (4.2%)	30 (15.9%)

Gaps to best known solutions

Only reported for instances with all jobs assigned, so cost comparison makes sense.

Exploration level	0 (fastest)	5 (best)
Minimum gap	+0.00%	+0.00%
Median gap	+3.95%	+1.35%
Average gap	+4.81%	+2.23%
Worst gap	+21.45%	+12.95%

TSP

TSPLIB

TSPLIB is the reference benchmark for TSP. We use all instances described using euclidean distance (EDGE_WEIGHT_TYPE = EUC_2D).

All required instances and scripts are available to reproduce results.

Benchmark description

• 78 instances
• Sizes ranging from 50 to 18,511 points
• Average size around 1,170 points

Global indicators

Using current master at 4463af7.

• Median computing time: 28 ms
• Average gap to optimal solution: +3.0%
• Worst gap to optimal solution: +7.6%

Examples

Instance	Size	Computing time	Gap
kroA100	100	5 ms	+0.0%
kroB200	200	9 ms	+1.7%
d493	493	48 ms	+3.8%
u1060	1,060	328 ms	+3.0%
u2152	2,152	1610 ms	+4.9%
rl5915	5,915	25.8 s	+2.4%
usa13509	13,509	14 m	+3.0%
d18512	18,512	35 m	+2.9%