1
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I'm going to go ahead and say there's no way in ... this problem isn't NP-complete. $\endgroup$
    – user5810
    Commented May 10, 2011 at 23:09
  • $\begingroup$ 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. $\endgroup$
    – David E Speyer
    Commented May 11, 2011 at 0:04
  • 2
    $\begingroup$ 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. $\endgroup$
    – David E Speyer
    Commented May 11, 2011 at 0:06
  • $\begingroup$ 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. $\endgroup$
    – Robert Israel
    Commented May 11, 2011 at 0:25
  • $\begingroup$ 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. $\endgroup$
    – TerryB
    Commented May 11, 2011 at 4:03

1 Answer 1

Reset to default
2
$\begingroup$

Is the routing from factory to distributor to location fixed, or are you considering optimizing this too? In particular, are there costs associated with using a distributor? If the answers to one or both of these questions are yes, then you should take at the literature on "uncapacitated facility location problems."

If the routing is fixed, then the only decision you have to make is how to pack the bags into boxes. For each route from factory to distributer you have a collection of bags, and you want to pack them optimally into boxes. This is what is known as a "bin packing problem", with "multiple bin sizes." It's NP-hard, but since your individual instances are tiny (an average of 10 locations per distrbuter), it shouldn't be hard to solve each instance exactly.

Improve this answer
$\endgroup$
3
  • $\begingroup$ In your example, none of the locations demanded more than 100 widgets. Does it happen that a single location will sometimes demand more than 100 widgets? In general, would you be willing to use multiple bags to the same location even if the bags are smaller than 100 widgets? Is there an extra cost associated with doing this? $\endgroup$
    – Brian Borchers
    Commented May 11, 2011 at 4:15
  • 1
    $\begingroup$ Although there are multiple bin sizes (300 widget and 200 widget boxes), there is no advantage (in the problem as described, where the objective is to minimize the number of boxes) to ever using a 200-widget box. So it's just an ordinary bin-packing problem. $\endgroup$
    – Robert Israel
    Commented May 11, 2011 at 5:49
  • $\begingroup$ I assumed that there would be some differential price for using the larger boxes. If not, then Robert is right that there's no point in using the 200 widget boxes. $\endgroup$
    – Brian Borchers
    Commented May 11, 2011 at 13:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .