CVRP Challenge
CVRP Challenge for Exact Methods
In order to further motivate the research on exact methods for the CVRP we are offering two prizes for solving instances of the new benchmark proposed in Uchoa et al. (2017):
500-Customer Prize - A certificate and 300 US dollars for the first person or group who can solve to proven optimality the 68 instances in the X series with up to 500 customers.
1000-Customer Prize - A certificate and 500 US dollars for the first person or group who can solve to proven optimality all the 100 instances in the X series, with up to 1000 customers.
Rules:
1. Priority claims by competing groups will be resolved by the date of the online publication of a research report fully describing the method and presenting detailed computational results. Conference presentations will not be considered. The research report should be published at a well-known web repository, like Optimization Online, arXiv, or similar. However, the prize will only be granted after the corresponding article is peer-reviewed and accepted for publication in a major operations research journal.
2. The method should be able to solve all the required instances (68 for the 500-Customer and 100 for the 1000-Customer prizes). It is not enough to solve the last instances never solved by other authors. However, the method can combine any number of basic techniques, as long as it automatically decides what strategy to follow in each instance. For an example, consider the method in Fukasawa et al. (2006). It could solve all instances from the literature with up to 134 customers. On most instances, it performed as a branch-cut-and-price algorithm. However, when it detected that column generation was not working well, it automatically shifted to a branch-and-cut algorithm.
3. In recent years, the performance gains of a single CPU core were quite limited. Instead, manufacturers are investing in many-core architectures. Moreover, distributed cloud computing technologies hold promise of offering affordable large-scale parallelism in the near term. Since we believe that future optimization algorithms should be able to harness all that potential computing power, there are no restrictions on the use of parallelism in the challenge.
We are not expecting (but really would love) to grant those prizes soon. Let us see what happened with other proposed benchmark sets:
- Eilon and Christofides CVRP instances (up to 100 customers): proposed in 1969, all instances solved in 2003 - 34 years later.
- Christofides, Mingozzi and Toth CVRP instances (up to 199 customers): proposed in 1979, all instances solved in 2013 - 34 years later.
- Solomon VRPTW instances (up to 100 customers): proposed in 1986, all instances solved in 2012 - 26 years later.
- Golden et al. CVRP instances (up to 483 customers): proposed in 1998, 8 out of 12 instances remain open.
The current state of the X instances is the following. According to the article that introduces them, 38 instances with less than 500 customers were already solved, 30 instances in that range remain open. Only 2 instances with more than 500 customers were solved, 30 instances in that range remain open.
Eduardo Uchoa
Marcus Poggi
Rio de Janeiro, October, 16th 2014.
