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 must 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 by which sequence. Often, the target there may be to seek 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. For example, if you’ve gotten 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 unravel the vehicle routing problem, we obviously we won’t do our modeling without proper demand information and, ideally, customer-related characteristics. For 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 must be shipped to a certain location. All of this determines the time that you simply would wish to service that exact 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 give you 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 may be 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 practical way.

Using a standard OR approach means you write up an optimization model, where you begin by defining the target function. Usually that is some form of cost function. Then there are a bunch of other equations that outline the inner workings of a routing problem. For example, you will need to tell the model that, if the vehicle visits a customer, it also needs to go away the client again. In academic terms, that is normally called flow conservation. Similarly, you could ensure 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 the most effective 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 seek 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 could actually mathematically prove that it found the optimal solution. The common delivery vehicle in a U.S. city makes about 120 stops. It might take some time to unravel 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 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 considered one of these efficient heuristics. In most machine-learning models, you not have an explicit objective function. As a substitute, you could make the model understand what type of problem it’s actually taking a look at and what a great solution to the issue looks like. For example, just like training a big language model on words in a given language, you could train a route learning model on the concept of the varied delivery stops and their demand characteristics. Like understanding the inherent grammar of natural language, your model needs to know methods to connect these delivery stops in a way that ends in a great solution — in our case, an inexpensive or fast solution. In the event you then throw a totally latest set of customer demands at it, it would still find a way to attach the dots quite literally in a way that you simply would also do for those who were trying to seek out a great route to attach these customers.

For this, we’re using model architectures that the majority people know from the language processing space. It seems a bit bit counterintuitive because what does language processing must 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. For example, in a language, you’ve gotten 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 must 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 important test bed for us since it’s probably the most fundamental problem within the logistics industry. 

After all, 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 in a position to predict routes which are 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 when it comes to computational resources which are 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 latest solution because it becomes required. 

One other aspect to think about is that the operational environment of a route, especially in cities, is continually changing. The available road infrastructure, or traffic rules and speed limits could be altered, the perfect 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 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 more. While if you’ve gotten 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 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, repeatedly learns a routing policy from data. Once you’ve gotten 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 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 far more complex than that, and infrequently also they are somewhat contradictory. For example, an organization wants to seek out efficient routes, however 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 simply would never find a way 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 are far more complex than this. For example, if you should optimize a whole supply chain — as an instance, the flow of a product from the manufacturer in China through the network of various ports around the globe, 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 in addition private sector development efforts to construct tools that may eventually enable higher end-to-end supply chain optimization.