Traveler Salesman in Amazon Flex

by Masatoshi Nishimura

As we dived in last in Canada Post delivery, the route is often fixed and rarely change in the system (even though new guys have to cover different routes, the routes themselves don't change for a few years at the time). Since the route is fixed, dynamic traveler salesman will not be a frequent problem. Canada Post can spend a year analyzing the most efficient route.

This time, we will look into Amazon Flex. That business is driven by temporary drivers that has dynamic routes every day. The navigation is guided by software of course. No pre-road knowledge is expected.

Let's dive in what the delivery load and routes of typical drivers look like. And see if there's a possibility of improvement.

Delivery Flow

For Amazon Flex, driving section is called block. It's like a little district you have to go around. That block ranges in about 1.8 miles. That's about 10min drive from the start to end. So it is a small area.

In that block, you need to drop off the given amount of packages under time limit. One example is 50 packages under 3.5 hours.

Within that block, each delivery address is numbered that matches with the goods. But the route is not specified. You're free to pursue whichever route is useful.

Driver Painpoint

Unlike Canada Post, no one complains about having to drive new routes every time. I assume Amazon employees expect to drive that way. In contrast, Canada Post complaint is driven by inequality. Union workers get easy routes all while they get paid more, while the new workers needing to do hard part with less.

It could be also true that the route set by Canada Post is not well designed or crafted, though this is unverified.

Difference between the two:

Canada Post

  • No timelimit. Only quota, you need to finish with over time.
  • Block time is a whole day.
  • Company provided cars.

Amazon Flex

  • Timelimit.
  • More availability.

The biggest complaint driver has is physical labor, unattended houses, stuck in congestion, and weather conditions.

Routing Issue

We now understand the drivers' reality. Let's now focus on the routing. Is there an room for improvement?

First, it's important to notice, the hypothetical traveler salesman problem is very big. It ranges to 50-150 packages a day. That's way beyond the machine limit of 24 today. However, most packages are clustered on the same street or extremely one another. Optimization over distance is minimal.

One place that can give traveler salesman a unique edge is to compute route dynamically. One of the issues was absent households. For some items (expensive ones), they need signature from the real humans. And when no one is at home, they can either flag it as failure (in which case not get paid), or come back at the end of the day to drop it off. That new route addition will mess up the beautiful compact routing block they receive at the beginning of the day.

The key here is dynamism in routing change.