24

I've received a task to build a shipping estimative that suggests the best accomodation of goods on as few boxes as possible:

  1. There is a finite set of known retangular box sizes

  2. There are many arbitrary retangular item to be packed inside boxes

  3. The fewer boxes should be used the best. Because shipping two boxes 1x1x1 is way more expensive than one box 1x2x1. This should be the priority here.

  4. It should also be optimized to use the smaller boxes as possible, as a second level priority. (eg.: if presented with a choice between one bigger box and two small, it should choose the bigger box)

  5. Items can be rotated to fit the box, but the rotation have to be limited to increments of 45° at a minimum (in my researches it seems that some configurations allow for a 45 degrees rotation to better fit retangular boxes inside a bigger retangular box), being 90° rotations the standard to be taken.

  6. Boxes have a weight limit and items have arbitrary weights (eg.: an item that is size is 1x1x1 can be havier than other 2x2x2 item)

I've researched a bit and found some abstracted algorithms on bin packing and the knapsack problem and came with the following somewhat bruteforce variation, similar to the best fit algorithm:

  1. Sort the items in decrescent volume order (bigger first) on an "items to pack" list

  2. For each item on this list:

    1. Choose the smaller box that is on the "used boxes" list and has enough remaining volume and weight limit to fit the item (I will use fit here to mean fitting the dimensions and weight)

    2. If there is not such box, create a new box from the know set of possible box sizes that is the smallest size that can fit the item's dimensions and weight and add it to the list of "used boxes".

    3. If a box fits the item (using the fitting function bellow), add it to the list of "this box's items" and remove it from the "items to fit" list, marking it's relative 3d position inside the box.

    4. Repeat from 2.1 until there is no item to be fitted on the "items to pack" list.

The fitting check function used on step 2 above:

  1. Check if the remaining volume of the box fits the volume of the item. If not, return false.

  2. Check if the sum of "box's items" weight plus the current item weight is less or equal to the box weight limit. If not, return false.

  3. Check the "box's items" list to choose the first box coordinate that has the smallest Y component and that has enough space for the item's width, depth and height, considering the other items placed as unavailable space.

  4. If the item doesn't fit at it's current orientation rotate it on one of the 6 possible rotations, not assuming 45° rotations for simplicity. (Rotations that result in sizes that where already tested can be skipped. Eg.: rotating a box 180° gives the same dimmensions as the original position because all boxes and items have the same size for opposite faces and so can be skipped.)

  5. If the item hasn't been rotated on all the possible ways back to its original orientation, try again from step 3.

  6. If all rotations where tried and no fit was found, consider the current coordinate as unavailable space.

  7. If there is not avaliable space to check, return false. Else, try again from step 3.

I want to know if there can be a best solution to my problem, given the presented constraints.

This seems to work on theory but I've not tried it on code. I wish to know if I'm going in the right direction or there are better, performant ways of doing this.

References would be great.

Edit:

I've found some interesting 3rd party API that do what I want, but this will have to be disconnected, so I will not have access to these.

Some examples are:

Edit 2:

A real world example of problem to solve would be:

  • I have 4 box sizes WxHxD: 10x12x18, 12x16x24, 16x20x30, 24x32x40
  • I have an order of 4 items, being 1 of size 6x8x10, 2x 22x14x30 and 1x 22x4x20

How do I fit this items into any amount of boxes of one or more sizes using the fewer boxes as possible, using the smallest boxes possible and leaving less free space as possible?

  • 4
    There is no need for a packing-related tag; algorithms suffices :) – Chris Cirefice Oct 3 '14 at 16:14
  • I'm curious, will the actual packing be performed by robots or humans? If it's the latter, is the space optimization going to be worth the time required for figuring out how to rotate each box to fit it in? – foraidt Oct 8 '14 at 5:58
  • Good question. The actual packing will be done by humans, but the software will suggest the packing order and position of each box. It will not require experience in packing to look at the layout provided and place the goods inside the box. At first, some time will be spent in get used to it, but it will not require thinking on the best disposition. – Ricardo Souza Oct 8 '14 at 12:37
  • 1
    I think all @msw is saying is that this type of problem is unlikely a good fit for a "perfect" solution, but rather a better fit for an acceptable solution found in a reasonable amount of time with heuristics based on the rules you've provided. From a mathematical viewpoint, this often means you approach it with a different set of algorithms and tools, so I think he's just recommending that. For example, genetic algorithms, simulated annealing, and other methods of following a gradient descent curve approximating the solution space with respect to your heuristic might provide benefits here. – J Trana Oct 9 '14 at 3:50
  • 1
    I'm posting just an idea here. In case you don't think it will be effective you can ignore it. This solution (it is more like an optimisation) really depends on how similar the input of your algorithm will be. So exploiting the fact that your input will have some similarities over time. You can store/cache the calculated results (which have an expensive calculating complexity), then compare them with your input and if you have a full match or a partial match you will only need to do a few calculations to reorder some minor size objects. Of course this causes new problems to rise. – JAAAY Sep 22 '18 at 16:10
4

Bin packing is very computationally difficult. Think of half of the problem: you want to pack product in shipping boxes with no wastage in the box. An optimal solution for that would require going through all possible subsets and all possible 3d arrangements of the product that needs to ship in one truck. I'll give you the optimal solution for that because I have a friend who does six impossible things before breakfast.

Now you just have to get all the boxes on the truck with no wastage. My friend does his second impossible thing and gives you the solution. Unfortunately, with the box sizes you selected above, there is empty space in the truck which could be reduced if you'd chosen different (either larger or smaller) boxes in the first task. If you change the size of one box, at best you'll have to re-pack the truck; at worst, you may have to repack all of the boxes which is just as hard as the problem we started with. And, as with the first stage, you'd have to try all possible 3d arrangements.

I found Skiena's The Algorithm Design Manual to be helpful for thinking about what class of algorithms suit which sorts of problems, but I mostly learned that good solutions for even mundane problems blow up in you face with computational difficulty. Most of what you are needing fit into the class of bin-packing problems and that article is a good jumping off point. It is worth noting that some of the best algorithms for this are commercial products because this task pops up everywhere in logistics (what's the smallest number of train cars can I get my goods into? and such). There is considerable money to be made if the right heuristics can save a manufacturer 100 train cars a month.

Unfortunately, the literature on optimizing heuristics isn't nearly as large as for algorithms. If you try to go it alone, I guarantee that you'll be dreaming about moving rectangular prisms around by your second month. I had a cutting-stock problem that if I had to do again I'd probably farm out to the experts (or their propriety software).

Thanks to @JTrana for the fine expansion of my comment.

  • Thank you for your feedback. As I've said on the question, I've already researched about this subject and came upon a mix of a few algorithms to propose that one above. I'm concerned only about the packing itself. All this boxes will be sent via posting office services. Fortunatally, I will not have to deal with truck loading. – Ricardo Souza Oct 10 '14 at 14:01
  • That was a goodly part of my explanation. You can't "extract" the algorithm from firms who want you to pay for their service. The two firms you listed have an API, but the packing is done on their servers and you have no access to the implementing code except by theft. And it is good that you don't have to pack the trucks, now your problem is only half as difficult which is why firms want to sell you a solution and people are willing to buy the service. – msw Oct 10 '14 at 15:40
  • 1
    I think we have a miscomunication here. I may not have expressed me well (as you may have noticed, English isn't my home language). I'm not asking for stealing the algorithms. I've came here for clarification on the subject. I've done some research and put it on the example above for analisys. Maybe there is someone that came upon the same problems that can give me some better directions. If my solution isn't applicable, what I can do to get better results? This is my real question up there. I hope I've made me clearer now. – Ricardo Souza Oct 10 '14 at 19:28
  • Your English is fine; I think the problem is that we are talking about different layers of the task. You are thinking implementation and I am thinking combinatorial explosion. I think solving your Edit 2 will help you better understand the problem from the way I'm looking at it. Can you solve that as stated? Without wastage, with a minimal number of boxes of the minimal size? That's the multioptimization problem I mentioned before which I said is impossible to do: you will have to sacrifice at least one of those factors to optimize another. – msw Oct 10 '14 at 20:07
  • Thank you. I think I got it now. I didn't tried to code it. I was thinking in not wasting time coding before a more concrete solution or at least a positive feedback over my proposal arise since this is, at first, for a quotation. I'm still researching but I'm afraid I'll have to get one of those APIs and see if the devices (data collectors running Win CE 6.0) can run connected to the internet. The first info I got from the client stated that they will not have internet access on the workplace. – Ricardo Souza Oct 10 '14 at 22:33
1

When creating new algorithms, and I recently just did a packing algorithm by myself (I know it still has some optimization potential), I always do the most simple approach:

How would I as a human do it, and try tro translate it into an algorithm: From my (robotics) AI teacher Rolf Pfeifer I still bear in mind, that apparent intelligence sometimes may be created with some very simple rules, so instead of overengineering I try to underengineer

  1. Identify too big items (items which do not fit in any given box)
  2. Try to find the best box possible (by cross comparing total volume and item dimensions)
  3. Order items from big to small and boxes (spaces) from small to big
  4. Fit biggest item into smallest possible space
  5. If biggest item does not find jump over it and try next one until nothing more fits
  6. For the remaining items, search new best box. ...

    X. always think about exceptional events (oversize items, strange forms, if a box contains only 1 item wouldn't it be better to send item without box?, etc.) but you can make a heuristic also in a form of a decision tree.

Off course there are further caveats the further you get, I just give these ideas as a starting point. From there there are lots of ways possible. One alternative would be to divide a box into little cubes (e.g. 5cmx5cmx5cm) and track them as occupied/free another approach could be called 3d tetris, etc.

With this approach you don't have to necessarily worry about combinatory explosion. At the other hand, combinatory explosion could happen if we're talking about trainloads of items, but then again: Do you really think a company will check the packing list item by item? No they'lll approach a divide and conquer solution: Divide complexity by using standardized volumes (e.g. palets, or fixed sized boxes). So even for practicitys sake, take into account that not only trains, sometimes employee's time is money too. a train can load x palets, every palet has fixed volume, so pack items into palet, but then again, perhaps a palet consists of several order, so use fixed boxes for the items, which then are loaded into palets, which then are loaded into trains.

At least that's how I as a human would deal with the task, get best box and then fit biggest item one by one in smallest space available (and add a little bit of preview).

As in my algorithm, in the end you probably won't have the best solution, but a farily good heuristic which you then can further refine.

Sometimes it's easier to start with the first step and clear out problems on your way, well off course ideally not a kind of step over the edge step, but a little bit smart... sometimes you may be forced, to explore alternatives and choose the best one or implement an "step back".

But as I learnt from my AI teacher (Rolf Pfeifer, sorry to bother with that again): Sometimes you can create apparent intelligent behaviour with some very simple and few rulesets > emergent behaviour in the example mentioned they programmed little remote cars to turn left if they detect an obstacle at the right side, turn right if there's an obstacle on the left side and go straight if there's no obstacle or if the obstacle is in front. 3 or 4 robots as that, put in a 3m x 3m square with lots of ping-pong balls lead to the amazing fact that the robots seemed to be cleaning up, pushing the ping-pong balls to the corners, even though the robots are only programmed to avoid obstacles.

PD: The only real-world deviation I found from this approach is when I was part-time working as a stagehand for big concerts as metallica, iron maiden, britney spears, paul mcCartney, U name it... The truckers working on the international tours have precise packing lists item by item. The calculations gets done once (I don't know by humans or machines), and then replicated. Sometimes when they pack the first time, they even make layer by layer pictures and stick it within the truck just so that local crews know exactly, which box has to be charged when and where. But this is also a specific packing need as for one tour they always work with the same boxes and trucks.

1

The heuristic that you mention in your post seems interesting.

I would suggest a couple of modifications in order to improve the final solution.

Given a solution with all items packed in one box, try to merge together the contents of two small boxes in one larger box (this should help in improving your criteria of using as few boxes as possible).

Alternatively, every time you start a new box, instead of using the smallest box that can accommodate the current item, you could pick the largest box that can accommodate it, and once every item is assigned to a box, try assigning all items of a box to a smaller box.

Also, in your fitting function, instead of considering the position of your other boxes as fixed, you could imagine changing the loading sequence. This should let you find better solutions at the expense of a longer running time.

  • That seems interesting improvements. I've not touched this problem for a long time. Maybe I should give it a try one of this days. Thanks. – Ricardo Souza Apr 25 at 21:04

protected by gnat Sep 22 '18 at 19:28

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.