Implementation Challenge: Vehicle Routing

12th Implementation Challenge


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 June 14-16, 2021. 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) Stochastic VRPs
6) Capacitated Arc Routing
7) Time-dependent Capacitated Arc Routing

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.

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.

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.

Thinking about entering? Fill out the participation information form.