-
Notifications
You must be signed in to change notification settings - Fork 346
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.3.0-rc.2 with -x 5 and comparing to best known solutions targeting cumulated travel time (more on objectives).
| Computing times | (ms) |
|---|---|
| Average | 827 |
| Median | 873 |
| Longest | 1467 |
| 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.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%) |
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% |
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 master at 4463af7.
- Median computing time: 28 ms
- Average gap to optimal solution: +3.0%
- Worst gap to optimal solution: +7.6%
| 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% |