Across the country, lots of of hundreds of drivers deliver packages and parcels to customers and corporations every day, with many click-to-door times averaging only a number of days. Coordinating a supply chain feat of this magnitude in a predictable and timely way is a longstanding problem of operations research, where researchers have been working to optimize the last leg of delivery routes. It is because the last phase of the method is commonly the most expensive attributable to inefficiencies like long distances between stops attributable to increased ecommerce demand, weather delays, traffic, lack of parking availability, customer delivery preferences, or partially full trucks — inefficiencies that became more exaggerated and evident in the course of the pandemic.
With newer technology and more individualized and nuanced data, researchers are capable of develop models with higher routing options but at the identical time 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 higher and more computationally efficient solutions to a combinatorial optimization problem like this one.
Q: What’s the vehicle routing problem, and the way do traditional operations research (OR) methods address it?
A: The vehicle routing problem is faced by just about every logistics and delivery company like USPS, Amazon, UPS, FedEx, DHL each day. Simply speaking, it’s finding an efficient route that connects a set of consumers that have to be either delivered to, or something must be picked up from them. It’s deciding which customers each of those vehicles — that you simply see on the market on the road — should visit on a given day and through which sequence. Often, the target there’s to seek out routes that result in the shortest, or the fastest, or the most cost effective route. But fairly often also they are driven by constraints which can be specific to a customer. As an example, if you’ve a customer who has a delivery time window specified, or a customer on the fifteenth floor within the high-rise constructing versus the bottom floor. This makes these customers tougher to integrate into an efficient delivery route.
To resolve the vehicle routing problem, we obviously we will not do our modeling without proper demand information and, ideally, customer-related characteristics. As an example, we’d like to know the dimensions or weight of the packages ordered by a given customer, or what number of units of a certain product have to be shipped to a certain location. All of this determines the time that you simply would want to service that individual stop. For realistic problems, you furthermore may need to know where the driving force can park the vehicle safely. Traditionally, a route planner needed to provide you with good estimates for these parameters, so fairly often you discover models and planning tools which can be making blanket assumptions because there weren’t stop-specific data available.
Machine learning might be very interesting for this because nowadays a lot of the drivers have smartphones or GPS trackers, so there’s a ton of data as to how long it takes to deliver a package. You’ll be able to now, at scale, in a somewhat automated way, extract that information and calibrate each stop to be modeled in a practical way.
Using a standard OR approach means you write up an optimization model, where you begin by defining the target function. Generally that is some kind of cost function. Then there are a bunch of other equations that outline the inner workings of a routing problem. As an example, you have to tell the model that, if the vehicle visits a customer, it also needs to depart the shopper again. In academic terms, that is normally called flow conservation. Similarly, you’ll want to ensure that each customer is visited exactly once on a given route. These and lots of other real-world constraints together define what constitutes a viable route. It could appear obvious to us, but this must be encoded explicitly.
Once an optimization problem is formulated, there are algorithms on the market that help us find the most effective possible solution; we discuss with them as solvers. Over time they find solutions that comply with all of the constraints. Then, it tries to seek out routes which can be higher and higher, so cheaper and cheaper ones until you either say, “OK, this is nice enough for me,” or until it might probably mathematically prove that it found the optimal solution. The common delivery vehicle in a U.S. city makes about 120 stops. It may take some time to unravel that explicitly, in order that’s normally not what corporations do, since it’s just too computationally expensive. Subsequently, they use so-called heuristics, that are algorithms which can be very efficient find reasonably good solutions but typically cannot quantify how distant these solutions are from the theoretical optimum.
Q: You’re currently applying machine learning to the vehicle routing problem. How are you employing it to leverage and possibly outperform traditional OR methods?
A: That is what we’re currently working on with folks from the MIT-IBM Watson AI Lab. Here, the final idea is that you simply train a model on a big set of existing routing solutions that you simply either observed in an organization’s real-world operations or that you simply generated using one in all these efficient heuristics. In most machine-learning models, you not have an explicit objective function. As a substitute, you’ll want to make the model understand what type of problem it’s actually taking a look at and what a very good solution to the issue looks like. As an example, just like training a big language model on words in a given language, you’ll want to train a route learning model on the concept of the assorted delivery stops and their demand characteristics. Like understanding the inherent grammar of natural language, your model needs to know connect these delivery stops in a way that ends in a very good solution — in our case, an affordable or fast solution. In the event you then throw a totally latest set of customer demands at it, it is going to still have the option to attach the dots quite literally in a way that you simply would also do in case you were trying to seek out a very good route to attach these customers.
For this, we’re using model architectures that almost all people know from the language processing space. It seems somewhat bit counterintuitive because what does language processing need to do with routing? But actually, the properties of those models, especially transformer models, are good at finding structure in language — connecting words in a way that they form sentences. As an example, in a language, you’ve a certain vocabulary, and that is fixed. It is a discrete set of possible words that you could use, and the challenge is to mix them in a meaningful way. In routing, it’s similar. In Cambridge there are like 40,000 addresses that you could visit. Often, it is a subset of those addresses that have to be visited, and the challenge is: How can we mix this subset — these “words” — in a sequence that is smart?
That is type of the novelty of our approach — leveraging that structure that has proven to be extremely effective within the language space and bringing it into combinatorial optimization. Routing is just an excellent test bed for us since it’s probably the most fundamental problem within the logistics industry.
In fact, there are already excellent routing algorithms on the market that emerged from many years of operations research. What we try to do on this project is show that with a totally different, purely machine learning-based methodological approach, we’re capable of predict routes which can be just about pretty much as good as, or higher than, the routes that you simply would get from running a state-of-the-art route optimization heuristic.
Q: What benefits does a way like yours have over other state-of-the-art OR techniques?
A: At once, the most effective methods are still very hungry by way of computational resources which can be required to coach these models, but you possibly can front-load a few of this effort. Then, the trained model is comparatively efficient in producing a brand new solution because it becomes required.
One other aspect to contemplate is that the operational environment of a route, especially in cities, is continually changing. The available road infrastructure, or traffic rules and speed limits is perhaps altered, the best car parking zone could also be occupied by something else, or a construction site might block a road. With a pure OR-based approach, you may actually be in trouble because you would need to mainly resolve the whole problem immediately once latest information concerning the problem becomes available. For the reason that operational environment is dynamically changing, you would need to do that over and another time. While if you’ve a well-trained model that has seen similar issues before, it could potentially suggest the next-best path to take, almost instantaneously. It’s more of a tool that will help corporations to regulate to increasingly unpredictable changes within the environment.
Furthermore, optimization algorithms are sometimes manually crafted to unravel the particular problem of a given company. The standard of the solutions obtained from such explicit algorithms is bounded by the extent of detail and class that went into the design of the algorithm. A learning-based model, alternatively, constantly learns a routing policy from data. Once you’ve 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’s being trained on. Simply put, a learning-based routing tool will proceed to seek out improvements to your routes without you having to take a position into explicitly designing these improvements into the algorithm.
Lastly, optimization-based methods are typically limited to optimizing for a really clearly defined objective function, which regularly seeks to reduce cost or maximize profits. In point of fact, the objectives that corporations and drivers face are far more complex than that, and sometimes also they are somewhat contradictory. As an example, an organization wants to seek out efficient routes, however it also desires to have a low emissions footprint. The driving force also desires to be protected and have a convenient way of serving these customers. On top of all of that, corporations also care about consistency. A well-designed route learning model can eventually capture these high-dimensional objectives by itself, and that’s something that you simply would never have the option to attain in the identical way with a standard optimization approach.
So, that is the type of machine learning application that may even have a tangible real-world impact in industry, on society, and on the environment. The logistics industry has problems which can be far more complex than this. As an example, if you must optimize a complete supply chain — as an example, the flow of a product from the manufacturer in China through the network of various ports world wide, through the distribution network of an enormous retailer in North America to your store where you truly buy it — there are so many selections 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 will lay the muse for research and likewise private sector development efforts to construct tools that can eventually enable higher end-to-end supply chain optimization.
