Organizer(s):

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

Description

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:

• Visit the VRP Challenge website
• Subscribe to the VRP Challenge mailing list
• Follow the Challenge on twitter.

If you have questions for the organizers please send email to the organizing committee. ([email protected])

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.

Program

Tuesday, April 5, 2022

Wednesday, April 6, 2022

Thursday, April 7, 2022

Friday, April 8, 2022

Call For Participation

The 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.

Presented in association with the Special Focus on Bridging Continuous and Discrete Optimization and the Implementation Challenges.

Registration for this event is closed.