PackRat 3d Bin Packing

Hi all,

I just released a component for Grasshopper for 3D box bin packing:

PackRat is a component for Grasshopper that facilitates the arrangement of rectangular items within rectangular containers with the aim of improving efficient use of space. In other words, it attempts to approximate optimal solutions to the 3D bin-packing problem.

Packrat accepts a list of containers and a list of items to be packed. Only rectangular items are recognized, so if the input consists of arbitrarily shaped BReps, their bounding boxes will be considered. It outputs a GH_Structure of items per container, and a supplementary list of items that did not fit in any container.

There is an option to choose whether sorting of elements and containers should be performed before packing. While sorting usually yields better results, disabling allows the user to perform their own sorting before inputing the elements to PackRat.

The packing method is based on the work by Crainic, Perboli and Tadei in

[Crainic, T, Perboli, G., Tadei, R., Extreme Point-Based Heuristics for Three-Dimensional Bin Packing. CIRRELT-2007-41, October 2007](https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2007-41.pdf).

PackRat has been found to work with Grasshopper v0.8.0052.

PackRat is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

Info / Download

Tags: 3d, bin, bounding, box, heuristics, packing, packrat

Attachments:

01.jpg, 47 KB

▶ Reply to This

Replies to This Discussion

Permalink Reply by Charles C Vincent on December 20, 2011 at 4:02am

Hi, Yiannis, fantastic job!!
Do you think it would be possible to improve packrat allowing for 90 degree rotations of individual breps when packing?

Best,

▶ Reply

Permalink Reply by Yannis Chatzikonstantinou on December 20, 2011 at 4:10am

Hi Charles,

Indeed I spent some time implementing rotations but I bumped into some trouble so I postponed it to the next release. But in the end I hope to also allow selection of possible rotation axes (e.g. allow rotation along Z but not X and Y).

Yiannis

▶ Reply

Permalink Reply by Charles C Vincent on December 20, 2011 at 4:48am

Nice!
How about some control of the span among packed breps?

▶ Reply

Permalink Reply by Charles C Vincent on December 20, 2011 at 5:58am

Oh, I'm so dumb... they're just being scaled down!

▶ Reply

Permalink Reply by pyrit on December 29, 2011 at 5:25am

hi yiannis ,

could you please explain your example file with the ga-solver a little bit ?

because i thougt your component aims at optimizing the packageing - so what is the galapagos for ?

thanks !

▶ Reply

Permalink Reply by Yannis Chatzikonstantinou on January 4, 2012 at 2:23am

hi pyrit,

The quality of the result of most packing heuristics (the Extreme-Points Heuristic used by Packrat included) is highly dependent on the order that elements are packed. With the same heuristic you can get a much better result just changing the sequence of input elements. Packrat contains some sorting algorithm that pre-sorts elements just before they are packed. However, in some cases this sorting does not produce optimal results.

The idea behind this example is to use a Genetic Algorithm to search for element orderings that could produce better results. Indeed, using Galapagos a slight reduction in packing size is achieved (although the performance measure should be number of bins actually). According to my tests, more advanced GAs (one is currently being implemented as a GH component at TU Delft) perform even better.

So indeed there is space for improvement even without switching packing heuristics, however it should be noted that in this case the execution time is many times longer (a couple of minutes, depending on the GA settings vs less than a second for pre-sorting performed by Packrat).

▶ Reply

Permalink Reply by Adam Blaney on March 1, 2012 at 8:28am

Hi, Yiannis, PackRat is really useful.

I'm an architecture student in my 6th year, I was interested to explore the possibilities of packing density base on solar a access criteria, I have looked at potentially combing other plug-ins to evaluate this, Geco will link to Ecotect to evaluate the solar access performance and Galapogos will evaluate the success for each generation, with the ultimate outcome of a optimised spatial organisation based on solar performance.

I suppose initially is there any way to three dimensionally pack a non square volume, above is a photo that shows potential apartment blocks packed in a solar envelope, this envelope that is to be packed is derived for specific solar conditions particular to that site, can this non square volume be packed?

Many thanks

Adam

▶ Reply

Permalink Reply by Yannis Chatzikonstantinou on March 4, 2012 at 11:44am

Hi Adam,

Thanks for the message. Indeed the potential of packing methods such as the one in use by Packrat is that they can be combined with metaheuristics to address possibly multiple goals at the same time. Packing within arbitrarily-shaped volumes is indeed an interest I had ever since I started developing this plugin. It seems that it is not a trivial thing to do actually! I am planning on implementing an approach to address it (rather crude I would say actually but nevertheless I hope it'll work for simple cases!), so expect something to come up in the next release of Packrat.

Kind Regards,

Yannis

▶ Reply

Permalink Reply by bassem M.EID.M on June 6, 2012 at 10:58am

Hi Yannis,
Amazing tool!

was wondering if there is a possinility to employ packrat in towards space planning of modular housing?
also, link it with galapagos for optimization of results?

Reagrds,

Bassem

▶ Reply

Permalink Reply by Yannis Chatzikonstantinou on June 11, 2012 at 6:37pm

Hi Bassem,

It could be possible, however in the case of housing there are actually many more goals that a design should satisfy, Packrat (the algorithm it's based on) just deals with efficiency in terms of space usage.

It could be combined with a stochastic search algorithm e.g. to search for arrangements that satisfy proximity constraints between packed elements, while maintaining efficient space usage.