-
Notifications
You must be signed in to change notification settings - Fork 340
Benchmarks
All computations done on a machine using an Intel Xeon E5-1620 CPU @ 3.50GHz, 4c/8t.
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.
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.
Using v1.5.0 with -x 5 and comparing to best known solutions targeting cumulated travel time (more on objectives).
| Computing times | (ms) |
|---|---|
| Average | 431 |
| Median | 493 |
| Longest | 605 |
| Quality | |
|---|---|
| Best known solutions | 13 (23.2%) |
| Minimum gap | +0.00% |
| Median gap | +1.11% |
| Average gap | +1.77% |
| Worst gap | +7.77% |
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.42 | 4.18 | 13.13 | 5.38 | 469 |
| VROOM CTT | 828.38 | 589.86 | 1190.24 | 911.17 | 1360.03 | 1039.80 | 55,678 |
| CTT gap | +0.00% | +0.00% | +1.23% | +3.73% | +1.49% | +3.54% | +1.79 |
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.
- 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
Using v1.5.0.
| Exploration level | 0 (fastest) | 5 (best) |
|---|---|---|
| Median computing time | 35ms | 696ms |
| Longest computing time | 2.6s | 167.2s |
| Jobs assigned | 99.54% | 99.85% |
| Solutions with all jobs | 159 (84.1%) | 168 (88.9%) |
| Best known solutions | 13 (6.9%) | 42 (22.2%) |
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.95% | +1.02% |
| Average gap | +3.17% | +1.67% |
| Worst gap | +14.19% | +10.04% |
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.
- 78 instances
- Sizes ranging from 50 to 18,511 points
- Average size around 1,170 points
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%
| 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% |