Traditionally, a route planner had to come up with good estimates for these parameters, so very often you find models and planning tools that are making blanket assumptions because no stop-specific data were available.
You’re currently applying machine learning to the vehicle routing problem. How are you employing it to leverage and possibly outperform traditional OR methods?
Another aspect to consider is that the operational environment of a route, especially in cities, is constantly changing. The available road infrastructure, traffic rules, or speed limits might be altered, the ideal parking lot may be occupied by something else, or a construction site might block a road. With a pure OR-based approach, you might actually be in trouble because you would have to basically resolve the entire problem instantly once new information about the problem becomes available. Since the operational environment is dynamically changing, you would have to do this over and over again. But if you have a well-trained model that has seen similar issues before, it could potentially suggest the next-best route to take, almost instantaneously. It’s more of a tool that would help companies to adjust to increasingly unpredictable changes in the environment.
This is because the last phase of the process is often the costliest due to inefficiencies such as:
• Long distances between stops
• Weather delays
• Traffic
• Lack of available parking
• Customer delivery preferences
• Partially full trucks
The average delivery vehicle in a U.S. city makes about 120 stops. It can take a while to solve that explicitly, so that’s usually not what companies do, because it’s just too computationally expensive. Therefore, they use so-called heuristics, which are algorithms that are very efficient in finding reasonably good solutions but typically cannot quantify how far away these solutions are from the theoretical optimum.
Moreover, optimization algorithms are often manually crafted to solve the specific problem of a given company. The quality of the solutions obtained from such explicit algorithms is bounded by the level of detail and sophistication that went into the design of the algorithm. A learning-based model, on the other hand, continuously learns a routing policy from data. Once you have defined the model structure, a well-designed route learning model will distill potential improvements to your routing policy from the vast amount of routes it is being trained on. Simply put, a learning-based routing tool will continue to find improvements to your routes without you having to invest into explicitly designing these improvements into the algorithm.
So, this is the kind of machine learning application that can actually have a tangible, real-world impact in industry, on society, and on the environment. The logistics industry has problems that are much more complex than this. For instance, if you want to optimize an entire supply chain—let’s say, the flow of a product from a manufacturer in China through the network of different ports around the world, through the distribution network of a big retailer in North America, to your store where you actually buy it—there are so many decisions involved in that, which obviously makes it a much harder task than optimizing a single vehicle route. Our hope is that with this initial work, we can lay the foundation for research and also private-sector development efforts to build tools that will eventually enable better end-to-end supply chain optimization.
To solve the vehicle routing problem, we obviously can’t do our modeling without proper demand information and, ideally, customer-related characteristics. For instance, we need to know the size or weight of the packages ordered by a given customer, or how many units of a certain product need to be shipped to a certain location. All of this determines the time that you would need to service that particular stop. For realistic problems, you also want to know where the driver can safely park the vehicle.
Once an optimization problem is formulated, there are algorithms out there that help us find the best possible solution; we refer to them as solvers. Over time, they find solutions that comply with all the constraints. Then, they try to find routes that are better and better, so cheaper and cheaper ones, until you either say, “OK, this is good enough for me,” or until they mathematically prove that they found the optimal solution.
In routing, it’s similar. In Cambridge, there are like 40,000 addresses that you can visit. Usually, it’s a subset of these addresses that need to be visited, and the challenge is: How do we combine this subset—these “words”—in a sequence that makes sense?
Usually, the objective is to find routes that lead to the shortest, fastest, or cheapest route. But very often they are also driven by constraints that are specific to a customer. For instance, you may have a customer with a specified delivery time, or a customer on the 15th floor in a high-rise building vs. the ground floor. These customers are more difficult to integrate into an efficient delivery route.
Using a traditional OR approach means you write up an optimization model where you start by defining the objective function. In most cases that’s some sort of cost function. Then there are a bunch of other equations that define the inner workings of a routing problem. For instance, you must tell the model that, if the vehicle visits a customer, it also needs to leave the customer again. In academic terms, that’s usually called flow conservation. Similarly, you need to make sure that every customer is visited exactly once on a given route. Together, these and many other real-world constraints define what constitutes a viable route. It may seem obvious to us, but this needs to be encoded explicitly.
Published April 16, 2024, in MIT News.
منبع: https://www.qualitydigest.com/inside/customer-care-article/enhancing-last-mile-logistics-machine-learning-050624.html
Routing is just a great test bed for us because it’s the most fundamental problem in the logistics industry.
The vehicle routing problem is faced by pretty much every logistics and delivery company, like USPS, Amazon, UPS, FedEx, and DHL, every single day. Simply speaking, it’s finding an efficient route that connects a set of customers that need deliveries or something needs to be picked up from them. It’s deciding which customers each of those vehicles—the ones you see out there on the road—should visit on a given day, and in which sequence.
For instance, similar to training a large language model on words in a given language, you need to train a route-learning model on the concept of the various delivery stops and their demand characteristics. Like understanding the inherent grammar of natural language, your model needs to understand how to connect these delivery stops in a way that results in a good solution—in our case, a cheap or fast solution. If you then throw a completely new set of customer demands at it, it will still be able to connect the dots quite literally in a way that you would also do if you were trying to find a good route to connect these customers.
Across the country, hundreds of thousands of drivers deliver packages and parcels to customers and companies each day, with many click-to-door times averaging only a few days. Coordinating a supply chain feat of this magnitude in a predictable and timely way is a longstanding problem of operations as researchers work to optimize the last leg of delivery routes.
You can now, at scale, in a somewhat automated way, extract that information and calibrate every single stop to be modeled in a realistic way.
What is the vehicle routing problem, and how do traditional operations research (OR) methods address it?
That’s kind of the novelty of our approach—leveraging that structure that has proven to be extremely effective in the language space and bringing it into combinatorial optimization. Routing is just a great test bed for us because it’s the most fundamental problem in the logistics industry.
For this, we’re using model architectures that most people know from the language processing space. It seems a little bit counterintuitive, because what does language processing have to do with routing? But actually, the properties of these models, especially transformer models, are good at finding structure in language—connecting words in a way that they form sentences. For instance, in a language, you have a certain fixed vocabulary. It’s a discrete set of possible words that you can use, and the challenge is to combine them in a meaningful way.
Lastly, optimization-based methods are typically limited to optimizing for a very clearly defined objective function that often seeks to minimize cost or maximize profits. In reality, the objectives that companies and drivers face are much more complex than that, and often they are also somewhat contradictory. For instance, a company wants to find efficient routes, but it also wants to have a low emissions footprint. The driver also wants to be safe and have a convenient way of serving these customers. On top of all of that, companies also care about consistency. A well-designed route learning model can eventually capture these high-dimensional objectives by itself, and that is something that you would never be able to achieve in the same way with a traditional optimization approach.
These inefficiencies became even more exaggerated and evident during the pandemic. But with newer technology and more individualized and nuanced data, researchers are able to develop models with better routing options. However, they must balance the computational cost of running them.
Matthias Winkenbach, MIT principal research scientist, director of research for the MIT Center for Transportation and Logistics (CTL), and a researcher with the MIT-IBM Watson AI Lab, discusses how artificial intelligence could provide better and more efficient solutions.
Right now, the best methods are still very hungry in terms of computational resources that are required to train these models. But you can front-load some of this effort. Then, the trained model is relatively efficient in producing a new solution as it becomes required.
What advantages does a method like yours have over other state-of-the-art OR techniques?
Of course, there are already very good routing algorithms out there that emerged from decades of operations research. What we are trying to do in this project is show that with a completely different, purely machine learning-based methodological approach, we are able to predict routes that are pretty much as good as, or better than, the routes that you would get from running a state-of-the-art route optimization heuristic.
That’s what we’re currently working on with folks 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 either observed in a company’s real-world operations or that you generated using one of these efficient heuristics. In most machine-learning models, you no longer have an explicit objective function. Instead, you need to make the model understand what kind of problem it’s actually looking at and what a good solution to the problem looks like.Similar to training a large language model on words in a given language, you need to train a route-learning model on the concept of the various delivery stops and their demand characteristics.
It’s more of a tool that would help companies to adjust to increasingly unpredictable changes in the environment.
Machine learning can be very interesting for this, because nowadays most of the drivers have smartphones or GPS trackers, so there is a ton of information as to how long it takes to deliver a package. You can now, at scale and in a somewhat automated way, extract that information and calibrate every single stop to be modeled in a realistic way.