The 39 open instances of the CVRPLIB X set

The capacitated vehicle routing problem asks for the cheapest set of routes from a depot that delivers every customer's demand without overloading a vehicle. Of the 100 X instances published in 2017, 39 have never been solved to proven optimality, and their best-known solutions were still being improved in October 2026.

Problem

An instance has a depot and customers at integer points in the plane, a demand $d_i$ per customer and a vehicle capacity $Q$; travel costs are Euclidean distances rounded to the nearest integer (TSPLIB EUC_2D). 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 X-n1001-k43, 1001 counts the depot and the customers and 43 is the minimum number of routes. For each instance below, find a solution of lower total cost than the best-known solution (BKS), or prove that the BKS is optimal.

Background

Uchoa, Pecin, Pessoa, Poggi, Vidal and Subramanian (2017) generated the X set: 100 instances with 100 to 1,000 customers that vary the depot position, the customer layout, the demand distribution and the average route length. It became the reference benchmark for exact and heuristic CVRP methods, such as the branch-cut-and-price solver VRPSolver (Pessoa et al., 2020), and was the basis of the CVRP track of the 12th DIMACS Implementation Challenge.

What is known

• 61 X instances have proven optimal solutions; the 39 above do not (CVRPLIB instance table, October 2026). The most recent proofs, for X-n313-k71, X-n359-k29 and X-n384-k52, came from the RouteOpt exact solver of Zhengzhong You and Yu Yang (June 2025).
• CVRPLIB records upper bounds only; it lists no lower bounds for the open instances. Queiroga et al. (2026) write that most of these BKSs are widely believed to be optimal, or within a few units of the optimum.
• Records still fall. The BKS of X-n1001-k43 stood at 72,355 from November 2020 until June 2026 and has since been lowered four times, most recently to 72,334 by Luca Accorsi on 8 October 2026. X-n536-k96 (Yuchen Shi, 13 October 2026) and X-n979-k58 (Martín Vizzolini, 12 October 2026) also improved this month.

What would count as progress

• A solution file in CVRPLIB format (one Route #i: line per route, then the cost) that beats a BKS above. A script checks it in milliseconds: each customer appears once, each route load is at most $Q$, and the rounded cost is recomputed. CVRPLIB also has an online checker.
• A proof that a BKS is optimal, for example a branch-cut-and-price run that closes the gap. CVRPLIB accepts optimality claims only with a citable reference for the method, and this is a separate, harder kind of progress.

References

1. 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
2. A. Pessoa, R. Sadykov, E. Uchoa and F. Vanderbeck (2020). A generic exact solver for vehicle routing and related problems. Mathematical Programming 183, 483–523. https://doi.org/10.1007/s10107-020-01523-z
3. 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

Source

Imported from CVRPLIB, X set, 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.