NVIDIA cuOpt

Last-Mile Delivery

More than 150 billion parcels are shipped each year, which is around 5,000 parcels every second (source: Pitney Bowes Parcel Shipping Index).

Transport and logistics companies are also facing multiple new challenges arising from the pandemic and the changing economic and geopolitical landscape within the industry.

As a result of these conditions, last-mile delivery (LMD) has become the most expensive portion of the logistics fulfillment chain, representing over 41 percent of overall supply chain costs for industries like retail, quick-service restaurants (QSRs), consumer packaged goods (CPG), and manufacturing (source: Capgemini Research Institute, The Last-Mile Delivery Challenge).

Based on these conditions, the challenges of last-mile delivery are manifesting as shrinking delivery timelines, profitability concerns, scaling issues, and numerous evolving delivery options.

Reducing these challenges has become critical for businesses to fully optimize the final leg of the transportation journey and reduce the total cost of delivery.

Vehicle Routing Problem

Consider the Vehicle Routing Problem (VRP), which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" It generalizes the well-known traveling salesman problem (TSP).

Operations Research (OR) and logistics issues at greater scale are incredibly compute intensive with massive operational costs. As the number of destinations increases, the corresponding number of roundtrips surpasses the capabilities of even the fastest supercomputers.

With 10 destinations, there can be more than 3 million roundtrip permutations and combinations. With 15 destinations, the number of possible routes could exceed a trillion.

Adjusting for changes in these parameters due to inclement weather, a driver out sick, vehicle maintenance, and new orders greatly increases the scope of the problem.

Anatomy Of The Routing Problem

In this simple food delivery example, a pizza shop is planning to deliver pizzas to four different addresses, then return to the store. The problem is represented as a graph with five nodes, including the depot (pizza shop). The edges represent the ability to go from one location to the other with a given cost. The solver supports multiple cost or weight dimensions (eg. distance and time). Costs could be asymmetric and triangle inequality compliance is not required. From there, the pizza delivery application models and solves the problem through the following steps:

1. Query a mapping app to determine the distance between any two addresses in this list.
2. Pizzas must be delivered to customers within defined time windows. This is encoded into this distance matrix and constraint tuple. The transaction time and the number of pizzas per address are also encoded.
3. Encode the fleet information into a second tuple with vehicle properties (weight capacity). The number of capacity dimensions is arbitrary.
4. Pass the result to NVIDIA cuOpt to discover that the optional approach is to send one driver to locations one and two, and another driver to locations three and four.