Algorithm to Minimize Number of Shipments from Multiple Warehouses

Question

I have 10 warehouses across the US. Each of them may or may not have product A, B, C, D, E in stock. Someone orders all five items from my website.

I want to minimize the number of shipments I'm sending. How do I identify which items to ship from which warehouses?

For example, someone orders A, B, C, D and E.

• I have A and B (but no others) in New York.
• I have A and B and C (but no others) in Boston.
• I have D and E (but no others) in Chicago.

I'm trying to develop an algorithm that will create a shipment of three items from Boston and a shipment of 2 items from Chicago.

I don't want 2 items from New York, 1 from Boston and 2 from Chicago.

All the items are in one central database.

Answer 1

Your problem is exactly the classical set cover optimization problem, which is NP-hard; the "universe" is the set of items that the user wants, and the candidate sets are the warehouses.

The algorithm proposed by @user384706 and @Kickaha is the greedy algorithm discussed there, which is an okay approximation.

If you want to find the actual optimal solution, your best bet is to use the integer linear programming formulation and plug into some ILP solver.

You say you don't care about distances, but if you did the set cover problem also accounts for a cost per warehouse (c(s) on the wiki page) that would represent farther-away warehouses being less optimal to pick.