Vehicle routing
XL-n9784-k2774
A solution of the CVRPLIB instance XL-n9784-k2774 with total cost 4,076,853, below the 4,076,860 listed as best known on CVRPLIB on 25 October 2026. Quantavane found it on 25 October 2026.
Sent to CVRPLIB's maintainers on 25 October 2026.
The record
| Ours | cost 4,076,853 |
|---|---|
| Previous best | cost 4,076,860 |
| Previous source | the best known solution listed on CVRPLIB (read 25 October 2026) |
| Found | 25 October 2026 |
| Status | Sent to CVRPLIB's maintainers on 25 October 2026. |
| Check | An independent program checked every route, the capacities and the total cost with CVRPLIB's rounding. |
XL-n9784-k2774 has 9,783 customers; every one is served once from the depot, no vehicle carries more than its capacity, and the routes cost 7 less in total.
How it was found and checked
Started from the best known solution and improved by splitting the routes into smaller subproblems that HGS-CVRP solves again, keeping every gain. An independent program checked every route, the capacities and the total cost with CVRPLIB's rounding.
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.
Questions
What is the best known solution for XL-n9784-k2774?
Ours, with cost 4,076,853; CVRPLIB listed 4,076,860 on 25 October 2026.
How was it found?
By improving the listed best solution with decomposition and HGS-CVRP.
Is it on CVRPLIB yet?
Sent to CVRPLIB's maintainers on 25 October 2026.