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