New research in the Daniel J. Epstein Department of Industrial and Systems Engineering harnesses a unique algorithm to improve last-mile delivery. Image/Pexels
You’re waiting for that important package. Actively following the tracking updates, you see it’s out for delivery, and you’re the next stop. All of a sudden, you get an alert. The delivery failed and your item is back at the depot, with no word on when it will be on your doorstep.
In less than a decade, the world has become increasingly reliant on home delivery of everything from food and groceries, to consumer goods and essential medication. According to the Pitney Bowes parcel shipping index, the volume of parcels in the United States in 2023 was 21.7 billion across USPS, Amazon, UPS, FedEx and others. With the added uncertainty of traffic, weather, driver availability and countless other factors, the delivery process causes significant logistical challenges to businesses. This is compounded when customers rely on express or same-day service for critical items. The key concern is the “last-mile delivery” stage, where providers must navigate the final leg of delivery from a satellite depot or distribution center to the consumer’s door.
Recent research led by Kellner Family Early Career Chair John Carlsson and Han Yu, a recently graduated PhD student in the Daniel J. Epstein Department of Industrial and Systems Engineering harnesses a new algorithmic approach to streamline the critical final mile of delivery. Yu’s work was recently honored as an outstanding paper from the Freight Special Interest Group at the 2024 INFORMS Annual Meeting in Seattle. Yu and Carlsson’s application of related last-mile delivery work for Southeast Asian delivery company Ninja Van was also shortlisted for the prestigious Wagner Prize, honoring the application of mathematics to practical problems.
Last-mile delivery poses several challenges for companies that need to service customers as quickly and cost-effectively as possible. To do this, companies need to work out how to efficiently assign individual drivers’ workloads, ensuring they’re not making too many trips back and forth to the depot while servicing clients in densely populated areas. The algorithmic approach that Yu and Carlsson applied to the issue looks at the optimum method of dividing metropolitan delivery areas into smaller districts for each driver to service. Their process takes its inspiration from a surprising source – the humble ham sandwich.
A delivery driver carries a box. Image/Pexels.
Carlsson said that the premise of the Ham Sandwich Theorem — a theorem that has long been used in a branch of mathematics called topology — was that if a person had two slices of bread and a piece of ham, there is always a way to take a knife and slash the bread and the ham in half at the same time, regardless of their position in three-dimensional space.
“So what Han and our team did was figure out a way to say, ‘let’s use this old theorem and apply it to designing districts for vehicles.’ So we’re going to use this theorem and invent an algorithm that takes the region and divides it into a bunch of pieces where all of the pieces have the same amount of work,” Carlsson said.
In this case, the team harnessed the theorem to look at two variables – the distance to the depot and the density of customers in a given area, to ensure that driver workload was divided into equal parts.
“When we use the ham sandwich method to divide the region into different sub-regions to make sure the expected waiting time for all customers in each sub-region is the same,” Yu said.
The result is what the team describes as “spatially unbiased,” meaning that customers in one particularly dense and busy region, or those further from the depot, would not be kept waiting longer than customers closer to the depot, or in a region with fewer orders. The method also ensures a more equitable division of work for delivery drivers.
“As the number of customers becomes large, the driver workloads are all going to be balanced. So, drivers all come back at about the same time, too,” Carlsson said.
Streamlined Delivery in Action in Southeast Asia
Kellner Family Early Career Chair John Carlsson
Yu and Carlsson harnessed a similar algorithmic approach to work on delivery solutions for Singaporean company Ninja Van, which manages last-mile delivery services across six densely populated countries in Southeast Asia, including Indonesia, Malaysia and Thailand.
Yu said that when applying their work to a real-life scenario, they could not simply enact arbitrary division of the delivery regions but also needed to consider a range of other challenges unique to high-density delivery zip codes. She said that Ninja Van faced particularly high delay rates, impacting their ability to guarantee next-day delivery.
“Also there are some issues with the sorting process for when a package moves from the hub to the customer. So, for example, if one vehicle has ten packages and another vehicle has 100 packages, we need to consider a lot more sorting time for the 100 packages,” Yu said.
Yu said that when it came to a complex city like Bangkok, the team needed to integrate historical data into the model to ensure the distribution of drivers across the territory remained even.
“We can see it’s pretty dense in Bangkok, but some other areas are pretty sparse, so this means we need to put more drivers and more vehicles in this dense area,” Yu said. “But we need to consider that if we put more cars and more packages in this area, how do we balance the sorting time?”
The application of the zoning system for Ninja Van also needed to remain dynamic to respond to rapid fluctuations in demand across the areas served. The algorithmic approach made use of a Lagrange multiplier mathematical strategy — similar to surge pricing — to rezone driver areas, taking into account heightened demand at a particular location. For instance, if a customer is assigned a nearby depot, but that region is overloaded with orders, a shadow price is placed on that location.
Research co-author Han Yu completed her PhD in industrial and systems engineering – operations research in 2023.
“What Han figured out how to do is how to get an algorithm that would adjust these Lagrange multipliers, or adjust these shadow prices, to balance the workloads of all of these vehicles,” Carlsson said.
The new zoning policy was implemented by Ninja Van in November 2023, using a “treatment” area for the new zoning system, along with a control area to measure against. The team’s analysis showed that the maximum average work span across the treatment area was 6.6% lower than the stations in the control area, reducing delivery time per driver and lowering their likelihood of working overtime.
Yu and Carlsson said that they were honored to be finalists in the Wagner prize for their last-mile delivery work for Ninja Van.
“It’s an unusual approach. We’re using a lot of principles from geometry and topology, which are not research areas that you usually associate with transportation and logistics. So it’s very encouraging to see that this community has appreciated the results enough to bestow this honor upon us,” Carlsson said.
Published on December 4th, 2024
Last updated on December 4th, 2024
