# Model for shipping widgets in an optimal way

I am a programmer and have the following requirement.

We are trying to figure out the optimal way to ship widgets. Below is the scenario:

• We need to ship 1,000,000 widgets
• We have two different size boxes. A 300 widget size box and a 200 widget size box.
• The widgets are shipped to 2,000 individual distributors, in multiple boxes.
• Each of those 2000 distributors service on average 10 locations
• There are 20,000 individual locations
• Each location calls for random number of widgets
• Location 1 requires 25 widgets
• Location 2 requires 75 widgets
• .
• .
• Location 20,000 requires 12 widgets
• The widgets are put into a bag; a bag is for one location. There can be multiple bags in a box. The box is shipped to the distributor.
• We cannot have more than 100 widgets in a bag.

What would be the most efficient way to ship as few boxes as possible?

-
I'm going to go ahead and say there's no way in ... this problem isn't NP-complete. – Ricky Demer May 10 '11 at 23:09
NP-complete isn't the end of the story. I don't understand the set up well enough to think about it, but this sounds similar to the sort of questions that people who think about transportation polytopes study. win.tue.nl/diamant/symposium0705/slides/loera.pdf In that field, when the things you are shipping are infinitely divisible (like oil), there are usually good theoretical results. When your shipping input is discrete (widgets) then the problem is often NP-complete in theory, but you can get good approximations in practice by solving the continuous problem and rounding. – David Speyer May 11 '11 at 0:04
As I said, I don't understand this question, but I'd like to leave it open until users like David Eppstein take a look at it. – David Speyer May 11 '11 at 0:06
It's not clear to me what the variables and constraints are. Is the map from locations to distributors fixed, or is it variable? If it's fixed, you have separate (and fairly small) problems for each distributor. If it's variable, what are the constraints? You say "Each of those 2000 distributors service on average 10 locations", but that could mean one distributor services all 20000 locations and the others service 0. – Robert Israel May 11 '11 at 0:25
Thanks for the comments so far and the answer below. The locations for each distributor is fixed. I am ultimately trying to figure out the best way to pack the boxes that go to the distributors. I will look into the "bin packing problem" mentioned by Brian Borchers. – user15013 May 11 '11 at 4:03