The XL set: vehicle routing with 1,000 to 10,000 customers

In January 2026 CVRPLIB released 100 new instances of the capacitated vehicle routing problem with 1,000 to 10,000 customers, together with a 30-day community challenge to find the best possible solutions. None of them is solved, and their best-known solutions are still being lowered.

Problem

Each instance has a depot and up to 10,000 customers at integer points of the square $[0,1000]^2$, a demand $d_i$ per customer and a vehicle capacity $Q$. Travel costs are Euclidean distances rounded to the nearest integer. A solution is a set of routes that start and end at the depot, visit every customer exactly once in total and carry at most $Q$ each; the number of routes is free. In a name such as XL-n5067-k201, 5067 counts the depot and the customers and 201 is the minimum number of routes. For each of the 100 instances, find a solution cheaper than the best-known solution (BKS) listed by CVRPLIB.

Background

Queiroga, Martinelli, Subramanian, Uchoa and Vidal (2026) generated the XL set with the same scheme as the X set of Uchoa et al. (2017), varying depot position, customer layout, demand distribution and route length. To obtain starting values they ran five published heuristics (KGLS-XXL, SISRs, FILO and FILO2, HGS-CVRP with decomposition, and AILS-II) 60 times for two hours on each instance; AILS-II produced 93 of the 100 initial BKSs. The CVRPLib BKS Challenge then ran from 12 January 2026 for 30 days: 19 teams took part, 1,932 improved solutions were submitted, and the winning team, OptVerse-CityU, ran a portfolio of AILS-II variants with HGS-CVRP and FILO2 for about 42,600 CPU-days.

What is known

• All 100 instances are open. CVRPLIB lists BKSs but no lower bounds, and the organisers describe the XL instances as beyond the reach of current exact methods.
• During the challenge XL-n8389-k2028 received 74 BKS updates, while XL-n1094-k157 received none: its initial AILS-II value of 112,431 still stands.
• Records keep falling after the challenge. On 11 September 2026 a Baidu team (Qianlong Wang and four colleagues) improved 70 XL instances at once, and in October 2026 Shiyao Bian and Martín Vizzolini lowered several more, including XL-n10001-k1570 to 2,330,257.

What would count as progress

• A solution file in CVRPLIB format (one Route #i: line per route, then the cost) that beats a BKS. A script checks it in seconds: each customer appears exactly once, each route load is at most $Q$, and the rounded Euclidean cost is recomputed. CVRPLIB also runs an online checker and publishes improvements on its updates page.
• A certified lower bound for any XL instance, which would measure for the first time how far its BKS can be from optimal; proving a BKS optimal is a separate and much harder kind of progress.

References

1. E. Queiroga, R. Martinelli, A. Subramanian, E. Uchoa and T. Vidal (2026). The XL instances and the CVRPLib Best Known Solution Challenge. arXiv:2601.11467. https://arxiv.org/abs/2601.11467
2. E. Uchoa, D. Pecin, A. Pessoa, M. Poggi, T. Vidal and A. Subramanian (2017). New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research 257, 845–858. https://doi.org/10.1016/j.ejor.2016.08.012
3. V. R. Máximo, J.-F. Cordeau and M. C. V. Nascimento (2024). AILS-II: an adaptive iterated local search heuristic for the large-scale capacitated vehicle routing problem. INFORMS Journal on Computing 36, 974–986. https://doi.org/10.1287/ijoc.2023.0106
4. L. Accorsi and D. Vigo (2024). Routing one million customers in a handful of minutes. Computers & Operations Research 164, 106562. https://doi.org/10.1016/j.cor.2024.106562
5. F. Arnold, M. Gendreau and K. Sörensen (2019). Efficiently solving very large-scale routing problems. Computers & Operations Research 107, 32–42. https://doi.org/10.1016/j.cor.2019.03.006

Source

Imported from CVRPLIB, XL set and BKS Challenge, curated by CVRPLIB maintainers (PUC-Rio). Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.