Posted on 2006-11-02
Last Modified: 2013-11-12
Ok well here is the scoop. My boss laid a project on me that is pretty much... hasn't really been done before? At least that's the impression I get when I try googling it.

He wants me to make an automated packaging system. Meaning the system knows it has boxes of a certain dimension and size, and then you have a set amount of products and their dimensions. Well it needs to determine the best way to package the products in order to use the least space possible. And there should never be a small item just in a box by itself, the packages should be "weighted". What I mean by weighted, is that if you are going to be forced to use a second box, simply cause of one or two products, then even the boxes out to make the load lighter for each box.

Basically, it should replicate someone who has been boxing packages their entire life and knows the best way to put items into boxes.

The basic layout I have so far is a class Box that has the width, height, length, and contents (triple subscripted array to simulate each 1in x 1in x 1in location inside the box, this is basically a switch Y or null if its filled in. I have also thought about a code system to help me determine the layout of the box. Everything but 0 means its filled in, 0 is empty. And then the codes will tell me ALL of the different combinations of what can be filled around it.. but that might be slower than actually just checked the array values.)

What I need help with is determining how to efficiently place the boxes into each other, and be able to track it(?) if I have too. So that I can repeadidly try different combinations till the best 2 or 3 are found.

This is sort of like finding the best way through a maze, you go through the maze successfully and retract your steps to try different turns until the shortest path is found.

I will probably be working on this for a very long time so I have some time to talk about it. I'd offer alot more than 500pts for this but apparently I can't.
Question by:digitalpacman
  • 6
  • 3
  • 3
  • +1
LVL 84

Accepted Solution

ozo earned 250 total points
ID: 17861968

Expert Comment

ID: 17864457
There are other ways to think of this problem. For example, clothing manufacturers need to lay out their patterns to minimize waste.

I have seen a tool that helps you pack your boxes efficiently. I thought it was part of Canada Post's Electronic Shipping Tools, but I couldn't find any reference to it in the manuals posted on their website

This article explains how one company planned to implement such software.

By the way, if you Google
reduce carton void
you get quite a few links that suggest you should solve your problem by using boxes with serrated sides, so you can cut them down in size to fit the contents.

Searching this site might yield results

Author Comment

ID: 17868814
That was some good reading, and a nice code sample.

ozo, the paper you presented is a good resource, but I am looking for something more simple. It doesn't have to be perfect. And the items are not 3d free form, they are actually all rectangles. That code sample also says it can only be used for academic and research purposes... with is sad cause its very close to what I want!

I need to be able to say I have X  20x20x20 boxes, and Y 40x60x40 boxes, and I have to pack A 2x4x8, B 5x5x8, and C 1x20x20 items. And then it needs to just go :P My boss doesn't really understand the complexity in this problem, he thinks its a 1-2 week project for one guy.

I tried searching, but all I could find was a bunch of packing line articles about how wel people are doing, or how well robots operate.

Anyways I'm going to continue searching around and trying code samples from resources you two supplied. Thanks for the help, and anymore from you or anyone else is still wanted!

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.


Assisted Solution

garlin007 earned 250 total points
ID: 17871800
Great reference ozo! David Pisinger seems to be one of the experts in this area.

digitalpackman, why don't you write David and ask him if he will license his code for a not-for-resaile single company application? Perhaps he knows if his code has been implemented commercially, or if there is a commercial application that uses a similar algorithm.

Now that you know what to search for, googling "three-dimensional bin-packing" (in quotes) turns up a lot of relevant hits, although they are mostly academic.

It did lead me to this, though

It sells for about $300 - $650.

Author Comment

ID: 17899900

Yes I did think about asking David, but sadly, his heuristic method is very limited. It only allows fixed sized "bins" to place objects in. I have many different sized ones... and looking at his source code it would take me forever to figure out how to put in that capability, sadly =(

I found that software too! Except it really would sell for 2-4k... I emailed them and this is what they quoted me. They also do not offer a com object or DLL format of the software. The best they could offer me is their batch processing method of using text files and output files to push/get data.

Since it has to be integrated seemlessly with what I'm building, I can't really use it until they offer some kind of DLL.

Anyway, they are still a possibility, my boss is looking into it. We might be able to create temporary text files based on the userid of the person making the request, getting the results, and then deleting all the files. But we dislike using disk IO too much.

I noticed that three-dimensional bin-packing helped alot too. But again same results as you, lots of academic articles and papers, but no real programming code or programs! What a dilemma.

This is what I have decided to do, I've been playing with boxes to see if the algorithm works :P

I first run a filter on the bins available, based on the greatest length and width and height of my largest boxes. Then I filter this out again based on the total volume of the boxes, and the total volume of the bins to find the smallest best fitting solution. I simply just compare the volumes, and add 10% to the boxes volume for lee-way. EXP: 35 volume boxes, 55 volume box or 2 20 volume boxes.. I use the 2 20 volume boxes because its less than 55 and has a 10% volume gain on the box volumes.

I then point all the bins length-wise, width-wise, and then height-wise.
Then I sort the boxes by volume, and point them the same way as bins... length-wise, width-wise, then height-wise.
This makes it so all the boxes and bins face the same general direction.

After that, I start placing in boxes... my method is...
I have a triple subscripted array each cell representing a 1x1x1 area inside a bin. The contents are filled with the ID of the box taking up that space, 0 if no box.
I start in the lower left corner, and check if there is room, if there is I then check to see if the box has enough room (the box doesnt stick outside the bin)
If that check is good, I check the other 7 corners of of the box, if they are all successsful I check every 1x1x1 square inside the bin at this spot.
If that is ok, I set my "starting reference point" to the far bottom left corner of the box just placed.
I start checking the rest of the boxes from there..
If a corner fails I go to the next available corner of that box, the order is... far bottom left, close bottom right, far bottom right, then the same for the top corners.
(I may change this algorithm to just go from any corner of any box inside the bin.... going in the order inserted)
If none is found, I rotate the box 90deg (max 2 rotations) and the check restarts.
If none is found, I remove the previous box, swap their insert order with the current box, and try inserting the current box again. (since their order was swapped I simply go back in time and retry.. the order is different so it starts with the current box that never fit)

If none is found still, I grab a new box and place them inside it.

New boxes are attempted to be placed into bin 1 as long as its available volume > box volume. Then it goes to the next box if it doesn't fit anywhere.

Well that's that. It sure as hell ain't perfect! But it has worked well enough for the examples we've put together. The only problem is it can create "holes" where packing popcorn cannot fall into.. but if the boxes shift around after being shaken the popcorn may fall into place and the goods will be fine.

Long explanation I know..
LVL 49

Expert Comment

ID: 17903114
FWIW, that's about the algorithm I'd use.  Of course, there are four orientations for a "rectangular" box
  |        ||
  |        ||
    /           /|
   /           / /
  /______/  /
   /    /|
  /__/  |
  |    | |
  |    | |
  |    | /

So you would need to cycle through all four before choosing the next permutation of box orders.  I had some fun with a similar (though two-dimensional) problem some years back, fitting oddly-shaped "pentomino" puzzle pieces into a rectangle

I sure wish my boss would give me such interesting projects :-)

-- Dan
LVL 84

Expert Comment

ID: 17903488
There are six orientations for a "rectangular" box

Author Comment

ID: 17903546
Hah ozo, I was about to say that... 6 orientations..

THey include the 3 dimenions flat and also rotated 45 degress left.

Anyway.. I figured 3 different orientations is enough..

and I also ran into problems with checking corners.. because the box placement is dependent on which corner it goes on. So I ran a stress test on looping through a triple subscripted array of 36x13x18... a fairly large box. I was able to do it pretty quickly. So I think I might use that route since i'm not using a very heuristic method. If I was well then.. my script would stop running about this time next year give or take a day.

LVL 84

Expert Comment

ID: 17905195
here's a method for packing squares into rectangles by analysing the packing as an electrical network

Author Comment

ID: 17907643
ozo, what format is .ps? My windows box doesn't know how to execute it

Author Comment

ID: 17907674
Hmm edit that.. I found out myself.. postscript.... opens with two listed programs that I found. One the domain expired... so I'm a bit shakey to download software to open it

Expert Comment

ID: 17912228
I was able to open that file in Paintshop Pro - but it is essentially a multipage document. This appears to be the same file
The directory contents are visible


Author Comment

ID: 17950854

I managed to make a working program so far, its not very efficient. I need to come up with a better algorithm to find open spacing. I think I have an idea but gota figure a way to properly program it.

Currently all I'm doing is looping through the box, finding an open locatoin, then checking 8 corners of where the box is to be placed, then check the entire insides. But this becomes pretty slow when the box becomes larger.

I'm thinking of like checking the X axis first, and if I find a box there, then add the width of the inserted box to the current location.. do the same for the Y while moving along the Y.. and Z too.

Thanks for the assistasnce. I'm going to give credit now since I was able to make a working solution. But if you find an algorithm for finding squares inside a box quickly let me know.


Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

The CRUD Functions CRUD, meaning "Create, Read, Update, Delete (,_read,_update_and_delete)" is a common term to data base developers.  It describes the essential functions of data base table maintenance.  This art…
What is Waterfall Model? Waterfall model is the classic Software Development Life Cycle method practiced in software development process. As the name "waterfall" describes, this development is flowing downwards steadily like waterfall, i.e., procee…
Exchange organizations may use the Journaling Agent of the Transport Service to archive messages going through Exchange. However, if the Transport Service is integrated with some email content management application (such as an antispam), the admini…
Attackers love to prey on accounts that have privileges. Reducing privileged accounts and protecting privileged accounts therefore is paramount. Users, groups, and service accounts need to be protected to help protect the entire Active Directory …

749 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question