3 Questions: Improving last mile logistics through machine learning

Q: What is the issue of auto routing and the way do traditional operations research (OR) methods cope with it?

A: Almost every logistics and delivery company comparable to USPS, Amazon, UPS, FedEx and DHL faces the issue of auto route planning each day. Simply put, it’s about finding an efficient route that connects a gaggle of consumers who either need delivery or pickup. It’s about deciding which customers each of those vehicles – those you see on the market on the road – should visit on a given day and in what order. Usually the goal there’s to search out routes that result in the shortest, fastest or most cost-effective path. But fairly often they may also be traced back to customer-specific constraints. For example, if you might have a customer who has a delivery time slot specified, or a customer on the fifteenth floor of the high-rise constructing in comparison with the bottom floor. This makes it tougher to integrate these customers into an efficient delivery route.

To solve the issue of auto guidance, we obviously cannot perform our modeling without appropriate demand information and, ideally, customer-related characteristics. For example, we want to know the scale or weight of packages ordered by a specific customer, or what number of units of a specific product should be shipped to a specific location. All of this determines the time it might take you to service that specific stop. If there are realistic problems, you furthermore may need to know where the driving force can safely park the vehicle. Traditionally, a route planner had to provide good estimates for these parameters. Therefore, you frequently find models and planning tools that make blanket assumptions because no stop-specific data was available.

Machine learning may be very interesting for this, as most drivers nowadays have smartphones or GPS trackers and subsequently there’s loads of details about how long a package takes to be delivered. You can now extract this information at scale and in some automated way and calibrate each individual stop to model it in a sensible way.

If you employ a conventional OR approach, you write an optimization model where you first define the target function. In most cases this is a few sort of cost function. Then there are various other equations that outline the inner workings of a routing problem. For example, it is advisable to tell the model that when the vehicle visits a customer, it must also leave. In academic jargon this will likely be called flow conservation. Likewise, you could be certain that each customer is visited exactly once on a selected route. These and lots of other real-world constraints mix to define what constitutes a viable route. It could seem obvious to us, but this must be coded explicitly.

Once an optimization problem is formulated, there are algorithms that help us find the perfect possible solution; we call them solvers. Over time, they find solutions that meet all limitations. Then it tries to search out routes that get well and higher, i.e. cheaper, until you either say, “Okay, that is ok for me,” or until it might probably prove mathematically that it has found the optimal solution. The average delivery vehicle in a US city makes about 120 stops. It can take some time to resolve this explicitly, so corporations normally don’t do that since it’s just too computationally intensive. Therefore, they use so-called heuristics, i.e. algorithms which are very efficient at finding reasonably good solutions, but typically cannot quantify how far these solutions are from the theoretical optimum.

Q: They are currently applying machine learning to the vehicle routing problem. How do you employ it to leverage and potentially surpass traditional surgical methods?

A: We are currently working on this with people from the MIT-IBM Watson AI Lab. The general idea here is that you simply train a model on a big set of existing routing solutions that you might have either observed in the true operations of an organization or generated using one in all these efficient heuristics. In most machine learning models, there isn’t a longer an explicit objective function. Instead, it is advisable to make it clear to the model what sort of problem it actually is and what a very good solution to the issue looks like. For example, just like training a big language model on words in a selected language, it is advisable to train a route learning model on the concept of various delivery stops and their demand characteristics. Just like understanding the inherent grammar of natural language, your model needs to grasp the way to connect these delivery stops in a way that creates a very good solution – in our case, a low-cost or quick solution. Then once you confront it with completely recent customer requirements, it is going to still give you the option to literally connect the dots in a way that you simply would should you were trying to search out a very good option to find to attach these customers.

To do that, we use model architectures that almost all persons are accustomed to from the sphere of language processing. It seems a little bit counterintuitive, because what does language processing must do with routing? But actually the properties of those models, especially the transformer models, are good at finding structure in language – connecting words in such a way that they form sentences. For example, in a language there’s a certain vocabulary and that’s fixed. It’s a discrete set of possible words you should use, and the challenge is to mix them in a meaningful way. It’s similar with routing. There are around 40,000 addresses in Cambridge you can visit. Usually it’s a subset of those addresses that should be visited, and the challenge is: How will we mix this subset – these “words” – in a meaningful order?

This is, so to talk, the novelty of our approach: we use the structure that has proven to be extremely effective within the language area and incorporate it into combinatorial optimization. Routing is solely an important test for us since it is probably the most fundamental problem within the logistics industry.

Of course, there are already excellent routing algorithms which have emerged from a long time of operations research. What we are attempting to do on this project is to indicate that using a very different, purely machine learning-based methodological approach, we’re capable of predict routes which are pretty much as good or higher than the routes you’d get from running a state-of-the-art Route optimization heuristic.

Q: What benefits does a technique like yours have over other modern surgical techniques?

A: At the moment, the perfect methods are still very hungry when it comes to the computational resources required to coach these models, but you’ll be able to bring forward a few of that effort. Then the trained model is comparatively efficient at making a recent solution when it is required.

Another aspect to think about is that the operating environment of a route, especially in cities, is consistently changing. Existing road infrastructure or traffic rules and speed limits could change, the perfect automobile parking space could possibly be occupied by something else, or a construction site could block a road. With a pure OR-based approach, you would actually get into trouble because you’d essentially have to resolve your complete problem immediately as soon as recent information concerning the problem became available. Since the operating environment changes dynamically, you would need to do that many times. On the opposite hand, if you might have a well-trained model that has encountered similar problems before, it would give you the option to suggest the following best path almost immediately. It is more of a tool designed to assist corporations adapt to increasingly unpredictable changes within the environment.

In addition, optimization algorithms are sometimes created manually to resolve the precise problem of a specific company. The quality of the solutions obtained from such explicit algorithms is proscribed by the extent of detail and complexity that went into the design of the algorithm. A learning-based model, alternatively, constantly learns a routing policy from data. Once you define the model structure, a well-designed route learning model will filter out potential improvements to your routing policy from the big set of routes it’s trained on. Simply put, a learning-based routing tool will proceed to search out improvements to your routes without you having to take a position in explicitly designing those improvements into the algorithm.

Finally, optimization-based methods are typically limited to optimization for a really clearly defined objective function, often aimed toward minimizing costs or maximizing profits. In fact, the goals that corporations and drivers face are rather more complex and infrequently somewhat contradictory. For example, an organization wants to search out efficient routes while also having a low emissions footprint. The driver also desires to be secure and have a convenient option to serve these customers. In addition, corporations also value consistency. A well-designed route learning model can ultimately capture these high-dimensional goals itself, and that is something you would never achieve in the identical way with a conventional optimization approach.

So that is the sort of machine learning application that may even have a tangible real-world impact on industry, society and the environment. The logistics industry has problems which are much more complex. For example, if you wish to optimize a complete supply chain – say, the flow of a product from the manufacturer in China, through the network of varied ports around the globe, through the distribution network of a serious retailer in North America, to your store where you really buy it – it’s so many selections involved, which in fact makes it a rather more difficult task than optimizing the route of a single vehicle. We hope that with this initial work we are able to lay the inspiration for personal sector research and development efforts to develop tools that can ultimately enable higher end-to-end supply chain optimization.