Why your packages arrive too late: the challenges (and solutions) behind last-mile delivery.
We all know this feeling. You have ordered a gift for your mother via Amazon. It’s Thursday morning. Since you don’t want to disturb your neighbors again, you have decided to stay home. You open the app of the parcel delivery service. It shows that the driver will arrive between 10:00 and 12:00. Perfect! Now you can catch up on some work and get lunch afterward.
It is 12 o’clock. The package has not been delivered yet. You wait another half hour. Then you decide to quickly leave your house to get a sandwich and a coffee at the new place around the corner. When you arrive back, you find a note in your letterbox saying the driver missed you. It cordially states that the package will be delivered to a pickup point tomorrow. Oh no!
How is this possible? You have been waiting the entire morning. And just when you left, the delivery person had to come by. ‘Why did I stay home at all?’ you ask yourself. Working in the office would have been much more convenient. ‘But why was the driver late in the first place?’ If the delivery person had been on time, you’d have your package in your hands right now.
Naturally, you bring out the true analyst in yourself. The delivery person may be late due to the high workload. That means there are more things that can happen on the road. Therefore, the delivery driver may arrive a little earlier or later than initially expected by the parcel delivery app. ‘A 2-hour time window should be wide enough to accommodate this, though!’ You think out loud. If it is not enough, what can be improved in the delivery prediction app?
You can only draw one conclusion. The driver deviated from the route the delivery app had in mind. ‘Otherwise, the driver would have been on time for sure.’ In practice, delivery drivers are usually free to deviate from any suggested route. This is because drivers usually know details about the neighborhoods they are driving in which may affect the routes they chose. This additional information is usually missing in the delivery prediction apps. Apparently, it must be hard to predict driver behavior. Or at least, people don’t know yet how to do it well.
This problem, of predicting the actual routes the drivers choose, is difficult. It’s so hard, that Amazon organized a challenge in collaboration with MIT: the Amazon Last-Mile Routing Research Challenge. The prize money is huge: $175,000. Based on roughly 6,000 historical routes, a total of 3,072 new routes must be predicted. The performance is determined based on how much these predictions match the driven routes. The best-performing team received $100,000.
Why is this problem so difficult that Amazon dedicated a challenge to it? To figure this out, it is required to first dive deeper into the problem.
A look into a delivery driver's day
On a typical morning in July, in Tacoma, Washington, our delivery driver Elisabeth arrives in her battered white van. At the station, she finds a bunch of packages to deliver, each belonging to a different address. Now Elisabeth has to come up with a route, that is, the order of stops to visit. Ideally, this route should be efficient in some way; it is certainly not desirable to drive the entire route back and forth between streets.
Elisabeth already has an idea in mind: she would like to find the fastest possible route that goes to each address exactly once before finally returning to the station. This task is a well-known mathematical problem, namely the Traveling Salesman Problem (TSP).
The TSP is a very difficult problem to solve; especially when the number of stops to visit is large. Too bad! Elisabeth’s idea might not seem feasible. Luckily, Elisabeth can use Google Maps to generate one of the fastest routes available. But, from her experience Elisabeth does not like this computer-generated route and decides to follow the route she feels is better. What do you think? Will these two routes be similar?
Below is a comparison between the route prescribed by Google Maps and the route taken by Elisabeth.
The route prescribed by Google Maps.
The actual route taken by Elisabeth. You can use your cursor on the map to move it and zoom in or out.
Surprisingly, Elisabeth didn’t follow the route that the navigation app suggested to be the fastest. Even though Elisabeth is free to deviate from the prescribed route at any time, what could be her motivation to do this? Elisabeth can tell us the answer.
Elisabeth has much better local knowledge of the neighborhood. Also, parking availability and traffic congestion make Elisabeth deviate from the suggested route. ‘For example, I know which schools should be avoided around 8:30 and 15:00. Such factors are not taken into account by Google Maps,’ says Elisabeth. ‘I can imagine it is hard to find routes that take my street knowledge into account and are not only faster in practice but also more efficient to drive. Perhaps you can better predict the route that I will follow by looking at how this area has been driven in the past few weeks?’
Knowing that thousands of drivers like Elisabeth work every day for the delivery service of Amazon, it is highly desirable to find an automated way to prescribe routes that are actually followed by the delivery drivers. Also, as the full set of addresses to visit can be unknown until the drivers load their packages into their vans, a feasible route should be computed within a couple of seconds. Otherwise, it would not be possible for the driver to immediately follow the prescribed route.
Together with two other doctoral students from the Amsterdam Business School at the University of Amsterdam (UvA), I was stimulated by Elisabeth’s idea. And so, we decided to try to tackle this very problem and see if we could win the Amazon challenge. From now on, I will elaborate on the approach we have taken.
Benefiting from the knowledge of the drivers
Since solving a TSP is in general very difficult, we need to break down the problem to obtain a solution within seconds. One way to do this is using a divide-and-conquer method. In such an approach, the problem is split into multiple subproblems. Next, each of these problems is solved separately. Together they form a solution that is not necessarily the fastest route but at least has much lower computational complexity and therefore can be found much faster.
Let’s find a solution that makes use of this idea. First, we need a clever way that breaks Elisabeth’s service area down into smaller regions. To accomplish this, we will have a careful look at what data Amazon actually has at its disposal.
First of all, the data contains a number of routes driven in a region in Washington. The region is already divided into small subregions, called zones. Each possible stop is located in such a zone and a route contains several zones. Typically, drivers prefer to visit all stops within a zone before moving to the next one. Hence, it seems unlikely that drivers return to a zone after they left it.
We conclude that the divide part is already done by Amazon. The next goal is to first find the order of these zones to visit, after which the stop order within each zone can be conquered.
The zone sequence will show a global route that includes the general directions that Elisabeth will follow. To find such a sequence, we need to reduce each zone to a single location. This can be done by choosing the address in the route that is closest to the zone center. With the travel times between these stops readily available, the TSP framework can be used to find the order of these specific stops, and therefore the zone sequence.
But this is not yet enough. If we solve the problem in this way, we still do not adopt the historical routes in this region. On the other hand, using history alone may not lead to the desired outcome. For example, certain zones may not be visited very often because few people live there. We need a combination of both history and travel times to predict the order of zones Elisabeth will follow. The more it is observed that drivers moved from one zone to another in the past, the smaller we make the travel time between these particular zones.
Having found the zone sequence in a way that also incorporates history, a full stop sequence is obtained by solving another TSP within each zone. As the number of addresses to visit within a zone is much smaller than the total number of stops to visit, this can be done relatively fast. To add some sense of direction, the TSP starts at the last stop of the previous zone and ends at a stop of the next zone. As these additional stops are not part of the solution, they are removed afterward.
Now we have found a two-step method that can generate an entire route given the addresses to visit. But how well does it perform in the Amazon challenge? It led to 12th place during the challenge, but minor tweaks show that the performance can be improved up to second place! A picture of our prediction corresponding with Elisabeth’s route can be found below.
The predicted route.
The actual route Elisabeth has taken.You can use your cursor on the map to move it and zoom in or out.
The route that Elisabeth is taking can be predicted quite well! As Elisabeth now happily delivers your parcel in the predicted time window, you are wondering if you can treat her to a cup of coffee at the new place around the corner. Well, at least you know now when she’s going to ring your doorbell next time…
Recently there has been a breakthrough in the field of algorithms for geometric network problems, concerning the complexity of the Euclidean Travelling Salesman Problem.
Suppose you have a delivery service. You have one truck and have to deliver a large number of parcels to different cities in the country every day. Then you run into the following problem: in which order should you visit the cities?
. Suppose you are coming to the Netherlands for the first time, you want to enjoy your time in the country in the best possible way and probably visit and see as much as possible. So you rend a car and you decide to travel around. But now the challenge begins, planning such a trip!
What if I tell you that long queues in airports are also caused by the impatient passengers that arrive too far in advance at the airport? Today, we will analyze how the organization of the security check queue affects the waiting time of passengers.
