Layplan generator finds the optimal layout of pieces to be cut i.e. arranges them on a cutting area in a way that minimises total material consumption. Fabrics are fed from rolls with a fixed width and "unlimited" length (meaning that the fabric roll can be always changed to a new one after a previous one runs out).
The problem is in the domain of irregular strip packing and the chosen way to find a solution is based on TOPOS – A new constructive algorithm for nesting problems and A beam search implementation for the irregular shape packing problem. A heuristic based approach is selected instead of a semi-random search, such as simulated annealing or genetic algorithm, since it can be made to be completely deterministic and thus better follows the knowledge-based paradigm of the whole system: the heuristics can be improved over time based on aquired new knowledge and can become better and better suited for the exact categories of pieces used by the system.
no-fit polygon
An important tool in strip packing process is so called no-fit polygon (NFP), and its counterpart, inner-fit polygon (IFP). They are used to calculate relative placements of two polygons, either inside or outside of each other, where they touch each other, but don't overlap. For example, in the image above, the reference node 0 of polygon B can be placed on any edge of the created green NFP, and always be completely outside of A.
orbital sliding
An orbital sliding method based on Complete and robust no-fit polygon generation for the irregular stock cutting problem is used to generate the NFP and IFP polygons. An orbiting polygon travels around the boundary of a stationary polygon and traces a path around or inside of it. The method can handle concave polygons and shapes with holes.
boolean operations
A second important set of tools in the packing process are polygon boolean operations. They can be used to construct all valid placements relative to already placed shapes by combining NFPs and IFPs.
In a boolean operation, a path is traced along the boundary of a polygon, until an intersection with another polygon is encountered. At the intersection, the traversal jumps to the other polygon: in substraction towards the inside and in addition towards the outside.
panel boundaries
Calculating the layplan with the real cutting path would be computationally costly, so before a search is started, a simplified outline is generated for each panel. The outline encloses the whole shape and also contains a fabric specifc safe area, which allows the packing algorithm to place the items side by side, without any gaps between them.
remaining canvas
The possible area for the placements of a given new piece is calculated by first getting an inner fit polygon of the full cutting area and the piece in question. Then substracting no-fit polygons of all already placed pieces from that area.
placement heuristics
The first piece of a placement sequence is always on the top left position of the fabric. From then on, a two part search is conducted to find an optimal next piece.
First, a placement is found for every piece, in all of its possible rotations, where it minimally increases the combined bounding box height of all pieces. The used fabric determines allowed rotations, most commonly only 180° degree rotations are used, but in some cases 90° and 270° are also allowed.
Secondly, all remaining pieces are compared in their optimal placements, to find a piece that creates the least amount of waste between all pieces, i.e. the unused area on their shared bounding box is the smallest. The second step also tries to maximise the overlap area between the bounding boxes of all pieces.
tree search
It is fairly diffucult to assess the quality of a layplan from a partial solution, so a tree search is conducted to find a set of fully finished viable solutions, and the best one is selected from them.
The search grows every node with the next best two piece candidates. If no valid pieces are found, the whole branch is cut from the tree. Each node contains the index of a piece and its delta-x & delta-y translation values.
The search terminates once all pieces have been placed, and a branch with the lowest overall height is selected as the final packing order.
panel placement
Once the packing order is calculated for the simplified polygons, their translation values can be used to translate the actual laser cutter paths into correct positions.
filler
The full layplan can be amended with small extra pieces in order to increase the fabric utilisation from the level reached with just the absolutely necessary pieces. The filler pieces can include for example extra pockets or pocket bags, repair kits and logo patches. If the rotation rules are relaxed at this stage from the strict 90° rotations, the utilistaion can quite easily reach +90 percent.
cutting order
Once the panel positions have been established, the final step is to optimise the cutting order, i.e. the shortest transition distance from panel to panel. The laser cutting head always starts from the top left position, so the first piece to be cut is the top leftmost one, from there the sequence contimues to the closest one and so forth.
fabric rolling
Most products take more fabric than a single cutting area. Every step of the process first cuts all pieces that can fully fit inside of the cutting area, then the fabric is rolled down until the bottom most uncut piece touches the bottom of the cut area, and the process continues until all pieces are cut.
