Hundreds of thousands of drivers across the country deliver packages and packages to customers and businesses every day, often with an average click-to-door time of just a few days. Coordinating a supply chain feat of this scale in a predictable and timely manner has been a long-standing challenge in operations research, and researchers have been working to optimize the final leg of a delivery route. This is due to inefficiencies such as long distances between stops due to increased demand for e-commerce, weather delays, traffic congestion, parking availability, customer delivery requests, or partially full trucks. This is because the final stage of the process is often the most costly. It was exaggerated and obvious during the pandemic.
New technologies and more personalized and nuanced data allow researchers to develop models with better routing options, but at the same time they must balance the computational cost of running the models. there is. Matthias Winkenbach, principal investigator at MIT, director of research at the MIT Center for Transportation and Logistics (CTL), and researcher at the MIT-IBM Watson AI Lab, discusses how artificial intelligence can improve combinatorial optimization. We talk about how we can provide better, more computationally efficient solutions. Problems like this.
question: What is the vehicle routing problem and how do traditional operations research (OR) techniques address it?
answer: Vehicle routing issues are faced every day by nearly every logistics and delivery company, including USPS, Amazon, UPS, FedEx, and DHL. Simply put, it's about finding efficient routes between a set of customers that need to be delivered or receive something from them. Each vehicle you see on the road determines which customers you visit on any given day and in what order. The goal there is usually to find the route that leads to the shortest, fastest, or cheapest route. But they are often also driven by customer-specific constraints. For example, if you have a customer who has a specified delivery window, or if you have a customer who lives on her 15th floor of a high-rise building instead of her 1st floor. This makes integrating these customers into efficient delivery routes even more difficult.
Solving vehicle routing problems cannot be modeled without proper demand information and, ideally, customer-related characteristics. For example, you might need to know the size and weight of a package ordered by a particular customer, or how many of a particular product should be shipped to a particular location. All of this determines the time required to serve that particular stop. In a practical matter, drivers also want to know where they can safely park their vehicles. Traditionally, route planners have had to derive good estimates for these parameters. As a result, models and planning tools were often found making blanket assumptions because there was no stop-specific data available.
Since most drivers now have smartphones and GPS trackers, there is a wealth of information about how long it takes to deliver a package, so machine learning could be very interesting in this regard. We can now extract that information at scale in a somewhat automated way and adjust every outage that is modeled in a realistic way.
Using the traditional OR approach, you start by creating an optimization model and defining an objective function. Most of the time it's some kind of cost function. Additionally, there are many other equations that define the inner workings of the wiring problem. For example, if a vehicle visits a customer, we need to tell the model that it needs to leave the customer again. In academic terminology, this is usually called flow conservation. Similarly, every customer needs to make sure that he is visited only once on a particular route. These and many other real-world constraints combine to define what constitutes a viable route. Although it may seem obvious to us, this needs to be encoded explicitly.
Once an optimization problem is formulated, algorithms exist to help find the best possible solution. We call them solvers. Over time, a solution will be found that satisfies all constraints. It then tries to search for a better, or less expensive, route until the user says “OK, this is good enough” or until it can prove mathematically that it has found the optimal solution. The average delivery vehicle in a U.S. city makes about 120 stops. Solving this explicitly can be time consuming, so companies typically don't do this because the computational cost is too high. Therefore, they use so-called heuristics. This is a very efficient algorithm for finding fairly good solutions, but it usually does not allow you to quantify how far these solutions are from the theoretical optimum.
question: You are currently applying machine learning to a vehicle routing problem. How do you leverage this to leverage and perhaps outperform traditional OR techniques?
answer: That's what we're working on right now with the folks at the MIT-IBM Watson AI Lab. The general idea here is to base the model on a large set of existing routing solutions, either observed in an enterprise's actual operations or generated using one of these efficient heuristics. It means training. Most machine learning models no longer have an explicit objective function. Instead, you need to make the model understand what kind of problem it is actually investigating and what an appropriate solution to the problem might be. For example, just as you would train a large language model for words in a particular language, you would need to train a route learning model based on the concept of different shipping locations and their demand characteristics. Just like understanding the inherent grammar of natural language, the model needs to understand how to connect these delivery stops in a way that yields a suitable solution, in this case a cheap or fast solution. Then, if you throw a whole new set of customer demands at you, you can quite literally connect the dots, just as you would if you were trying to find the right route to connect those customers.
For this, we use a model architecture that is familiar to most people in the language processing field. What does language processing have to do with routing? This seems a little counterintuitive. But in reality, the properties of these models, especially the Transformer model, are good at finding the structure of language, that is, connecting words in ways that form sentences. For example, languages have a certain vocabulary, which is fixed. This is a distinct set of words that can be used, and the challenge is to combine them in a meaningful way. The same goes for routing. He has around 40,000 addresses in Cambridge that he can visit. Typically, it is a subset of these addresses that needs to be accessed, and the challenge is how to combine this subset (these “words”) in a meaningful order.
This is a kind of novelty in our approach, in that we take a structure that has proven to be very effective in the language space and bring it to combinatorial optimization. Routing is the most fundamental problem in the logistics industry, so it's just a great testbed for us.
Of course, very good routing algorithms already exist, born from decades of operational research. What we are trying to do with this project is to show that using a completely different, purely machine learning-based methodological approach, we can predict routes that are almost as good as, or even better than, the ones that users get. is. Runs state-of-the-art route optimization heuristics.
question: What advantages does a method like yours have compared to other state-of-the-art OR techniques?
answer: Currently, even the best methods are still very resource intensive in terms of the computational resources required to train these models, but some of this work can be frontloaded. The trained model then generates new solutions relatively efficiently when needed.
Another aspect to consider is the constantly changing environment in which lines operate, especially in urban areas. Available road infrastructure, traffic rules and speed limits may change, ideal parking spots may be taken over by others, or roads may be blocked by construction sites. A pure OR-based approach can actually create problems because it essentially requires the entire problem to be solved immediately once new information about the problem becomes available. Because the production environment changes dynamically, this must be repeated many times. On the other hand, if you have a well-trained model that has encountered similar problems before, it may suggest the next best route almost instantly. Rather, it is a tool that helps companies adapt to changes in an increasingly unpredictable environment.
Additionally, optimization algorithms are often created manually to solve specific problems for specific companies. The quality of solutions obtained from such explicit algorithms is limited by the level of detail and sophistication built into the design of the algorithm. Learning-based models, on the other hand, continuously learn routing policies from data. Once the model structure is defined, a well-designed route learning model extracts potential improvements to routing policies from the large number of routes it trains. Simply put, learning-based routing tools continue to find route improvements without having to invest in explicitly designing these improvements into the algorithm.
Finally, optimization-based methods are typically limited to optimization for very well-defined objective functions, often aiming at minimizing costs or maximizing profits. In reality, the goals facing companies and drivers are much more complex than that, and they are often somewhat contradictory. For example, companies want to find efficient routes, but at the same time they want to reduce emissions. Drivers also want a safe and convenient way to serve these customers. In addition to that, companies also value consistency. A well-designed route learning model can ultimately achieve these high-dimensional goals on its own, which traditional optimization approaches can never accomplish in the same way.
So this is the kind of machine learning application that can actually have a tangible, real-world impact on industry, society, and the environment. The logistics industry is far more complex than this. For example, if you want to optimize your entire supply chain, the flow of products from a manufacturer in China, through a network of various ports around the world, through the distribution network of a large retailer in North America, to your store. Let's think about. Where to actually buy – there are so many decisions involved and it's clearly a much more difficult task than optimizing a single vehicle route. Our hope is that this initial work lays the foundation for research and private sector development efforts to ultimately build tools that better enable end-to-end supply chain optimization.
