Authors
Chekanin V.
|
Degree
|
Dr. Sci. (Eng.), Associate Professor, Theoretical Mechanics and Strength of Materials Department, Moscow State University of Technology "STANKIN"; Leading Researcher, V. A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences |
|---|---|
|
E-mail
|
vladchekanin@rambler.ru |
|
Location
|
Moscow, Russia |
|
Articles
|
Optimizing orthogonal packing task solutionThe general multi-dimensional orthogonal objects packing problem is considered. To construct the orthogonal packing of objects of arbitrary dimension the model of «virtual objects» is suggested. In order to optimize the solution multimethod genetic algorithm is used. We propose new heuristics placement of objects. The developed algorithms are implemented as software modules built on the basis of the universal library of classes of packing problems proposed by the authors. The results of computational experiments on standard two-dimensional rectangular packing problems are presented.
Read more...
Effective model of objects management for the orthogonal packing and rectangular cutting problems
The orthogonal packing problem is a problem related with the founding of the optimal placement
of a given set of small orthogonal items (objects) into a set of large orthogonal items (containers).
This problem is a well-known NP-completed problem that has many applications in industry and economics.
To solve the packing problems usually are applied various approximation algorithms that are
based on the heuristic methods of optimization. To provide the effectively work of an optimization algorithm
is necessary to minimize any delays related with construction of a placement according to solution
obtained by the algorithm. For this purpose were investigated the causes affecting the speed and
quality of placement generation by the given solution in a form of a sequence of objects to be placed
into containers. The paper is presented an effective model of orthogonal objects management which
provides the possibility of constructing orthogonal packings of arbitrary dimension in solving of all
optimization problems of orthogonal packing and rectangular cutting. This model is the fasted compared
with other known models for objects management. In paper are given algorithms of placement
and deleting objects. The deleting objects algorithm may be used in future in realization of the algorithm
for the local improvements of the obtained placement. The efficiency of the proposed model is
demonstrated on the standard three-dimensional orthogonal packing test problems.
Read more...
Program realization of an effective data structure for the orthogonal packing problems of arbitrary dimension
In the paper is considered a well-known NP-completed orthogonal packing problem which has
many applications in industry and economics. The orthogonal packing problem is a problem related
with the searching of the optimal placement of a given set of small orthogonal items (objects) into a
set of large orthogonal items (containers). The effective approach to solve NP-completed problems is
application of heuristic methods which provide obtaining of suboptimal decisions. The maximal efficiency
of such will be achieved when delays on packing generation will be minimized. In the paper
is considered a multilevel linked data structure which provides the possibility of fast management of
free spaces into orthogonal containers during the process of filling them with objects. The program
realization of the proposed data structure, which is implemented invariantly on the dimension of the
considered packing problem, makes it universal and applicable for solving of rectangular packing and
orthogonal packing problems of arbitrary dimension. The paper presents results of the carried out computational
experiment. The results demonstrate that the efficiency of proposed data structure increases
with the number of objects and it tends to double the effectiveness of the time compared with the simple
linear linked list. In paper is also given a description of the developed applied software intended
for various types of rectangular cutting and orthogonal packing problems.
This work was carried out with the financial support of the Ministry of Education and Science
of Russian Federation in the framework of the state task in the field of scientific activity of MGTU
«STANKIN» (No. 1.7706.2017/8.9).
Read more...
Development of packing compacting algorithm to improve the efficiency of rectangular cuttingIn this article is considered the NP-hard optimization strip packing problem that is actual in solving
many practical problems of automation and control, in particular, it takes a place in solving such
problems as cutting of materials, calendar scheduling and planning, placement of resources in multiprogramming
systems and a lot of other problems. With the aim to optimize the placement of objects
in a container, the iterative packing compaction algorithm which insures the increasing of the density
of packed objects was developed. In the basis of the proposed algorithm lays usage of six rules
which select several placed objects with the aim of removing them with subsequent more rational filling
of the freed spaces in a container by the deleted objects through a single-pass heuristic algorithm.
The results of carried out computational experiments on the investigation of the packing compaction
algorithm on the standard test instances of the strip packing problem with the given random and optimized
placements are presented. On the average the packing compaction algorithm provides increasing
the density of random placements to 3% and density of optimized placements to 0.4%. The developed
algorithm has been implemented in a general form, which makes it possible to use it not only for
two-dimensional problems as well as for three-dimensional orthogonal packing problems.
Read more...
Algorithms for the correct visualization of two- and three-dimensional orthogonal polyhedronsThe article is devoted to algorithms for obtaining outlines of two-dimensional and three-dimensional
orthogonal polyhedrons. An orthogonal polyhedron is a geometric figure representing the union of
non-overlapping orthogonal objects (rectangles or parallelepipeds in the two-dimensional or three-dimensional
case, respectively) with a fixed position relative to each other, considered as a single whole
object. The need to use orthogonal polyhedrons as individual objects arises, in particular, at solving a
number of resource allocation problems. When an orthogonal polyhedron is being drawn, there should
be displayed only those edge fragments of its orthogonal objects that compose the outline of the orthogonal
polyhedron. The article contains a detailed description of the developed algorithms to obtain
a set of edges belonging to the outline of a two-dimensional or three-dimensional orthogonal polyhedron.
The algorithms are based on the idea of searching and cutting off segments located on edges belonging
to several orthogonal objects belonging to the considered orthogonal polyhedron. The developed
algorithms provide the possibility of visualization of arbitrary orthogonal polyhedrons, including
those containing any holes. The algorithms presented in the article are implemented in the developed
applied software intended to optimize the solution of resource allocation problems of various dimension,
including the orthogonal packing and rectangular cutting problems.
Read more...
Methods of forming orthogonal polyhedra for cutting and packing objects of complex geometryThe article deals with the problem of packing objects of arbitrary geometry. Modern methods of designing irregular packing schemes use a mathematical model based on phi-functions and a hodograph vector function of dense placement. These methods make it possible to obtain exact solutions, but they are time-consuming and very sensitive to the dimension of the problem being solved and the degree of detail of the geometry of vector objects. The use of a discrete representation of placed objects in the form of orthogonal polyhedra can signifi increase the speed of construction a packing, which makes the problem of adequately transforming the shape of placed objects (vector models in the two-dimensional case and polygonal models in the three- dimensional case) relevant. The aim of the study is to systematize methods that provide the formation of orthogonal polyhedra of various dimensions for describing objects and containers of arbitrary geometry. Methods for creating orthogonal polyhedra based on set-theoretic operations (addition, subtraction and intersection), analytical modeling using a set of functions and relational operators, as well as voxelization of fl and volumetric object models are considered. The use of set-theoretic operations is best suited for the manual creation of orthogonal polyhedra with relatively simple geometry. The method of analytical modeling is intended for the formation of voxelized objects based on geometric fi es described by a set of analytically specifi functions. The application of various relational operators to obtain orthogonal polyhedra that describe the contour, internal and external regions of analytical given objects is shown. An algorithm for creating a container in the form of an orthogonal polyhedron based on a given vector model is proposed, which makes it possible to solve problems of irregular packing of objects inside containers of arbitrary shape. All the methods presented in the article are programmatically implemented with a generalization in terms of dimension and are applicable to solving any types of cutting and packing problems. Read more... Greedy heuristic of orthogonal polyhedra placement for optimized solution of irregular shape object packing problemsThe article deals with the cutting and packing problems of irregular shape objects, which consist in finding the most compact way to place a given set of objects of arbitrary geometry inside a certain limited space. These problems belong to the class of NP-hard discrete optimization problems for which there are no methods of polynomial complexity to obtain exact solutions, so in practice they are most often solved approximately using heuristic and metaheuristic optimization methods. When placing objects of irregular shape, it is additionally necessary to take into account the geometry of objects to determine the correctness of their placement relative to each other. Existing methods of analyzing the geometry of objects and the formed placement scheme, based on the use of phi-functions and the construction of a hodograph of a vector function of dense placement, theoretically provide the possibility of obtaining an accurate solution, but require the use of time-consuming methods of nonlinear optimization. Therefore, in order to increase the speed of packing a large number of irregular-shaped objects, their shape is transformed by voxelization, followed by combining the resulting set of voxels into orthogonal polyhedra. To improve the quality of the solutions obtained, the paper proposes a greedy heuristic for the placement of orthogonal polyhedra, which implements the choice of the best orientation option for the object being placed, in which the formed packing will be the densest in comparison with other available orientation options for this object. The analysis of the effectiveness of this greedy heuristic on the problems of irregular cutting and packing of three-dimensional objects is carried out. Computational experiments have shown that the proposed greedy heuristic provides very fast high-quality solutions. Additionally, the results of testing the greedy placement heuristics using a genetic algorithm to optimize solutions to the packing problem are presented. Read more... |
