Across the country, hundreds of thousands of drivers deliver packages and parcels to customers and businesses every day, with average click-to-door times of just a few days. Coordinating a supply chain of this size in a predictable and timely manner is a long-standing problem for operations research, as researchers work to improve last-mile delivery methods. This is because the last stage of the process is often the most expensive due to inefficiencies such as long distances between stops due to increased e-commerce demand, weather delays, traffic, unavailability of parking, customer delivery preferences, or partially full trucks. – shortcomings that have become more exaggerated and evident during the pandemic.
With newer technology and more personalized and accurate data, researchers can develop models with better routing options but at the same time need to balance the computational cost of running them. Matthias Winkenbach, principal research scientist at MIT, research director at the MIT Center for Transportation and Logistics (CTL) and researcher at MIT’s Watson AI Lab and IBM, discusses how AI can provide better and more efficient solutions than… Computational aspect of combinatorial optimization. Problem like this.
s: What is the vehicle routing problem, and how do traditional operations research (OR) methods address it?
a: Almost every logistics and delivery companies like USPS, Amazon, UPS, FedEx and DHL face the problem of vehicle routing every day. Simply put, it is finding an efficient route that connects a group of customers who either need a delivery to them, or something to be obtained from them. It’s determining which customers each one of these vehicles – that you see out there on the road – should visit on a given day and in what sequence. The goal is usually to find routes that lead to the shortest, fastest, or cheapest route. But often they are also driven by client-specific constraints. For example, if you have a customer with a specific delivery time slot, or a customer on the 15th floor of a high-rise building versus the ground floor. This makes integrating these customers into an effective delivery path more difficult.
To solve the vehicle routing problem, we obviously cannot perform our modeling without appropriate demand information and, ideally, customer-related characteristics. For example, we need to know the size or weight of packages ordered by a particular customer, or how many units of a particular product need to be shipped to a particular location. All of this determines the time you will need to service that specific station. For real-world problems, you also want to know where the driver can park safely. Traditionally, a route planner has had to come up with good estimates of these parameters, so you often find models and planning tools making blanket assumptions because stop-specific data are not available.
Machine learning can be very interesting for this because most drivers nowadays have smartphones or GPS trackers, so there is a lot of information about how long it takes to deliver a package. You can now, at scale, and in a somewhat automated way, extract that information and calibrate each breakpoint to be designed in a realistic way.
Using the traditional OR approach means that you write an optimization model, where you start by defining the objective function. In most cases, this is some type of cost function. Then there are a set of other equations that define the inner workings of the routing problem. For example, you should tell the model that if the car visits a customer, it must also leave the customer again. In academic terms, this is usually called flow conservation. Likewise, you need to ensure that each customer is visited exactly once on a particular route. Together, these and many other real-world constraints define what constitutes a viable path. It may seem obvious to us, but this needs to be explicitly coded.
Once an optimization problem is formulated, there are algorithms that help us find the best possible solution; We refer to them as solutions. Over time, they find solutions that meet all constraints. Then it tries to find better and better, cheaper and cheaper ways until you say, “Okay, this is good enough for me,” or until it can prove mathematically that it has found the optimal solution. The average delivery vehicle in an American city makes about 120 stops. It would take some time to solve this problem explicitly, so this is not what companies usually do, because it is very computationally expensive. Therefore, they use so-called heuristics, which are algorithms that are very effective at finding reasonably good solutions but usually cannot determine how far these solutions are from the optimal theoretical solution.
s: You are currently applying machine learning to a car routing problem. How do you use it to leverage and perhaps even outperform traditional operations methods?
a: This is what we are currently working on with people from the MIT-IBM Watson AI Lab. Here, the general idea is that you train a model on a large set of existing routing solutions that you have either observed in real-world company operations or that you have created using one of these powerful heuristics. In most machine learning models, you no longer have a clear objective function. Instead, you need to make the model understand what kind of problem it is actually looking at and what a good solution to the problem looks like. For example, just as you would train a large language model on words in a particular language, you need to train a route-learning model on the concept of different delivery stations and their demand characteristics. Like understanding the inherent rules of natural language, your model needs to understand how to connect these delivery stations in a way that leads to a good solution — in our case, a cheap or fast solution. If you then throw a whole new set of customer requests at him, he’ll still be able to connect the dots quite literally the way you would too if you were trying to find a good route to deliver those customers.
For this, we use typical constructs that most people know from the language processing space. It seems a bit counterintuitive because what does language processing have to do with orientation? But in fact, the properties of these models, especially the transformed models, are good at finding structure in language – connecting words in such a way that they form sentences. For example, in a language, you have a certain vocabulary, and this is fixed. It’s a separate set of possible words you can use, and the challenge is to combine them in a meaningful way. In guidance, it is similar. In Cambridge there are around 40,000 addresses you can visit. Usually, there is a subset of these addresses that need to be visited, and the challenge is: How do we group this subset—these “words”—into a logical sequence?
This is kind of the novelty of our approach – taking this structure that has proven very effective in the language domain and introducing it into combinatorial optimization. Routing is just a great test for us because it is the fundamental problem in the logistics industry.
Of course, there are already very good routing algorithms that have emerged from decades of operations research. What we’re trying to do in this project is to show that using a completely different methodological approach based on machine learning, we can predict methods that are substantially as good as or better than the methods you can get from them. Run the latest heuristics for route optimization.
s: What advantages does a method like yours have over other modern process techniques?
a: Right now, the best approaches are still very thirsty in terms of the computational resources required to train these models, but you can make some of these efforts early on. Hence, the trained model is relatively efficient in producing a new solution when it becomes required.
Another aspect to consider is that the operational environment of the road, especially in cities, is constantly changing. The available road infrastructure, traffic rules and speed limits may be changed, an ideal parking lot may be occupied by something else, or a construction site may block the road. With the OR-based approach, you may actually be in trouble because you will have to solve essentially the entire problem immediately as soon as new information about the problem becomes available. Since the operating environment changes dynamically, you will have to do this over and over again. Whereas if you have a well-trained model that has seen similar issues before, it will likely suggest the next best path to take, almost instantly. It is just a tool that will help companies adapt to increasingly unpredictable environmental changes.
Furthermore, optimization algorithms are often designed manually to solve a specific problem for a particular company. The quality of solutions obtained from such explicit algorithms is limited by the level of detail and complexity that has been introduced into the design of the algorithm. On the other hand, the learning-based model continuously learns the routing policy from the data. Once the model architecture is defined, a well-designed path learning model will extract potential improvements to your routing policy from the vast amount of paths being trained. Simply put, a learning-based routing tool will continue to find improvements to your routes without you having to invest in explicitly designing those improvements into the algorithm.
Finally, optimization-based methods are usually limited to optimizing a very clearly defined objective function, which often seeks to minimize cost or maximize profits. In reality, the goals faced by companies and drivers are much more complex, and often also somewhat contradictory. For example, a company wants to find efficient methods, but also wants to have a low emissions footprint. The driver also wants to be safe and have a convenient way to serve these customers. Above all, companies also care about consistency. A well-designed path learning model can eventually capture these high-dimensional goals itself, which is something you will never be able to achieve in the same way using a traditional optimization approach.
So, this is the type of machine learning application that can have a tangible real-world impact in industry, on society, and on the environment. The logistics industry faces much more complex problems than this. For example, if you want to optimize your entire supply chain – let’s say, the flow of a product from a manufacturer in China through a network of different outlets around the world, through the distribution network of a large retailer in North America to your store where you actually buy it – there Many decisions are involved, which clearly makes it a much more difficult task than optimizing a single vehicle’s route. Our hope is that through this initial work, we can lay the foundation for research as well as private sector development efforts to build tools that will ultimately enable better end-to-end supply chain optimization.