The chief goal of the research the results of which are presented in the report is development and software implementation of the algorithm to solve a problem of “packing items into a container” for 2- and 3-dimensional cases. This algorithm is based on human arguments modeling when solving these problems. The problem of “packing items” is generalization of 1-dimensional “knapsack problem” and 2- and 3-dimensional cases of “containers packing”. This problems deals both with close arrangement in one container and their distribution to lower their quantity.
There was proposed an algorithm based on the heuristic performance functional merit of the subject of research in order to choose one among the variety of others at every single stage. The idea is to narrow the task solution down to 2-dimensional case by means of choosing a flat surface on the already packed objects and placing objects of similar height. Heuristic performance functional merit is used to choose: an area of 2-dimensional packing of all types, a set of objects to pack this area, an object to be packed under a 2 dimensional algorithm; and to choose the best place for this object.
The report will cover details of theoretical and experimental evaluations of performance of the proposed algorithm functioning. There was assessed theoretical time performance for 2- and 3-dimensional algorithms as based on quantity of objects in the problem: O(N4) and O(N5) respectively. Experimental quality evaluations of the proposed algorithm will demonstrate average density of containers loading to 80% - 90% of capacity which is a very good output for the majority of the practical problems.
Source [3]