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 just see on the market on the road — should visit on a given day and during which sequence. Normally, the target there’s to search out routes that result in the shortest, or the fastest, or the most affordable route. But fairly often also they are driven by constraints which are specific to a customer. As an illustration, if you’ve got 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 harder to integrate into an efficient delivery route.
To unravel the vehicle routing problem, we obviously we will not do our modeling without proper demand information and, ideally, customer-related characteristics. As an illustration, we want to know the scale 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 just would wish to service that individual stop. For realistic problems, you furthermore mght 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 are making blanket assumptions because there weren’t stop-specific data available.
Machine learning could be very interesting for this because nowadays many 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 possibly can now, at scale, in a somewhat automated way, extract that information and calibrate each stop to be modeled in a sensible way.
Using a standard OR approach means you write up an optimization model, where you begin by defining the target function. Normally 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 illustration, you have to tell the model that, if the vehicle visits a customer, it also needs to go away the shopper again. In academic terms, that is normally called flow conservation. Similarly, you’ll want to make sure that that each customer is visited exactly once on a given route. These and plenty 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 one of the best possible solution; we seek advice from them as solvers. Over time they find solutions that comply with all of the constraints. Then, it tries to search out routes which are 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 typical delivery vehicle in a U.S. city makes about 120 stops. It could take some time to resolve that explicitly, in order that’s normally not what firms do, since it’s just too computationally expensive. Subsequently, they use so-called heuristics, that are algorithms which are 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 overall idea is that you just train a model on a big set of existing routing solutions that you just either observed in an organization’s real-world operations or that you just generated using one among these efficient heuristics. In most machine-learning models, you now not have an explicit objective function. As a substitute, you’ll want to make the model understand what form of problem it’s actually taking a look at and what solution to the issue looks like. As an illustration, much 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 grasp how one can connect these delivery stops in a way that leads to solution — in our case, an inexpensive or fast solution. For those who then throw a very latest set of customer demands at it, it’s going to still have the opportunity to attach the dots quite literally in a way that you just would also do for those who were trying to search out route to attach these customers.
For this, we’re using model architectures that the majority people know from the language processing space. It seems just a little 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 illustration, in a language, you’ve got a certain vocabulary, and that is fixed. It is a discrete set of possible words that you may 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 may visit. Normally, 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 sensible?
That is form 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 important 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 very different, purely machine learning-based methodological approach, we’re in a position to predict routes which are just about pretty much as good as, or higher than, the routes that you just 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: Right away, one of the best methods are still very hungry by way of computational resources which are required to coach these models, but you’ll be able to 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 would possibly actually be in trouble because you would need to principally resolve the complete problem immediately once latest information in regards to the problem becomes available. For the reason that operational environment is dynamically changing, you would need to do that over and once again. While if you’ve got 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 firms to regulate to increasingly unpredictable changes within the environment.
Furthermore, optimization algorithms are sometimes manually crafted to resolve 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, however, repeatedly learns a routing policy from data. Once you’ve got 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 search out improvements to your routes without you having to speculate 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 frequently seeks to reduce cost or maximize profits. In point of fact, the objectives that firms and drivers face are rather more complex than that, and infrequently also they are somewhat contradictory. As an illustration, an organization wants to search out efficient routes, nevertheless it also desires to have a low emissions footprint. The motive force also desires to be secure and have a convenient way of serving these customers. On top of all of that, firms 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 just would never have the opportunity to realize in the identical way with a standard optimization approach.
So, that is the form 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 are rather more complex than this. As an illustration, if you need to optimize a complete supply chain — for example, the flow of a product from the manufacturer in China through the network of various ports around the globe, through the distribution network of a giant retailer in North America to your store where you really buy it — there are so many choices 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 inspiration for research and in addition private sector development efforts to construct tools that can eventually enable higher end-to-end supply chain optimization.