Reduction of Problems

Photo by Olav Ahrens Røtne on Unsplash

At Cheetah, a rapidly growing start-up disrupting the wholesale food industry with an agile fulfillment service, our engineering team deals with an on-going conflict. On the one hand, we support a massive operation that includes inventory optimization, warehouse fulfillment, route planning, truck loading, and fleet management. On the other hand — we are an early-stage start-up, following an agile approach and trying to focus on providing simple solutions to core problems. By the way, here’s an excellent opportunity to recommend the Theory of Constraints book, where Eliyahu M. Goldratt provides some surpassing frameworks to discover what is your core problem.

The original, solved problem

For the last two years, Cheetah’s engineers developed the Delivery Service — an essential component in our platform, which aims to solve the Time-Dependent Vehicle Routing Problem (TD-VRP).

The problem statement is the following:

Minimize transport time (or completion time, fuel, CO2, etc.), while satisfying the following constraints:

1. Visit each node once
2. Return to the fulfillment center
3. Use multiple vehicles
4. Each vehicle has a capacity constraint
5. Each vehicle has service time constraints
6. Each node has time constraints
7. Each node has service time constraints
8. Drivers need to take a break (by law)
9. Fulfillment center has time constraints
10. Model traffic pattern

A solution to this problem is a set of routes, where each route assigned to a vehicle and includes a set of stops with an estimated time to arrive (ETA). We run this scheduling task every day at the cut-off time (the time we stop receiving new orders for the following day).

A visualization of a solution looks like that:

4 trucks/20 orders routing at the cut-off time

And here is how it resembles on a map:

Delivery Service Output (SFO1 — Mar 13, 2020)

The new, unsolved problem

During the operation day, many changes can occur including late departure from the fulfillment center, traffic jams, parking issues, hard-to-predict service time (unloading and receiving), weather conditions, and more. Therefore the initial ETA becomes more and more outdated as the day goes on.

To show our customers a more accurate time of delivery, we decided to work on a new feature that updates the initial ETA for all undelivered orders of vehicle T1, when vehicle T1 departures from FC, arrives at each stop and leaves it.

problem A is reducible to problem B if an algorithm for solving problem B efficiently (if it existed) could also be used as a subroutine to solve problem A efficiently — wikipedia

We defined ETA (problem A) as a sub-problem of TD-VRP (problem B), and use our Delivery Service (the algorithm), only with different input:

vehicles = [vehicle_t1]
nodes = non delivered orders assigned to vehicle_t1
departure_time = now

Using the previous visualization, the beginning of the route presented as:

vehicle T1 ETA — the beginning of the route

and at the end of the route as:

vehicle T1 ETA — the end of the route

We took advantage of our micro-service architecture, and re-use our Delivery Service without any code change. We only practiced a different perspective on our problem. In a couple of days, we delivered this feature and made our customers happier.

EAT for a specific order. in red — customer required delivery window. in green — actual arrival time. in blue — ETA