Enhancing last-mile logistics with machine learning

Across the country, hundreds of thousands of drivers deliver packages and parcels to customers and companies each day, with many click-to-door times averaging only a few 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. This is because the last phase of the process is often the costliest due to inefficiencies like long distances between stops due 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 during the pandemic.

The vehicle routing problem is faced by pretty much every logistics and delivery company like USPS, Amazon, UPS, FedEx, DHL every single day. Simply speaking, it's finding an efficient route that connects a set of customers that need to be either delivered to, or something needs to be picked up from them. It’s deciding which customers each of those vehicles — that you see out there on the road — should visit on a given day and in which sequence. Usually, the objective there is to find routes that lead to the shortest, or the fastest, or the cheapest route. But very often they are also driven by constraints that are specific to a customer. For instance, if you have a customer who has a delivery time window specified, or a customer on the 15th floor in the high-rise building versus the ground floor. This makes these customers more difficult to integrate into an efficient delivery route.

To solve the vehicle routing problem, we obviously we can't do our modeling without proper demand information and, ideally, customer-related characteristics. For instance, we need to know the size or weight of the packages ordered by a given customer, or how many units of a certain product need to be shipped to a certain location. All of this determines the time that you would need to service that particular stop. For realistic problems, you also want to know where the driver can park the vehicle safely. Traditionally, a route planner had to come up with good estimates for these parameters, so very often you find models and planning tools that are making blanket assumptions because there weren’t stop-specific data available.

Using a traditional OR approach means you write up an optimization model, where you start by defining the objective function. In most cases that's some sort of cost function. Then there are a bunch of other equations that define the inner workings of a routing problem. For instance, you must tell the model that, if the vehicle visits a customer, it also needs to leave the customer again. In academic terms, that's usually called flow conservation. Similarly, you need to make sure that every customer is visited exactly once on a given route. These and many other real-world constraints together define what constitutes a viable route. It may seem obvious to us, but this needs to be encoded explicitly.

Once an optimization problem is formulated, there are algorithms out there that help us find the best possible solution; we refer to them as solvers. Over time they find solutions that comply with all the constraints. Then, it tries to find routes that are better and better, so cheaper and cheaper ones until you either say, "OK, this is good enough for me," or until it can mathematically prove that it found the optimal solution. The average delivery vehicle in a U.S. city makes about 120 stops. It can take a while to solve that explicitly, so that's usually not what companies do, because it's just too computationally expensive. Therefore, they use so-called heuristics, which are algorithms that are very efficient in finding reasonably good solutions but typically cannot quantify how far away these solutions are from the theoretical optimum.