engleski

Testing of several overlapping optimization methods for bin-packing problem

In this paper several optimization methods for NP- hard bin-packing optimization problem are considered. Bin-packing problem consists of a number of items that need to be packed into a limited number of containers while satisfying the following constraints: items need to lie entirely within a container without overlapping. Bin- packing methods are also used in textile industry to optimize the material usage while cutting regular and irregular items from a fixed-width material strip. Giving a brief overview of the problem, several computational methods are described in this paper such as items and container data representation, overlapping detection and avoidance methods (constraints graphs, no-fit polygons) and optimization methods: direct search, genetic algorithm and nonlinear programming. Experiments with different number of rectangles, circles, triangles, ellipses and hexagons were performed using three methods - direct search, genetic algorithm and nonlinear programming to compare the overlapping area, total cover area and total overlapping area with nonlinear programming giving the best results.

direct search ; genetic algorithm ; MATLAB ; nonlinear programming ; optimization ; overlapping ; packing problem

nije evidentirano