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.3.0-rc.2.

Exploration level	0 (fastest)	5 (best)
Median computing time	31ms	569ms
Longest computing time	1.9s	95.8s
Jobs assigned	99.57%	99.86%
Solutions with all jobs	158 (83.6%)	171 (90.5%)
Best known solutions	14 (7.4%)	42 (22.2%)

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	+2.80%	+0.89%
Average gap	+3.24%	+1.73%
Worst gap	+19.07%	+10.08%

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 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%