Optimal order fulfillment

Question

I have the following problem. A user has a cart with N items in it. There is a quantity Q of each item. Further, there are P warehouses, and each of them has a certain stock level for each product (which may be 0). Distances between each warehouse and customer are also known. I need to find a set of warehouses that can accommodate the orders and satisfies the following constraints (ordered by decreasing priority):

1. It should contain a minimal number of warehouses
2. All warehouses should be as close to customer as it possible.

Any ideas are highly appreciated. Thanks!

UPD:

If one warehouse can't fulfill some line item completely, then it can be delivered by several different warehouses. E.g. we need 10 apples and we have 2 warehouses that have stock levels of 7 and 3. Then apples will be provided by these two warehouses (to provide 10 in total).

UPD 2 Number of available warehouses is nearly 15. So brute force won't help here.

Answer 1

I would recommend to go with David Eisenstat's solution. If you'd like to understand more about the topic or need to implement an algorithm for solving integer programs yourself, I can recommend the following reference:

Chapter 9 from an MIT lecture on Applied Mathematical Programming gives a nice introduction into integer programming. On the third page, you find the warehouse location problem as an example of a problem solvable by integer programming. Note that the problem described there is slightly more general than the problem you described in your question: For your case, warehouses can be assumed to be always open (y_i = 1), and the fixed operating cost f_i of a warehouse is always f_i = 0 in your case.

The rest of this chapter goes into the details of integer programming and also highlights various approaches to solve integer programs.

Answer 2

This is solvable by integer programming.

Let items be indexed by i and warehouses be indexed by j. Let Qi be the quantity of item i in the cart and Sij be the quantity of item i at warehouse j and Dj be the distance from the customer to the warehouse j.

First find the minimum warehouse count k. Let binary variable xj be 1 if and only if warehouse j is involved in the order. k is the value of this program.

minimize sum over j of xj
subject to
for all i, (sum over j of min(Sij, Qi) * xj) >= Qi
for all j, xj in {0, 1}

Second find the closest warehouses. I'm going to assume that we want to minimize the sum of the distances.

minimize sum over j of Dj * xj
subject to
for all i, (sum over j of min(Sij, Qi) * xj) >= Qi
(sum over j of xj) <= k
for all j, xj in {0, 1}

There are many different libraries to solve integer programs, some free/open source. They typically accept programs in a format similar to but more restricted than the one I've presented here. You'll have to write some code yourself to expand the sums and universal quantifiers ("for all").