The XL Instances and the CVRPLib Best Known Solution Challenge

This paper introduces the XL set, a new collection of large-scale benchmark instances for the capacitated vehicle routing problem (CVRP).

The set extends previous benchmarks by covering instances with 1,000 to 10,000 customers and a wide range of structural characteristics, following established generation principles from prior CVRP studies.

To provide strong reference solutions, we conducted an extensive computational study with several state-of-the-art algorithms and retained the best solutions obtained as the starting point for a community-driven BKS challenge hosted on the CVRPLib website.

The XL instances are publicly available to support the experimental evaluation and comparison of future solution methods.

The post-competition results demonstrate the impact of the challenge: over 30 days, participating teams submitted 1,932 BKS improvements, substantially refining the initial solution set and highlighting promising research directions for solving large-scale CVRPs, notably through LLM-assisted algorithm discovery.