Amazon delivery trucks 🚚

Scenario

Amazon Prime Now has 17-hour long days during which it deploys its fleet of trucks. The Order Forecaster for a region is really good at what they do and can give the exact number of trucks needed during each hour block for the coming day. The forecast schedule is in the form of a 17 element array. We can only deploy (add) trucks at the very beginning of the day, and any leftover trucks at the end of the day are automatically sent to maintenance. How would we algorithmically maintain a minimal service fleet? For example if the required number of trucks is forecasted as:

The optimal decommissioning schedule is:

Our job is to deploy trucks and coordinate with maintenance to decommission trucks that are not needed for the rest of the day. Once a truck is decommissioned, it won’t be available until the next day starts. Given the forecaster’s schedule, we need to keep a minimal number of trucks in service to fulfill the rest of the day’s deliveries, but send back (subtract) any trucks to maintenance as soon as we can. We’ll come up with a schedule to tell them how many trucks to decommission at the start of each hour.

In the example, we start off by adding 5 trucks into delivery. Observe that while we need only 3 trucks during the 7th hour, we’ll need 4 in the 8th hour. So we can remove only 1 truck at the 7th hour to keep at least 4 trucks in service for hours 8 and 9. For the 10th hour, we can decommission 1 truck, leaving 3 to make deliveries. In the next hour we remove 2 trucks, leaving the final truck required to make rest of the day’s deliveries.

Approach

We have many different regions to manage and can really give each forecast only one pass through to come up with the precise corresponding deployment/decommisioning schedule. We can do this by reading forecast backwards: at very end of the day where demand is 0 (all deliveries are done), then iterating from the last hour of the day and reading each previous hours one by one to the beginning of the day. Keeping track of the highest demand so far, look at each hour, and subtract the current demand from the highest, if we get a negative value, then that is the number to decomission in the hour+1, if highest minus current hour’s demand is positive, then we don’t decommission any trucks because we know they’ll still be in use in the future. Update the highest demand by taking the max of (current hour’s demand vs. highest demand). Then continue through the iteration. The very first hour is finally set to the highest demand.

Analysis

The time to do this scanning approach is linearly proportional (O(n)) to the number of hours in a day (e.g. 17). An alternative that will take O(n^2) is iterate over the forecast list starting at the beginning, then at each hour, iterate over the rest of the list again to find the max and deciding whether to keep the fleet count same or if it’s ok to decomission as much as needed to maintain the current max.

import random
def forecast():
    for _ in range(17):
        yield random.randint(5,20)

Let’s check the forecast.

random.seed(6449)
print(list(forecast()))

[19, 20, 17, 14, 6, 6, 13, 7, 20, 8, 17, 7, 10, 15, 11, 10, 5]

Now that we have the forecast, let’s do it!

random.seed(6449)
most = -1

# Get the entire days demand's
demands = list(forecast())
print(f"Entire day's demands:\n{demands}")

# We'll build the decomissioning list from the day's end and adding each earlier hour back to the beginning of the day
decomissions = []
i = -1
end = -len(demands)
most = max(demands[i], most)
while (i > end):
    i -= 1
    decomissions.insert(0, min(most - demands[i], 0))
    most = max(demands[i], most)

# Finally, add the number of trucks we'll start the day off with
decomissions.insert(0, most)
print(f"Service list:\n{decomissions}")

Entire day's demands:
[19, 20, 17, 14, 6, 6, 13, 7, 20, 8, 17, 7, 10, 15, 11, 10, 5]
Service list:
[20, 0, 0, 0, 0, 0, 0, 0, 0, -3, 0, -2, 0, 0, -4, -1, -5]

And to verify this approach gives the desired optimal schedule, I check against the orignal example forecast

# Get the entire days demand's
demands = [5,5,5,5,5,5,5,3,4,4,3,1,0,0,0,0,1]
most = -1
print(f"Example entire day's demands:\n{demands}")

# We'll build the decomissioning list from the day's end and adding each earlier hour back to the beginning of the day
decomissions = []
i = -1
end = -len(demands)
most = max(demands[i], most)
while (i > end):
    i -= 1
    decomissions.insert(0, min(most - demands[i], 0))
    most = max(demands[i], most)

# Finally, add the number of trucks we'll start the day off with
decomissions.insert(0, most)
print(f"Service list:\n{decomissions}")

Example entire day's demands:
[5, 5, 5, 5, 5, 5, 5, 3, 4, 4, 3, 1, 0, 0, 0, 0, 1]
Service list:
[5, 0, 0, 0, 0, 0, 0, -1, 0, 0, -1, -2, 0, 0, 0, 0, 0]

What ifs…

• Forecast lists had variable length because the time resolutions are different? The service list length would have to change accordingly.

• We had 24 hour rolling forecasts, updated with each new hour? The service fleet may have to have be more conservative in decommisioning and have some extra reserve trucks to “cushion” demand in case the last downstream demand increases.

• Maintenance speed improves and we can put trucks back into service after 2 hours? There would be another function to deposit trucks back into service simultaneously with how many would have been decommissioned.

🐱‍👤