A pairwise exact placement algorithm for the irregular nesting problem

The irregular nesting problem, a subset of cutting and packing problems, aims to minimise waste or unoccupied space inside a container and is found in wood, glass, shipbuilding and textile industries. The problem consists in finding the most compact arrangement of two-dimensional items inside a rectangular container without overlap. The length of the container is variable and up to four different orientations are allowed for each item. Overlap is avoided by using a constructive placement heuristic which places items one at a time, without colliding with other items. The proposed algorithm in this work uses a pairwise placement strategy in which one item is always positioned in exact fitting or sliding placements, which are positions where the item movement is restricted. A simulated annealing algorithm controls the placement sequence and guides the search over the solution space. Several placement heuristics were proposed and tests were conducted with benchmark instances. Results show improvement in efficiency and speed over previous works in some cases.