Route Efficiencies in On-Demand Delivery
Here at Postmates, we are obsessed with route efficiency. When we increase the number of deliveries a Postmate can fulfill per hour, we increase system capacity, increase fleet earnings, and improve our unit economics.
On-demand last mile delivery is extremely complex. While moving goods from point A to B seems like a simple task, it requires a platform like ours to be able to evaluate and service all potential delivery routes and product categories.
We’ve developed an elegant way of breaking down the components of efficiency, and have been continually improving our core technology which matches deliveries with Postmates. This matching algorithm is essentially solving a Travelling Salesman Problem in real time, maximizing route efficiency while adhering to customer delivery windows. We’ve innovated on top of this system by introducing Batching and Chaining technologies to create hyper-efficient routes which match Postmates with multiple deliveries heading the same direction.
In the following sections, we’ll dive into how we think about route efficiency, the matching technologies we’ve built to drive it, and how the platform will continue to evolve.
Route Efficiency
Postmate Delivery Time
Our on-demand logistics network enables anybody to trade their time for money. This time is effectively the fuel that’s used to power the platform. Given the finite number of Postmates who are online at any given time, it’s crucial that we use this fuel as efficiently as possible. By doing so, we maximize the number of deliveries per hour that a Postmate can fulfill, thus increasing average hourly earnings. We also increase the overall capacity of the network, which helps us reliably fulfill every customer’s delivery request.
Let’s define Postmate Delivery Time (PDT) as the average number of minutes it takes a Postmate to fulfill a delivery on the platform. Specifically, we calculate PDT as follows:
- PDT = (total number of minutes spent fulfilling deliveries) / (total completed deliveries)
This definition is important, as it’s generic enough to capture the efficiencies of a single Postmate fulfilling multiple deliveries at a time, which we enable through matching features called Batching and Chaining. Before diving into these technologies, it’s important to understand how we think about the fundamental time components of a delivery, for both the customer and our Postmates.
Delivery Components
When an order is created, there are a number of time segments which add up to the final delivery time.
- Ordering — the time it takes for the merchant to confirm the order
- Preparation — the time it takes for the merchant to prepare the order after confirmation
- Pick-up Leg — the time it takes for the Postmate to travel from the point of dispatch to the pick-up location
- Pick-up Waypoint — the time it takes for the Postmate to get in and out of the merchant location
- Drop-off Leg — the time it takes to travel from the pickup location to the customer’s drop-off
- Drop-off Waypoint — the time it takes to hand the order off to the customer
Our matching system minimizes waste by having a Postmate arrive at the pick-up point right as the order is ready. Thus, the Pick-up Leg happens in parallel with the Preparation Time, meaning that the Postmate Delivery Time is always less than the Customer Delivery Time. This is illustrated below.
Given the above, Postmate Delivery Time (PDT) is only affected by the following four-time components:
- Pick-up Leg
- Pick-up Waypoint
- Drop-off Leg
- Drop-off Waypoint
Increasing Efficiency
Our matching system is the brain of the network, orchestrating the assignments of Postmates to pending deliveries. This system periodically inspects the state of the world and calculates and dispatches the optimal set of assignments for each market, considering millions of potential matches in near real-time.
Each Matcher run attempts to maximize efficiency and reliability by selecting the combination of assignments, which minimizes PDT and maximizes timeliness for the entire system. In the next section, we describe how the Matcher calculates these parameters and the cost function used to determine the quality of a potential match.
By processing periodically, rather than as deliveries are created on the fly, the Matcher has a better opportunity to find a system-wide minimum. This is a classic combinatorial optimization problem, such as the Travelling Salesman Problem. Here’s a basic illustration of all of the potential solutions the Matcher has to choose from. In this simple example, we’re only trying to minimize Pick-up Leg time.
Calculating Cost
As described above, the Matcher attempts to select the combination of matches which minimizes the total cost for the entire system. For each potential match, we calculate its cost using a set of parameters and weights. These parameters include, but are not limited to, the following:
Basic efficiency parameters
- Pick-up Leg minutes
- Pick-up Waypoint minutes
- Drop-off Leg minutes
- Drop-off Waypoint minutes
Basic reliability parameters
- Pick-up early minutes
- Pick-up late minutes
- Drop-off early minutes
- Drop-off late minutes
Here are some examples of what this looks like for potential matches:
You can see in Figures 3 and 4 that when considering a potential match, the algorithm uses the set of delivery component estimates (efficiency parameters) to calculate when the Postmate will arrive at pickup and complete dropoff, thus determining the reliability parameters. As you can probably guess, our cost function uses a set of weights to boil all of this down into a scalar cost. This is necessary for comparing matches one-to-one, and enables us to tweak the weights over time as we see fit.
Batching & Chaining
Advanced Routing
In order to maximize efficiency, we’ve not only perfected the traditional solo delivery route, but we’ve also re-invented it with our Batching and Chaining technologies. These technologies enable Postmates to pick up multiple orders from one or more merchants along their current path of travel. Here’s what this looks like:
Efficiency Gains
Batching and Chaining dramatically reduces the average PDT it takes to fulfill a delivery. When sending a single Postmate to pick up a batch of two or more deliveries, three time components are shared: Pick-up Leg, Pick-up Waypoint, and Drop-off Leg. As long as the detour time between drop-offs is less than the time saved by sharing the other three components, the overall PDT is reduced. This is illustrated in Figures 6 and 7:
Had we sent two separate Postmates, the total time spent on delivery would have been 55 minutes, vs. 35 minutes in the batched case. Thus, Batching reduced the average PDT from 27.5 minutes to 17.5 minutes.
Platform-wide, we’ve found batched and chained deliveries to be over 30% more efficient than solo deliveries.
Compound Routes
As we see, the matching algorithm has three fundamental building blocks: Solo, Batched, and Chained matches. The algorithm is able to piece these together on the fly to create highly efficient compound routes. Here’s an example of how a delivery can be Chained within an existing Batch. In this example, the Postmate completes 3 deliveries in 54 minutes, resulting in an 18 minute PDT.
Challenges We Overcame
Cost function for Batching & Chaining
While Batching and Chaining provide obvious efficiency gains, the main risk is that the additional detours can result in an increase in lateness. In order to maintain timeliness, the matching algorithm has to carefully consider the pick-up and drop-off time windows and geospatial alignment for Batched and Chained deliveries. The good news is that we’ve elegantly taken care of this with the generic cost function detailed earlier.
Note that the Matching algorithm actually selects the set of matches which minimizes total cost per delivery, rather than simply minimizing match cost. This subtle difference captures the efficiencies of Batching and Chaining, thus prioritizing these efficient routes. Here’s an example of what this match matrix looks like in the case of the examples in Figures 6 and 7.
Waypoint Duration Estimates
It’s crucial that we have a good estimate of how much time a Postmate will spend at a pick-up or drop-off waypoint. Errors in this estimate result in inaccurate calculations of our efficiency and reliability parameters, as you can gather from Figures 3 and 4. Bad waypoint estimates also lead to inaccurate customer ETAs.
We’ve invested in an ML-based waypoint duration estimator which utilizes a rich set of features such as merchant history, location, and time of day. This estimator has reduced the root mean squared error by 5% over our previous estimator.
This is just one of the many estimators which we are continually investing in.
Matcher Run Time and Scalability
Given the nearly 3,000 cities in which we operate, and given the millions of potential matches which are considered each loop, the algorithm needs to run very fast. The Matcher relies on I/O to calculate travel times, making concurrency a necessity. Thus, we’ve built the Matcher using Golang due to its speed and its ease of enabling concurrency. The Matcher runs in parallel across a number of Kubernetes pods, allowing us to horizontally scale across our markets.
Additionally, we’ve built a large set of fine-tuned custom heuristics to filter out matches which we know to be suboptimal from the start. By pruning out bad matches at the top of the algorithm, we waste less time and I/O resources calculating unnecessary travel times and match costs. This also dramatically reduces the number of potential match combinations the algorithm needs to search through at the end when selecting the optimal set.
Stay tuned for a future post in which we take a deeper dive into the engineering challenges involved in making the system fast, scalable, and fault tolerant.
Next Steps
Demand Shaping
As you can imagine, our Batching and Chaining rates are heavily influenced not only by the matching algorithm, but by the properties of the deliveries which are to be matched. There are two key properties which we can leverage to shape demand in such a way that increases the probability of Batching and Chaining.
- Delivery window size and alignment
- Geospatial density and alignment
Delivery window size alignment
It’s important that pick-up and drop-off windows are as wide as possible. Short windows lead to the matching algorithm filtering out potential batches and chains for being late. It’s also important that pick-up ready times are aligned so Postmates can pick up multiple orders at the same time (we exclude batches whose pickup windows are not well aligned).
Here’s a diagram that shows some different examples of delivery windows and how they can greatly differ by the type of delivery.
As we grow delivery categories outside of hot food, we will increase the average size and alignment of our pick-up and drop-off windows. We’re already seeing this with our Delivery-as-a-Service product, which enables third parties to harness our last-mile delivery network via API.
Geospatial density and alignment
Even with large delivery windows, we won’t batch if it isn’t efficient. This is why it’s important that we have high density and alignment of pick-ups and drop-offs to increase the probability of Batching and Chaining.
A delivery has a high probability of Chaining if there exist (or if there will exist) another delivery originating from the same vicinity and heading in the same general direction.
A delivery has a high probability of Batching if there exist (or if there will exist) another delivery originating from the same merchant and heading in the same general direction.
It’s best that we increase the number of deliveries with high Batching probabilities and high Chaining probabilities. Based on real-time conditions and customer locations, we can dynamically promote merchants which would have a high chance of being Batched or Chained. Keep in mind that this would be contextual to the current location of the customer, as a popular merchant might have a high number of ongoing deliveries, but which are all headed in the opposite direction of the customer.
Hub and Spoke
As we continue to reinvent the future of delivery, we’ll be exploring alternative forms of fulfillment. One of these methods is called Hub and Spoke. In this model, walkers will pick up orders from merchants in dense blocks and bring them to a common nearby rendezvous point. Then, drivers will be dispatched to the rendezvous point to pick up and deliver large batches of pre-picked orders. This increases efficiency by enabling cross-merchant batching in dense areas, while also reducing parking time.
Note that this model can fare as an interesting use case for Serve, our self-driving sidewalk robot.
In Closing
Postmates has built matching technologies which elegantly maximize route efficiency and customer reliability. We’ve re-invented last mile logistics with our Batching and Chaining technologies, and we look forward to continuing to innovate by shaping customer demand and developing Hub and Spoke fulfillment.
If tackling these engineering problems sounds interesting to you, check out our jobs page to apply.
This post was written by Rob Moran, Director of Engineering, Fulfillment. He leads the Fleet and Logistics teams at Postmates, who are responsible for everything delivery — from the fleet product experience to the matching and market balancing technologies which power the network.
