« search calendars

« 12th DIMACS Implementation Challenge: Vehicle Routing Problems

12th DIMACS Implementation Challenge: Vehicle Routing Problems

April 05, 2022 - April 08, 2022


Online Event


Claudia Archetti, ESSEC Business School

Tamra Carpenter, DIMACS

Nicholas Kullman, Amazon

Catherine McGeoch, D-Wave Systems

Jorge Mendoza, HEC Montréal

Panos Pardalos, University of Florida

Mauricio Resende, Amazon

Eduardo Uchoa, Universidade Federal Fluminense

Thibaut Vidal, Polytechnique Montréal

Implementation Challenges trace back to the early years of DIMACS and to the vision of David S. Johnson to use experimentation as a companion to theory to gain more holistic perspective on the performance of algorithms. 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 research areas related to algorithms, data structures, implementation, and applications. This 12th DIMACS Implementation Challenge will be held in honor of David S. Johnson on the topic of Vehicle Routing Problems.

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 considers multiple VRP variants, representing a mix of classic VRP variants and newer variants inspired by practical considerations. The Challenge addresses problem variants that include some "classics" and 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 list of variants is:

  1. Capacitated VRP
  2. VRP with Time Windows
  3. Inventory Routing Problem
  4. VRP with Split Deliveries
  5. Routing for Electric Vehicles
  6. Capacitated Arc Routing (CARP) in realistic city networks
  7. CARP with time-dependent costs
  8. Dynamic Ridehailing.

This workshop will conclude the Challenge. It will take place online April 5-8, 2022 from roughly 9:00 AM (EDT/UTC-4) to 1:00 PM (EDT/UTC-4). Each day will be comprised of an early session (approximately 9:00-11:00 EDT) and a late session (approximately 11:00-1:00 EDT) and will include a keynote talk, as well as talks by selected teams that competed in the Challenge.

Spreadsheet View of Program

Video Playlist

After you are registered, you can click here (or the picture) to enter the virtual venue.

For information please:

If you have questions for the organizers please send email to the organizing committee. (dimacs_vrp_challenge_committee@email.rutgers.edu)

View the VRP Challenge flyer.

Challenge organizers Mauricio Resende and Eduardo Uchoa, together with Luciana Buriol and Celina Figueiredo, recently published The Guide to NP-Completeness is 40 Years Old: An Homage to David S. Johnson, which talks about Johnson's contributions to NP-completeness and experimental analysis of algorithms, including the Implementation Challenges.


Tuesday, April 5, 2022

Session - 1A Chairs: Tami Carpenter
9:00 AM - 9:20 AM

Welcome from Organizers

9:20 AM - 9:50 AM
Session - 1B Chairs: Jorge Mendoza
9:50 AM - 10:00 AM
10:00 AM - 10:20 AM

A Novel Repositioning Strategy for Ride-Hailing Problems

Christian Ackermann, University of Hildesheim

10:20 AM - 10:40 AM
Session - Interactive Time
10:40 AM - 11:10 AM

Break + Q & A/Discussion

Session - 2 Chair: Eduardo Uchoa
11:10 AM - 11:30 AM
11:30 AM - 11:50 AM
11:50 AM - 12:10 PM


Eduardo Queiroga, INRIA

12:10 PM - 12:30 PM

An Improved Hybrid Genetic Search with Data Mining for the CVRP

Marcelo R. H. Maia, Universidade Federal Fluminense

Session - Interactive Time
12:30 PM - 1:00 PM

Q & A/Discussion


Wednesday, April 6, 2022

Session - 3 Chair: Thibaut Vidal
9:00 AM - 9:20 AM
9:20 AM - 9:40 AM
9:40 AM - 10:00 AM

Adaptive Large Neighborhood Search for Vehicle Routing Problems

Stefan Røpke, Technical University of Denmark

10:00 AM - 10:30 AM
Session - Interactive Time
10:30 AM - 11:00 AM

Break + Q & A/Discussion

Session - 4 Chair: Claudia Archetti
11:00 AM - 11:20 AM

A Three-Stage Matheuristic for Multi-vehicle Inventory Routing Problem

Shihao Huang, Huazhong University of Science and Technology

11:20 AM - 11:40 AM

A Branch-and-cut Method with Warm-start for the Inventory Routing Problem

Jørgen Skålnes, Norwegian University of Science and Technology

11:40 AM - 12:00 PM

A New Branch-and-cut Algorithm for the Inventory Routing Problem

Thiago Guimaraes, Federal University of Paraná

12:00 PM - 12:20 PM

A Network Simplex based Matheuristic for the Inventory Routing Problem

Bruno Castro, Pontifical Catholic University of Rio de Janeiro

Session - Interactive Time
12:20 PM - 12:50 PM

Q & A/Discussion


Thursday, April 7, 2022

Session - 5 Chair: Eduardo Uchoa
9:00 AM - 9:20 AM

FHCSolver: Fast Hybrid CVRP Solver

Shibiao Jiang, Huawei Cloud

9:20 AM - 9:40 AM

MAESN: Solver Description

Jiongzhi Zheng, Huazhong University of Science and Technology

9:40 AM - 10:00 AM
10:00 AM - 10:20 AM

Hybrid Large Neighborhood Search for CVRP and VRP with Time Windows

Stefan Voigt, Catholic University of Eichstätt-Ingolstadt

Session - Interactive Time
10:20 AM - 10:50 AM

Break + Q & A/Discussion

Session - 6 Chair: Mauricio Resende
10:50 AM - 11:20 AM
11:20 AM - 11:40 AM
11:40 AM - 12:00 PM
12:00 PM - 12:20 PM
Session - Interactive Time
12:20 PM - 12:50 PM

Q & A/Discussion


Friday, April 8, 2022

Session - 7 Chair: Claudia Archetti
9:00 AM - 9:20 AM
9:20 AM - 9:40 AM
9:40 AM - 10:10 AM

Keynote: Routing Problems: Yesterday, Today, Tomorrow

M. Grazia Speranza, University of Brescia

Session - Interactive Time
10:10 AM - 10:40 AM

Break + Q & A/Discussion

Session - 8 Chair: Jorge Mendoza
10:40 AM - 11:00 AM
11:00 AM - 11:20 AM

Solving the VRP with Split Deliveries

Simen Tung Vadseth, Norwegian University of Science and Technology

11:20 AM - 11:40 AM

Redoute - Pruning Instances of E-VRP-NL Problems

James Fitzpatrick, University College Dublin

Session - Interactive Time
11:40 AM - 12:10 PM

Break + Q & A/Discussion

12:10 PM - 1:00 PM

https://www.youtube.com/playlist?list=PLKVCRT3MRed54TKIyR9o-bGgi_nciswtaThe Implementation Challenge workshop is open to all who register. Registration is free, but you must register to be admitted to the online venue. Presentations at the workshop are by invitation and will largely be given by teams that competed in the Challenge. (Please visit the Challenge website for details on the competition.)


After you are registered, you can click here to enter the virtual venue.

Please note that you may not be able to register once the event has begun.