EURO Meets NeurIPS 2022 Vehicle Routing Competition
The efficient transport of people and goods is often a big puzzle; in jargon formulated as solving ‘vehicle routing problems’ (VRP’s). For many companies, solving VRP’s is an essential daily task, for which they use industrial applications that support them, packed with smart algorithms based on advanced mathematics and artificial intelligence.
While Vehicle Routing Problems (VRP’s) have been traditionally studied in the domain of Operations Research (OR), they have lately been the subject of extensive work in the scientific Machine Learning (ML) community, tackling them using Deep Learning. In OR, problems are broken down into basic components and then solved in defined steps by mathematical analysis. In ML, algorithms use historical data or experience to recognize patterns to solve problems.
This competition bridges the domains of Operations Research and Machine Learning – which is quite unique. Supported by renowned academic organizations in the field of OR and ML, it’s a privilege to organize this competition as part of the annual NeurIPS conference.
We anticipate that the winning method will significantly advance the state-of-the-art for solving routing problems, therefore providing a strong foundation for further research in both the OR and ML communities, as well as a practical impact on the real-world solving of VRP’s.
Deadline for team registration is September 30, 2022.
In this competition, participating researchers from both Operations Research (OR) and Machine Learning (ML) have to optimize routes for around 25 vehicles dispatching goods to around 500 customers.
The goal is to minimize the total distance, and respecting time windows in which deliveries should occur. Vehicles can wait at a customer when they arrive too early, but cannot be late. Obviously, each vehicle has a maximum load capacity.
Decision-Making in the Face of Uncertainty
While this is a significant challenge in itself, the competition also considers a dynamic variant where new orders arrive during the day. In this setting, it may be more efficient to delay some deliveries, to combine them in a route with nearby orders that may still arrive. As these future orders are unkown, this models a real-world problem of complex decision-making in the face of uncertainty. To win the competition, participants will likely need a mix of both Operations Research and Machine Learning.
Unique competition
The competition aims to make a fair comparison between OR and ML methods and encourages hybrid methods to advance the state-of-the-art in vehicle routing. “And that is necessary”, states Wouter Kool, PhD candidate in Machine Learning, Senior OR engineer at ORTEC, and initiator of the competition. “With much hype around Machine Learning, powerful OR-based methods are often overlooked. On the other hand, Machine Learning can bring much to the table, which is why we are focusing on integrating disciplines. Then 1 plus 1 really becomes 3. However, this is not easy, as few researchers have knowledge of the state-of-the-art in both OR and ML. For example, OR researchers often use simple ML techniques, if any, whereas ML researchers use advanced Deep Learning models, but in many cases fail to outperform OR methods.”
Challenging the Status Quo in Routing Optimization
The Vehicle Routing Problem with Time Windows (VRPTW) has been studied for many years, but recently machine learning based approaches have started to address this problem. The competition provides a timely and fair evaluation, on a new realistic dataset provided by ORTEC. Additionally, the dynamic variant challenges both OR and ML researchers to come up with new techniques to handle the uncertainty aspect, while optimizing routes at the same time. Such a dynamic setting is traditionally difficult for OR based approaches and may provide additional opportunities for ML.
The overall winner of the competition is determined by the best performance on both problem variants, to encourage flexible methods that can handle different settings.
Real Data, Real Relevance
Normally, routing competitions work with limited, often synthetically generated, data. For this competition, ORTEC provided a set of real anonymized data from one of its customers, providing 250 real instances from a US based grocery delivery service. This makes the competition more realistic and relevant, for example because it takes into account actual road distances.
Next to that, to encourage actual improvement of the state-of-the-art, ORTEC provided a state-of-the-art VRPTW solver (that won the first place in the recent DIMACS challenge!) as a starting point for participants. Combined with a strategy for using it to solve the dynamic variant, all participants have the tools necessary to solve both versions of the problem.
Why is this relevant?
From a practical perspective, solving vehicle routing problems is an essential daily task for many companies around the world. Improving our solutions, which are based on sophisticated techniques, result in more efficiency, lower costs, and above all less CO2 emissions.
In a broader sense, this competition is highly relevant for the future. As the world becomes increasingly complex and fast, algorithms need to become more dynamic: solving a problem not just once, but continuously under changing circumstances. The best solutions will likely involve a mix of Operations Research and Machine Learning and will emerge from high-quality academic research.
Wouter Kool: “We try to encourage just that: we bring researchers from different disciplines together and provide them with a relevant problem based on realistic data to work on. While both ML and OR methods can come to a solution, only together will the best solution emerge: the best routes under changing circumstances.”
About ....
... the Competition
The competition is a joint effort of several previous competitions: the 12th DIMACS Implementation Challenge, the series of VeRoLog competitions, and the AI4TSP competition. The competition is hosted at the Thirty-sixth Conference on Neural Information Processing Systems (NeurIPS 2022). Sponsors are the Association of European Operational Research Societies (EURO), the Eindhoven AI Systems Institute (EAISI), and ORTEC.
... EURO
EURO is the association of European Operational Research Societies. It counts 29 society members all over Europe. EURO’s goal is to promote Operational Research throughout Europe.
... NeurIPS
NeurIPS is a top-tier machine learning conference, with over 2000 papers presented and 15000 participants. It hosts a yearly competition track, with 25 competitions in various disciplines at NeurIPS 2022.