A Simple, Elegant Mathematical Structure at the Heart of Fulfillment Supply Chain

This has been an article based on an observation I made a long time back but never had a chance to write it up. If you have read my previous articles, you may know my fondness to appreciate simple but elegant properties which then lend themselves to writing simple, elegant but powerful pieces of software and this is another illustration of the theme from the real-world.

As you may know from previous articles, Onera is in the business of making Omnichannel fulfillment programs such as Ship-from-Stores (SFS) simultaneously more profitable while also increasing customer satisfaction. In this essay, we focus on the fulfillment part of the supply chain where an order has been taken online by a retailer to ship to a customer and the retailer needs to decide which set of stores to use to fulfill that order. To add to the complexity, as noted in previous write-ups, the best that we can do is attempt to fulfill an order from a store. But the reality is that the store associates may be busy at that time, the item may not be in the store in an accessible location etc, and so a certain time window may pass and the software algorithm needs to decide to switch to try another store. Therefore, we have fulfillment proceeding in rounds with each round being an attempt or probe to fulfill an item from a store and that attempted probe may fail and the algorithm retries with a possibly different attempted probe.

For simplicity, we will restrict ourselves to a single item fulfillment in this write-up and multi-line items, which is typical, adds much more complexity. To formalize the problem and the solution, we will use the following notation.

Let {1,..., J} be the set of stores, {1,..., L} be the set of fulfillment rounds. Let pj be the probability of probe failure at store j for this item which we assume already has been estimated for all stores, sj be the cost of shipping from store j to this customer, cj be the cost of handling (labor cost) charged for every attempted fulfillment probe at store j and C be the cost incurred if all L rounds of fulfillment probes fail.

Therefore the total cost incurred during fulfillment if it was successfully fulfilled would be the sum of cj for every attempted fulfillment at every store attempted plus the final sj for the shipping cost of the store from which we shipped the item. If we failed to fulfill within L rounds, then we will be charged with a substantial cost of C.

As a software engineer, how would you solve this problem? If you think about it for a while, the only solution that may come to your mind would be a large decision tree of all possible ways of exploring fulfillment. This would go as follows: we can try (every possible) Store a first and that will incur cost ca, then if it succeeds, we have cost sa but it can fail with probability pa in which case we would try b, etc. In other words, this decision tree would have L levels and about J options at each level, for a total exploration time of O(J^L). If you have say 500 store locations (quite typical), and 5 levels, thats more than 31 trillion options to explore and then pick the one with the least expected cost of fulfillment.

It feels incredibly hard to do better than that while still guaranteeing to find the best fulfillment plan. You can go down the path of cutting that decision tree down on the fly etc but as always better to spend the time planning (and testing) to write software than writing software with insane optimization of corner cases (if we have 6 hours to cut a tree, we'd rather sharpen our axe for 4 hours).

We stared at this problem for a while and this is when a beautiful mathematical structure presented itself hidden underneath.

Let us suppose that the perfect optimal algorithm decides to use f1, ..., fL as the series of locations to try to fulfill that item. Let us suppose we offer it the flexibility to even re-try at the same location twice in that series (maybe the store was busy first time). Then the cost of fulfillment can be written as the following expression (bear with me, its not that complicated and explanation to follow):

The above expression, just formally writes what we already know and have informally stated before. We first sum over the number of rounds accounting for costs per round with the associated probabilities. For a round l, we arrive at this round with the probability denoted by the product sign with every preceding round failing to fulfill and then we have expected cost c + (1-p) s charged for the fulfillment attempt at the store and the probability that it succeeds in which case we have the shipping cost. If all L rounds have failed, with associated probability shown on the right, then we charge cost C. For simplicity, we add two more notations. Let Cj = cj + (1 - pj) sj and rj = Cj / (1 - pj). Note that, Cj just combines the expected shipping and labor cost into one term.

Then it turns out that rj is the magic structure ratio that combines all three parameters of shipping cost, labor cost and fulfillment attempt probability into a single simple ratio with the beautiful structure below. More formal proof below and intuition further below in case you get overloaded.

Structure Theorem. The optimal fulfillment algorithm will never contain a pair of adjacent fulfillment attempted probes, fq and f(q + 1) such that r(fq) > r(fq + 1).

Proof. For the sake of contradiction, let us suppose that it is indeed optimal to consider f(q) and f(q + 1) even though r(q) > r(q + 1). We can now decompose the fulfillment cost into levels before q and levels after q + 1, neither of which are critical to this proof, since we focus on the all important q, q + 1 levels for the sake of contradiction. So we decompose the fulfillment cost above as

We can rewrite the all important q, q + 1 levels as below leaving the prefix and suffix terms untouched.

By our assumption, r(fq) > r(fq + 1) and therefore by definition,

Therefore, if we were instead to probe f(q + 1) followed by f(q), it would have a cost lower than what the optimal algorithm did, a contradiction. QED.

Intuition. First, let us draw our attention to something we have ignored all along, which is cost C, the final cost when all probes have failed. The reason the above proof works is because swapping the order of the probes q and q + 1, has no effect on the probability of incurring cost C. This should raise alarm bells since your intuition should be screaming that probing low failure probability stores first, should in fact be much better than probing high failure probability stores, so saying swapping the order has no effect on final cost C does not make intuitive sense. But here is why intuition is leading us a bit astray there. Yes, indeed probing high probability stores will make us less likely to incur cost C. However, conditioned on fixing the set of stores we are going to probe on our algorithm, means that the only way we incur cost C is if both probes fail, and therefore it really is agnostic to the order in which you probe them. This is why our magic ratio rj is in fact completely agnostic to C. Now, intuitively if we can prove the above theorem at first two levels, then it is likely to work across all levels. The first two levels terms are c1 + (1-p1)s1 + p1c2 + p1(1-p2)s2. We are simply asking when is c1 + (1-p1)s1 + p1c2 + p1(1-p2)s2 > c2 + (1-p2)s2 + p2c1 + p2(1-p1)s1. The rest is just collecting (1-p1) and (1-p2) terms and performing algebra.

This is a beautiful structure because now we have an incredibly simple and easy way to eliminate most of the sequence of fulfillment probes we need to evaluate. Specifically, we can simply sort every store by our magic ratio, r(j) and we know that we just need to examine those in sorted order to find the best series of fulfillment locations! We have reduced our search space from 31 trillion to simply a few thousand without compromising one tiny bit on optimality since we know that the optimal solution lies within this sequence. Hint: we can do this very efficiently (by some very weird coincidence), an idea similar to the classic knapsack dynamic program.

Once again, very simple code, much easier to implement and maintain and absolutely no loss in optimality. The only complexity if at all any lies in the underlying math which is just for your own proof and has no bearing on the actual software code itself that can be implemented.