Q: What is the issue of car routing and the way do traditional operations research (OR) methods take care of it?
A: Almost every logistics and delivery company resembling USPS, Amazon, UPS, FedEx and DHL faces the issue of car route planning every day. Simply put, it's about finding an efficient route that connects a gaggle of shoppers 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 may be to seek out routes that result in the shortest, fastest or most cost-effective path. But fairly often they will also be traced back to customer-specific constraints. For example, if you have got 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 car 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 selected customer, or what number of units of a selected product must be shipped to a selected location. All of this determines the time it will take you to service that specific stop. If there are realistic problems, you furthermore mght need to know where the motive 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 could be very interesting for this, as most drivers lately have smartphones or GPS trackers and subsequently there may be quite a lot 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 type of cost function. Then there are a lot of other equations that outline the inner workings of a routing problem. For example, you might want to tell the model that when the vehicle visits a customer, it must also leave. In academic jargon this is normally called flow conservation. Likewise, you will need to be certain that each customer is visited exactly once on a selected route. These and plenty of other real-world constraints mix to define what constitutes a viable route. It could appear obvious to us, but this must be coded explicitly.
Once an optimization problem is formulated, there are algorithms that help us find one of the best possible solution; we call them solvers. Over time, they find solutions that meet all limitations. Then it tries to seek out routes that recuperate and higher, i.e. cheaper, until you either say, “Okay, that's ok for me,” or until it could 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 often 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 have got either observed in the true operations of an organization or generated using one among these efficient heuristics. In most machine learning models, there is no such thing as a longer an explicit objective function. Instead, you might want to make it clear to the model what type of problem it actually is and what solution to the issue looks like. For example, just like training a big language model on words in a particular language, you might want 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 how one can connect these delivery stops in a way that creates solution – in our case, a low-cost or quick solution. Then once you confront it with completely recent customer requirements, it should still give you the option to literally connect the dots in a way that you simply would if you happen to were trying to seek out approach to find to attach these customers.
To do that, we use model architectures that the majority 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 may be a certain vocabulary and that’s fixed. It's a discrete set of possible words you should utilize, and the challenge is to mix them in a meaningful way. It's similar with routing. There are around 40,000 addresses in Cambridge that you may visit. Usually it’s a subset of those addresses that should be visited, and the challenge is: How can 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 just an incredible 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 many years of operations research. What we try to do on this project is to point out that using a very different, purely machine learning-based methodological approach, we’re in a position to predict routes which are nearly 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, one of the best methods are still very hungry by way of 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 contemplate is that the operating environment of a route, especially in cities, is always changing. Existing road infrastructure or traffic rules and speed limits could change, the best automobile parking space might be occupied by something else, or a construction site could block a road. With a pure OR-based approach, you may actually get into trouble because you’d essentially have to resolve all the problem immediately as soon as recent information concerning the problem became available. Since the operating environment changes dynamically, you would need to do that repeatedly. On the opposite hand, if you have got a well-trained model that has encountered similar problems before, it’d 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 particular problem of a selected company. The quality of the solutions obtained from such explicit algorithms is restricted by the extent of detail and complexity that went into the design of the algorithm. A learning-based model, then again, repeatedly 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 seek out improvements to your routes without you having to speculate 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 far more complex and infrequently somewhat contradictory. For example, an organization wants to seek out efficient routes while also having a low emissions footprint. The driver also desires to be protected and have a convenient approach 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's something you may never achieve in the identical way with a conventional optimization approach.
So that is the type 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 way more complex. For example, if you would like to optimize a whole supply chain – say, the flow of a product from the manufacturer in China, through the network of assorted ports world wide, through the distribution network of a serious retailer in North America, to your store where you truly buy it – it’s so many choices involved, which in fact makes it a far 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.
