VRPTW Best Known Solution Challenge

Introduction

Following the success of the 2026 CVRPLib Best Known Solution Challenge for the Capacitated Vehicle Routing Problem (CVRP), the CVRPLib team announces a new challenge, this time on the Vehicle Routing Problem with Time Windows (VRPTW).

The 2026 CVRP Challenge brought together 19 teams and generated 1,932 improved best known solutions over its 30 days. Beyond substantially improving the solutions available for the XL benchmark, the competition stimulated the development and refinement of new algorithms and provided an arena for comparing classical optimization approaches, hybrid methods, and emerging AI-assisted algorithm design techniques.

The new VRPTW Best Known Solution Challenge will follow the same general philosophy. Its goal is to obtain extremely high-quality solutions for a new set of large-scale VRPTW instances and, at the same time, stimulate the development of new methods for solving vehicle routing problems with thousands of customers.

The XTW and XLTW Sets

The Challenge will be over XLTW, a new benchmark set for the VRPTW, with instances ranging from 1,000 to 10,000 customers. The XLTW instances are closely related to the XL instances introduced for the 2026 CVRP Challenge. They preserve the original depot and customer locations, along with customer demands, while introducing time windows, service times, and a new vehicle capacity.

As with the XL set, the objective is to provide challenging large-scale instances that remain useful for algorithmic research for many years. The official XLTW instances will remain confidential until the beginning of the competition. In the meantime, the XLTW-Test set, containing instances similar to the official ones, is available for algorithm development and testing. XLTW-Test is not an official instance set and will be abandoned once the competition begins.

As an additional release, the XTW set is now part of CVRPLib. These VRPTW instances extend the well-known CVRP X set with time windows. XTW is not part of the Challenge, but the instances are already available with feasible solutions, including a number of proven optimal solutions. The community can already submit improved solutions for them through CVRPLib. The generation procedure is described in the XTW instance-generation document.

Problem Definition and Conventions

Each instance consists of a depot (node 0) and \(n\) customers (nodes \(1, \ldots, n\)). Each customer \(i\) has a demand \(q_i\), a service time \(s_i\), and a time window \([e_i, l_i]\). The depot has \(q_0 = s_0 = 0\) and a time window \([0, H]\), where \(H\) is the scheduling horizon. All vehicles have capacity \(Q\).

Every customer must be visited exactly once by a vehicle route starting and ending at the depot, and the total demand on each route must not exceed \(Q\). Service at customer \(i\) must begin within \([e_i, l_i]\). A vehicle arriving before \(e_i\) must wait until \(e_i\) to start service; starting after \(l_i\) is not allowed. All routes must depart from and return to the depot within \([0, H]\).

As in the X set, distances follow the TSPLIB EUC_2D convention. For any two locations \(i\) and \(j\) with coordinates \((x_i, y_i)\) and \((x_j, y_j)\), the distance is

\(\displaystyle d_{ij} = \left\lfloor \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} + 0.5 \right\rfloor.\)

The total traveled distance is the sum of these individually rounded distances over all routes. Travel times are equal to the corresponding distances.

For a feasible solution \(S\), let \(K(S)\) denote its number of routes and \(D(S)\) its total traveled distance. The objective is

\(\displaystyle \operatorname*{lex\,min}_{S \text{ feasible}} \big(K(S),\, D(S)\big).\)

Thus, fewer routes always take priority over shorter distance; distance breaks ties only between solutions using the same number of vehicles. The number of routes is free and there is no prescribed fleet-size limit, as in the X instances.

The Competition

The competition will follow the basic format of the 2026 CVRPLib BKS Challenge. Everyone except the organizers may compete, including authors of algorithms used to obtain the initial BKSs. If the Challenge website is unavailable, scoring will pause and the competition end time will be extended accordingly.

Before the competition starts, the organizers will perform extensive computational experiments to obtain strong initial Best Known Solutions (BKSs) for all XLTW instances. The official instances will then be released at the start of the Challenge, and participating teams will attempt to improve these initial solutions.

During the competition, teams will be able to submit solutions through the CVRPLib website. Submitted solutions will be automatically checked for feasibility and their objective values will be computed by the platform. For each instance, a real-time leaderboard will record the progression of the BKS and the teams responsible for each improvement.

As in the previous Challenge, the solutions themselves will not be made public while the competition is running, preventing teams from directly improving solutions obtained by other participants. Final solutions will be released after the competition. Teams may use the computational resources and algorithmic strategies of their choice during the BKS competition.

Scoring

The scoring system is the same as in the CVRP BKS Challenge. Each time a team submits an improved BKS, it accumulates lead time (in days) until another team improves the solution or the 30-day competition ends. The team holding the final BKS receives an additional 5-day bonus. The global score is the sum of these scores over all official instances; a team can earn at most 35 days per instance. A team improving its own BKS keeps accumulating lead time without interruption.

For example, the leaderboard for a hypothetical XLTW instance at the end of the competition could look as follows. The BKS value is shown as vehicles; distance:

Team 1 first improves only the distance. Team 2 then reduces the number of routes, establishing a better BKS despite its greater distance, and subsequently improves its own BKS. Team 3 takes the lead, but Team 1 later regains it. At the end (26 March 2027, 15:00 GMT), this instance contributes 7 + 5 + 5 (bonus) = 17 days to Team 1, 4 + 4 = 8 days to Team 2, and 5 days to Team 3. Instances for which the initial BKS is never improved contribute no points.

The team at the top of the Global Leaderboard will be declared the Overall Winner and receive a CVRPLib certificate. Any team obtaining at least one final BKS will also receive a certificate.

Pre-Challenge Algorithm Evaluation

A BKS competition necessarily rewards the ability to find the best possible solutions, and teams may differ substantially in the amount of computing power available to them. This is part of the nature of such a competition, but it makes the final leaderboard an imperfect instrument for comparing the intrinsic quality of algorithms.

In the 2026 CVRP Challenge, the experiments used to produce the initial BKSs already provided an evaluation under comparable computational conditions: publicly available methods were run by the organizers using a common computational environment and experimental protocol.

For the VRPTW Challenge, we will expand this process by making an explicit open call to algorithm developers. Authors who would like their VRPTW algorithms to be considered in the experiments used to establish the initial XLTW BKSs may make their implementations available to the organizers. These submitted implementations will be considered together with other relevant algorithms already publicly available.

Participation in this pre-Challenge evaluation and participation in the BKS competition are independent. A research group may make its algorithm available for the initial BKS experiments without subsequently participating in the competition. Conversely, a team may participate in the BKS competition without having submitted an algorithm for the pre-Challenge evaluation.

After an initial screening to exclude methods that are not competitive with the current state of the art, the selected algorithms will be run by the organizers under the same computational environment, computational budget, and experimental protocol. The submission requirements and execution protocol are listed in the rules and guidelines below.

This evaluation is complementary to, and separate from, the BKS competition itself. Once the competition starts, teams will remain free to use the computational resources and algorithmic strategies of their choice. The Challenge therefore pursues two related but distinct objectives: establishing extremely strong BKSs for the XLTW set and providing meaningful evidence about the performance of algorithms under comparable computational conditions.

Pre-Challenge Algorithm Evaluation: Rules and Guidelines

1. Eligible submissions and documentation. We accept (i) publicly available source code with at least a descriptive README, (ii) private source code or precompiled binaries supported by a published paper or public technical report (e.g., ArXiv or Optimization Online), and (iii) documented commercial software. A short report of results on the XLTW-Test set is mandatory for all submissions. Commercial-software submissions must include a valid license, provided at no cost to the organizers, covering the full evaluation period and allowing multiple independent solver processes to run concurrently. By submitting an algorithm, participants authorize the organizers to publish its computational results and algorithm/software identification.
2. Build and execution environment. Implementations must run on Linux x86-64. For source submissions, building must require only make at the repository root or a supplied build.sh Bash script. Precompiled binaries must be accompanied by all necessary dependencies and clear execution instructions. Programs must run without Internet access or root/sudo privileges. Submissions that cannot be built or executed with minimal effort may be excluded.
3. Preliminary selection. The organizers will assess submitted and other relevant publicly available algorithms and select a limited number of competitive methods for evaluation. The selection criteria, which include performance on the XLTW-Test instances, and the number of selected algorithms are at the organizers' discretion.
4. Execution protocol. Only sequential (single-threaded) execution is permitted. Algorithms found to use parallel execution will be excluded. Each solver execution will be allocated one dedicated logical CPU, exclusively reserved for that execution. The solver must accept exactly three command-line arguments: the path to the instance, the wall-clock time limit in seconds (as a positive real number), and a random seed (as an integer) provided by the organizers. For example:

   ./solver /path/to/instance.vrp 1800.0 1234

   The program should print its solutions to standard output (stdout), using the CVRPLib solution format, for example:

   Route #1: 1 3 5
   Route #2: 2 4 6
   Cost: 4321

   Routes list customer IDs in visit order (excluding the depot); the number of routes gives the number of vehicles, and Cost denotes total distance. In CVRPLib solutions, customers are numbered \(1, \ldots, n\). Each solution must start on a new line. No logs or other text may appear on stdout. Solutions will be independently checked for feasibility and objective value. If the reported cost differs from the cost computed from the routes, the latter prevails. If multiple solutions are printed, only the last complete, feasible solution produced before the time limit will be considered.
5. Time limit. The wall-clock time limit for an instance with \(n\) customers is \(T(n) = 1800\,(n/1000)\) seconds (e.g., 30 minutes per 1,000 customers; 5 hours for 10,000 customers). The wall-clock time limit will be passed to the solver as its second command-line argument and independently enforced by the organizers. At the time limit, the process will receive SIGTERM, followed by SIGKILL after five seconds if still running. The organizers will execute each algorithm 20 times per instance. Each execution must be deterministic for a given seed, which will be randomly selected and provided by the organizers. Each run must start independently, without reusing solutions or other information generated by previous runs.

Timeline

• September 30, 2026 – Initial announcement.
  Publication of the general format, objectives, and timeline of the VRPTW Best Known Solution Challenge.
• October 28 October 31 November 2, 2026 – Detailed rules and technical information released.
  Publication of the rules, XLTW-Test set, and XTW generation document.
• December 16, 2026 – Registration and algorithm submission open.
  Team registration for the BKS competition opens. Submissions of algorithm implementations for consideration in the pre-Challenge computational experiments also open.
• January 16, 2027 – Deadline for algorithm submissions.
  Last day for authors to make their implementations available for consideration in the experiments used to generate the initial XLTW BKSs. A companion report presenting the results on the XLTW-Test instances is mandatory; the organizers will use these results to determine whether the algorithm will be employed.
• February 24, 2027, 15:00 GMT – Challenge begins.
  The official XLTW instances and their initial BKS values are released. Submission of improving solutions opens, and the competition begins.
• March 26, 2027, 15:00 GMT – Challenge ends.
  The competition closes 30 days after the release of the official instances.

Organizers

• Rafael Martinelli (PUC-Rio)
• Eduardo Queiroga (UFBA)
• Anand Subramanian (UFPB)
• Eduardo Uchoa (UFF)
• Igor Malheiros (Sorbonne Université, CNRS, LIP6)