Nesting algorithm

[Orestes Chouchoulas]

Hi all,

I just wanted to post an email I sent to a CS department recently, trying to entice one of heir students to work on he nesting algorithm. It includes a decent definition of the nesting problem and what would make a good solution for wikihouse purposes. Please have a look and suggest any improvements to the definition:

Quoted email:

Hi Peter,

You can get the basic gist of the WikiHouse project by looking at wikihouse.cc or (more entertainingly) bywatching Alastair Parvin's TED talk from last spring.

I would like to give you a brief definition of the problem I felt you guys could give us a hand with. WikiHouse proposes a building system the major components of which can be cut from rectangular sheets of plywood using a CNC router. At the same time, the designs are available openly, so they change often, which means that new cutting pattern files have to be generated. WikiHouse have put together a plugin for SketchUp that can take the two-dimensional shapes of the components and place them on rectangular sheets to create cutting patterns. However, this is currently done using a very inefficient algorithm that wastes a lot of material.

So, in essence, we are looking at a 2D nesting problem for CNC routing. Clearly this is a problem that has great applications in industry. We have found some commercial solutions, but due to the way WikiHouse works, we need an algorithm that can be (eventually) open sourced.

This is lovely NP-complete stuff that your students could hopefully sink their teeth into. A cursory literature review reveals that most papers on the nesting problem are from the last 7 years, which suggests that it's current and interesting. So far, my hunch is that simulated annealing or a GA-based approach would work best, but I've seen papers proposing things like guided local search etc.

The particularities of the problem:
- The components are irregular concave polygons.
- The material sheets are rectangular and of identical fixed dimensions. Most component sets need to span multiple sheets. (Optimise for lowest number of plywood sheets.)
- Allow components to be translated AND rotated to be placed on the sheet. (Optional Boolean flag to allow flipping/mirroring of components—some sheet materials have differently finished faces.)
- Bonus: Some components are polygons with holes. Allow nesting of components within holes.
- Bonus: Optimise last sheet area use (strip nesting problem).

Algorithm inputs:
- Dimensions of material sheets.
- 2D geometric definitions of components.
- Minimum distance between components.
- "Allow mirroring" Boolean. Bonus: allow setting that flag per component.

Outputs:
- CNC cutting pattern files.

I would be happy to help with further defining the problem for this particular application and liaising with the Wikihouse community. WikiHouse has been getting a fair bit of interest recently, and a good, open-source nesting algorithm has been in high demand for a while. I expect that the growing hobbyist CAM community would also be very interested, so there is the potential for a lot of exposure, should that be of significance.

I hope this sounds interesting and I'm looking forward to receiving your thoughts on how all that could work within the department's academic process.

Orestes