The 12th Implementation Challenge is dedicated to the study of Vehicle Routing problems (broadly defined), bringing together research in both theory and practice. The over-arching purpose of a Challenge is to assess the practical performance of algorithms for a particular problem class, while fostering interactions that transfer ideas between researchers in areas that span algorithms, data structures, implementation, and applications. This rendition of the Challenge is part of the DIMACS Special Focus on Bridging Continuous and Discrete Optimization and will be capped by a workshop hosted by DIMACS at Rutgers University. The event has been postponed because of COVID-19 and is now planned for April 6-8, 2022. This Challenge is being held in honor of David S. Johnson, and the workshop will include activities dedicated to him and his many contributions to the study of algorithms.
Problems Addressed
The Vehicle Routing Problem (VRP) and other related dispatch problems have been widely studied for over fifty years because they are of both practical relevance and theoretical interest. Designing efficient routes for vehicles performing distribution or service functions translates directly to cost savings, making vehicle routing a topic of great commercial interest. Moreover, the fact that it generalizes the Traveling Salesman Problem, but is substantially more difficult, has kept it in the sights of theoreticians for decades. The VRP exists in a myriad of variations that arise from practical considerations like vehicle capacities, delivery time windows, delays in road networks, and the ability to split deliveries.
Because of the expansive problem space, this Challenge will consider multiple VRP variants, representing a mix of classic VRP variants and newer variants inspired by practical considerations. These include some of the most challenging of the VRP family. These problems focus on features that are critical to bridging the gap between application and practice, but they lead to different structural characteristics favoring different solution approaches.
The VRP variants currently included in the Challenge are:
1) Capacitated VRP
2) Capacitated VRP with Time Windows
3) Inventory Routing Problem
4) VRP with Split Deliveries
5) Electric Vehicle Routing
6) Capacitated Arc Routing
7) Time-depandent Capacitated Arc Routing
8) Dynamic Ride Hailing
If you would like to suggest additional variants to consider for inclusion please send email to the organizers describing the suggested variant and the availability of test instances. Variant that are appropriate for consideration should be of sufficient generality to be of broad interest and have some test instances currently available.
Participants in the Challenge are not expected to address all variants, or even multiple ones, although they are welcome to do so.
Each variant has its own webpage that specifies the formulation, instance format, and other special considerations for that variant. These pages can be accessed using the menu at right.
Participation in the challenge can take various forms, as detailed in our participation page. The participation page contains information that pertains to all variants, so please read it first.
Registered Teams
Registration for the Challenge closed on December 8, 2021 with 60 teams registered across the sever tracks.
Implementation Challenge registered competitors in all tracks: View list.
Challenge Goals
The main aim of the challenge is to create a reproducible picture of the state-of-the-art in vehicle routing problems. More specifically, its goals include:
- Identify and gather (with help from all participants) a standard set of benchmark instances and generators, with emphasis on real-world applications, enabling researchers to compare codes with one another.
- Encourage the implementation and experimental evaluation of methods with theoretical performance guarantees (such as approximation algorithms), helping identify the most effective algorithmic innovations.
- Identify realistic variants of the problem taking into account constraints that appear in practice, as well as new applications of existing variants.
- Produce research papers describing the algorithms studied, the experimental results obtained, and the new instances (or generators) produced. These papers will be presented at the Challenge workshop. Participants are also invited to submit papers with substantial original content to a special issue of one or more journals dedicated to the VRP Challenge.
Final Results
A total of 25 teams were invited to present results at the concluding workshop of the Implementation Challenge. Short papers about the invited solvers as well as videos from the workshop presentations are available on the Final Papers and Videos page (also accessible from the menu at right).
The full video playlist from the workshop includes presentations by the competitors as we as, keynote presentations by Mauricio Resende, Michel Gendreau, Renato Werneck, and Grazia Speranza and the unveiling of CVRP and VRPTW results by Eduardo Uchoa.
Detailed numerical results from the competition are available on the Results page (also accessible from the menu at right).
Publicity
To receive emails about the Challenge or to post messages once the Challenge begins, please subscribe to our mailing list.
View (and share) the VRP Challenge flyer.
View (and share) an announcement on algorithm evaluation. [Dated October 25, 2021]