Wikipedia:Reference desk/Archives/Mathematics/2012 September 30

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 30

Bin packing problem

Hi all,

for my webshop I need some kind of algorithm, which given the size and weight limits of postal packages and the sizes/weights determines the best (cheapest) way to distribute the goods into postal packages. Does anyone know a solution for that problem? The stuff on google is filled with university-level math and allows only for one standard "bin" size... 85.181.101.47 (talk) 12:55, 30 September 2012 (UTC)

You're going to need to define the problem precisely. I assume more than one item is allowed per package, but is there a maximum number ? Do we have a table of package dimensions and shipping rates, and another of items dimensions ? Does weight matter ? Are there any rules about what must be in what packages (like refrigerated items in insulated packages) ? If the total number of items and packages is low, I suggest a brute-force method, where you try every combo to determine which is best. StuRat (talk) 16:23, 30 September 2012 (UTC)

Yes, there is more than 1 item per package, but no maximum limit (although there will be a practical one ;)); there is a table of package dimensions and the associated rates, and the list of items to be sent contains the size/weight data of each element. There's no rules about combinations of items and packages, and the orientation of goods doesn't matter in nearly all cases, so it can be left out. 85.181.101.47 (talk) 18:06, 30 September 2012 (UTC)

If they give weights for each item, that implies that there's a weight limit on each package to consider. Is there ? It would help if you could give us the exact wording of the problem, as slight variations in the setup can change what method is optimal. But, to outline a general method, you might want to sort items from largest to smallest, and place the largest item first, in the smallest package which will accommodate it, then place the second largest item in the smallest package in which it will fit, and continue through the list, trying to pack items along with other items as you go. This isn't guaranteed to give you the optimal solution, but should be a "good" one. If there's no maximum number, it may not be possible to always get the optimal solution, as calculating it would take an infinite amount of time. You might also want to create a hybrid program, which, when the number of items is low enough, does the brute-force calculations to find the optimal solution, but, when the number is too high for that, uses the method I just outlined. StuRat (talk) 04:00, 1 October 2012 (UTC)

Hard to give advice without an example of the table and typical items; I looked at http://pe.usps.com/text/dmm300/Notice123.htm but there are way too many options. If all your items come in boxes that should stay in pristine condition, and you want a way to stack them so the amount of empty space is minimised, I'm not sure if any algorithm can help you much with that. A computer controlled robot hand can stack things in order but filling a box by hand with say 40 rectangular items, based on a print-out of a 3-D arrangement seems quite challenging, and computing time might be excessive.

If you're sending items the way most Chinese webshops do it, everything wrapped in plastic foil, where the sum of the volumes is a good enough measure to know if they would fit a box, then it becomes more a knapsack problem (for volume or weight).

Usually price per unit of volume or weight is lower for larger parcels, so you'd want to use as few parcels as possible.

One possible approach would be: Start with the total volume plus (or minus) a certain percentage based on experience, find cheapest combination of parcels for the volume needed, check if largest items will fit in largest parcel (for long thin items, putting them diagonally might be an option), then use a knapsack algorithm based on the volume to fill the parcels, starting with smallest parcel (only using items whose length would fit). Verify if weight limits are respected.

In it's most general, it's a bounded multiple constraints (with m=2) multiple knapsack problem (and that doesn't include the item length), but the details would determine the best practical way to go about it. Sites like paypal offer solutions for calculating shipping costs but you'd have to integrate their system in your website I suppose. Ssscienccce (talk) 09:16, 1 October 2012 (UTC)