Results
Vehicle routing best known solutions
The capacitated vehicle routing problem asks for the cheapest set of delivery routes from one depot that visits every customer once without overloading any vehicle. CVRPLIB, kept at PUC-Rio, lists the best known solution for each benchmark instance. Its XL set has 100 instances with 1,000 to 10,000 customers.
We start from the best known solution and improve parts of it at a time: the routes are split into smaller subproblems that HGS-CVRP, Thibaut Vidal's hybrid genetic search, solves again, and every improvement is kept. An independent program checks each final solution: every customer served once, no vehicle over capacity, and the total cost recomputed with CVRPLIB's rounding.
3 sent to its maintainer and 5 waiting for our next batch.
Eight routing solutions
| Entry | Ours | Previous best | Status |
|---|---|---|---|
| XL-n1048-k237 | 380,090 | 380,092 | next batch |
| XL-n1748-k271 | 173,756 | 173,757 | next batch |
| XL-n2074-k264 | 421,225 | 421,227 | next batch |
| XL-n5774-k290 | 249,847 | 249,849 | next batch |
| XL-n6168-k1922 | 1,527,161 | 1,527,163 | sent |
| XL-n8028-k294 | 266,253 | 266,255 | next batch |
| XL-n9784-k2774 | 4,076,853 | 4,076,860 | sent |
| XL-n10001-k1570 | 2,329,785 | 2,329,810 | sent |
Questions
What is CVRPLIB?
The standard library of capacitated vehicle routing benchmarks, with the best known solution for each instance, maintained at PUC-Rio.
How much better are these solutions?
By a few units of cost on instances whose totals run to hundreds of thousands or millions: small, but the listed solutions came from long runs of the best solvers, and every unit is checked.
Were the solutions built from scratch?
No. Each started from the best known solution listed on CVRPLIB and improved it, as is usual for best-known-solution updates.