This paper describes a new algorithm, PLANEPACK, which determines an optimal or near optimal solution for the Wj packing of identical shapes in the infinite plane. Restricted to polygons for computational convenience, it is based on the no-fit polygon/configuration space obstacle approach. The algorithm was tested on a modest set of fourteen polygons (thirteen non-interlocking and one interlocking) and yielded a feasible solution for each. The solutions were optimal for four of the non-interlocking polygons and near optimal for the other nine. As expected though, the solution for the one interlocking polygon was sub-optimal and enhancements to the algorithm would be required for such cases.
- Non-convex polygon
ASJC Scopus subject areas
- Management Information Systems
- Strategy and Management
- Management Science and Operations Research