Solved

THIS IS A VERY DIFFICULT QUESTION

Posted on 2006-11-02
13
263 Views
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.
0
Comment
Question by:digitalpacman
  • 6
  • 3
  • 3
  • +1
13 Comments
 
LVL 84

Accepted Solution

by:
ozo earned 250 total points
ID: 17861968
0
 
LVL 6

Expert Comment

by:garlin007
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 www.canadapost.ca.

This article explains how one company planned to implement such software.
http://www.deq.state.or.us/wmc/packaging/other/AppendixC_OM.pdf

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
http://www.packworld.com
0
 

Author Comment

by:digitalpacman
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 packworld.com, 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!

0
 
LVL 6

Assisted Solution

by:garlin007
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

http://www.astrokettle.com/pr3dlp.html

It sells for about $300 - $650.
0
 

Author Comment

by:digitalpacman
ID: 17899900
garlin007,

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..
0
 
LVL 49

Expert Comment

by:DanRollins
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
   http://webpages.charter.net/danrollins/pentsolv/pentsolv.htm

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

-- Dan
0
Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

 
LVL 84

Expert Comment

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

Author Comment

by:digitalpacman
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.


0
 
LVL 84

Expert Comment

by:ozo
ID: 17905195
here's a method for packing squares into rectangles by analysing the packing as an electrical network
http://www.math.washington.edu/~reu/papers/1997/shastry/shastry.ps
0
 

Author Comment

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

Author Comment

by:digitalpacman
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
0
 
LVL 6

Expert Comment

by:garlin007
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
http://www.math.washington.edu/~reu/papers/1997/shastry/shastry.pdf
The directory contents are visible
http://www.math.washington.edu/~reu/papers/1997/shastry/

0
 

Author Comment

by:digitalpacman
ID: 17950854
Hey,

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.

Thanks!
0

Featured Post

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
Disable a Command Button 2 279
Bots, Spiders, web crawlers 3 109
dividesSelf challange 15 77
Permutation and Combination 9 45
Setting up SVN Server using Windows and Apache Purpose of the document:       This article will explain the process of how to configure SVN repository in a windows environment using APACHE web server. What is SVN? (http://subversion.tigris.org/) …
The Fluent Interface Design Pattern You can use the Fluent Interface (http://en.wikipedia.org/wiki/Fluent_interface) design pattern to make your PHP code easier to read and maintain.  "Fluent Interface" is an object-oriented design pattern that r…
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…
This video demonstrates how to create an example email signature rule for a department in a company using CodeTwo Exchange Rules. The signature will be inserted beneath users' latest emails in conversations and will be displayed in users' Sent Items…

708 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

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now