Benchmarks

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

VRPTW

Solomon

The Solomon benchmark is used as a reference in most research papers including time window constraints.

All required instances and scripts are available to reproduce results.

Benchmark description

56 instances with 100 jobs, grouped in classes C (clustered), R (random), RC (mix of both), and 1 or 2 for short or long planning horizon.

Global indicators

Using v1.6.0 with -x 5 and comparing to best known solutions targeting cumulated travel time (more on objectives).

Computing times	(ms)
Average	456
Median	539
Longest	652

Quality
Best known solutions	13 (23.2%)
Minimum gap	+0.00%
Median gap	+1.11%
Average gap	+1.75%
Worst gap	+8.61%

Results by problem class

Comparison to best known solutions (BKS) targeting cumulated travel time (CTT). Cumulated number of vehicles (CNV) is only reported for the record.

Class	C1	C2	R1	R2	RC1	RC2	Total
BKS CNV	10.0	3.0	13.25	5.36	12.88	6.25	485
BKS CTT	828.38	589.86	1175.75	878.41	1340.02	1004.21	54,699
VROOM CNV	10.0	3.0	13.33	4.36	13.13	5.25	469
VROOM CTT	828.38	589.86	1190.03	911.56	1359.48	1038.89	55,668
CTT gap	+0.00%	+0.00%	+1.21%	+3.77%	+1.45%	+3.45%	+1.77

PDPTW

Li & Lim

The Li & Lim 100 benchmark is derived from the Solomon instances with the addition of pickup and delivery constraints.

All required instances and scripts are available to reproduce results.

Benchmark description

56 instances with around 100 jobs, grouped in classes C (clustered), R (random), RC (mix of both), and 1 or 2 for short or long planning horizon.

Global indicators

Using v1.6.0 with -x 5.

Computing times

Computing times	(ms)
Average	256
Median	256
Longest	422

Quality

We target cumulated travel time (CTT), but best known results are only reported for approaches using the number of vehicles as the first optimization objective. For a meaningful comparison we rule out instances lc103, lc104, lc109 andlr211 for which we provide solutions that are better in term of CTT but use one more vehicle than the reported "best known solution".

CTT comparison
Best known solutions	24 (46.2%)
Minimum gap	+0.00%
Median gap	+0.09%
Average gap	+1.22%
Worst gap	+9.86%

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

Exploration level	0 (fastest)	5 (best)
Median computing time	41ms	754ms
Longest computing time	2.3s	230.2s
Jobs assigned	99.5%	99.9%
Solutions with all jobs	160 (84.7%)	168 (88.9%)
Best known solutions	14 (7.4%)	41 (21.7%)

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.81%	+0.97%
Average gap	+3.24%	+1.69%
Worst gap	+16.41%	+10.01%

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

• Median computing time: 36 ms
• Average gap to optimal solution: +2.79%
• Worst gap to optimal solution: +6.37%

Examples

Instance	Size	Computing time	Gap
kroA100	100	5ms	+0.0%
a280	280	16ms	+1.12%
d657	657	98ms	+3.96%
u1060	1,060	288ms	+2.47%
u2152	2,152	1706ms	+4.36%
rl5915	5,915	25s	+2.14%
usa13509	13,509	14m5s	+3.13%
d18512	18,512	34m40s	+2.99%