ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2015, № 2, с. 98-106
КОМПЬЮТЕРНЫЕ ^^^^^^^^^^^^^^ МЕТОДЫ
УДК 62.40
PACKING CIRCULAR-LIKE OBJECTS IN A RECTANGULAR CONTAINER
© 2015 г. I. Litvinchev, L. Infante, L. Ozuna
Russia, Moscow, Computing Center Russian Academy of Sciences, Mexico, UANL, Faculty of Mechanical and Electrical Engineering Received June 05, 2014
A problem of packing unequal circles in a fixed size rectangular container is considered. The aim is to maximize the (weighted) number of circles placed into the container or minimize the waste. The circle is considered in a general sense, as a set of points that are all the same distance (not necessary Euclidean) from a given point. An integer formulation is proposed using a grid approximating the container and considering the nodes of the grid as potential positions for assigning centers of the circles. The packing problem is then stated as a large scale linear 0—1 optimization problem. The binary variables represent the assignment of centers to the nodes of the grid. The resulting binary problem is then solved by commercial software. Valid inequalities are proposed to strengthening the original formulation. Nesting circles inside one another is considered tacking into account the thickness of the circles. Numerical results on packing circles, ellipses, rhombuses and octagons are presented to demonstrate the efficiency of the proposed approach.
DOI: 10.7868/S0002338815020079
Introduction. Packing problems generally consist of packing a set of items of known dimensions into one or more large objects in order to minimize a certain objective (e.g., the unused part of the objects or waste).
The circle packing problem is a well studied problem [1, 2] whose aim is the packing of a certain number of circles, each one with a fixed known radius (not necessary the same for each circle) inside a container. The circles must be totally placed inside the container without overlapping. The shape of the container may vary from a circle, a square, a rectangular, etc.
This problem has been applied in different areas, such as the coverage of a geographical area with cell transmitters, storage of a cylindrical drums into containers stocking them into an open area, packaging bottles or cans into the smallest box, planting trees in a given region as to maximize the forest density and the distance between the trees, and so forth [3—5]. Other applications one can find in the motor cycle industry, circular cutting, communication networks, facility location and dashboard layout [2, 6, 7].
Many variants of packing circular objects in the plane have been formulated as nonconvex (continuous) optimization problems with decision variables being coordinates of the centers. The nonconvexity is mainly provided by no overlapping conditions between circles. These conditions typically state that the Euclidean distance separating the centres of the circles is greater than a sum of their radii.
The nonconvex problems can be tackled by available nonlinear programming (NLP) solvers, however most NLP solvers fail to identify global optima. Thus, the nonconvex formulation of circular packing problem requires algorithms which mix local searches with heuristic procedures in order to widely explore the search space. We will refer the reader to review papers presenting the scope of techniques and applications for the circle packing problem (see, e.g., [1, 8—12] and the references therein).
In this paper we study approximate packing of circular-like objects using a regular grid to approximate the container. The circular-like object is considered in a general sense, as a set of points that are all the same distance (not necessary Euclidean) from a given point. Thus different shapes, such as ellipses, rhombuses, rectangles, octagons can be treated the same way by simply changing the norm used to define the distance. The nodes of the grid are considered as potential positions for assigning centers of the circles. The packing problem is then stated as a large scale linear 0—1 optimization problem. Valid inequalities are proposed to strengthening the original formulation. Nesting circles inside one another is considered tacking into account the thickness of the circles. Numerical results on packing circles, ellipses, rhombuses and octagons are presented to demonstrate the efficiency of the proposed approach.
To the best of our knowledge, the idea to use a grid was first implemented in [13] in the context of cutting problems. This approach was recently applied in [14—19] for packing problems. This work is a continuation of [15].
The rest of the paper is structured as follows. In Section 1 the main integer programming model for packing problem is presented. Section 2 is related to the experimental results on packing circles, ellipses, rhombuses and octagons to show that our methodology is efficient. A final section concludes this work.
1. The model. Suppose we have non-identical circles Ck of known radius Rk,k e K = {1,2,... K}. Here we consider the circle as a set of points that are all the same distance Rk (not necessary Euclidean) from a given point. In what follows we will use the same notation Ck for the figure bounded by the circle,
Ck = {z e [R2: ||z - z0k|| < Rk}, assuming that it is easy to understand from the context whether we mean the curve or the figure. Denote by Sk the area of Ck.
Let at most Mk circles Ck are available for packing and at least mk of them have to be packed. Denote by i e I = {1,2 ..., n} the node points of a regular grid covering the rectangular container. Let F c I be the grid points lying on the boundary of the container. Denote by dy the distance (in the sence of norm used to define the circle) between points iand j of the grid. Define binary variables xk = 1 if centre of a circle Ck is assigned to the point i; xk = 0 otherwise.
In order to the circle Ck assigned to the point i be non-overlapping with other circles being packed, it is necessary that xj = 0 for j e I, l e K, such that dy < Rk + Rl. For fixed i, k let Nik = {j, l: i ^ j, dy < Rk + Rl}. Let nik be the cardinality of Nik: nik = |Nik|. Then the problem of maximizing the area covered by the circles can be stated as follows:
max YY S2kxi, (1.1)
ieIke K
subject to
mk < Yxkt < Mk, k e K, (1.2)
i e I
Y xk < 1, i e I\F, (1.3)
k e K
Rkxk < min dj, i e I, k e K, (1.4)
j e F
xk + xlj < 1, for i e I; k e K; {j, l) e Nik, (1.5)
xk e {0,1}, i e I, k e K. (1.6)
Constraints (1.2) ensure that the number of circles packed is between mk and Mk; constraints (1.3) that at most one centre is assigned to any grid point; constraints (1.4) that the point i can not be a centre of the circle Ck if the distance from i to the closest grid point of the boundary is less than Rk; pair-wise constraints (1.5) guarantee that there is no overlapping between the circles; constraints (1.6) represent the binary nature of variables.
Remark 1. In (1.4) Rk is compared with the distance from the center i to grid points of the boundary, i.e. the boundary is represented by its grid points only. Thus in general constraints (1.4) do not guarantee that a circle fits into the container. However if the point of the boundary closest to Ck is a grid point, then (1.4) ensure that there are no intersections between circles and the boundary.
Similar to plant location problems [20] we can state non-overlapping conditions in a more compact form. Summing up pair-wise constraints (1.5) over {j, l) e Nik we get
nikxf + Y xj ^ nik for i e I, k e K. (1.7)
j,l e Nk
Note that constraints similar to (1.7) were used in [9] for packing equal circles (K = 1).
Proposition 1. [16, 18]. Constraints (1.5), (1.6) are equivalent to constraints (1.6), (1.7).
Thus the problem (1.1)—(1.6) is equivalent to the problem (1.1)—(1.4), (1.6), (1.7). To compare two equivalent formulations, let
P1 = {x > 0 : xk + xj < 1, for i e I, k e K, (j,J) e Nlk},
P2 = {x > 0: nkkxk + ^ xj < nk for i e I, k e K}.
j,l e Nik
Proposition 2. [16, 18]. P с P2.
As follows from Proposition 2, the pair-wise formulation (1.1)—(1.6) is stronger [20] than the compact one. Numerical experiments presented in [18] demonstrate that the pair-wise formulation is also computationally more attractive since it provides a tighter LP-bound. Bearing in mind these reasons we restrict ourselves by considering below only pair-wise formulations.
By the definition, Nik = {j,l: i Ф j, dij < Rk + R,} and hence if (j,l) e Nik, then (i,k) e Njl. Thus a half of the constraints in (1.5) are redundant since we have
xk + xj < 1, for i e I, k e K, (j, l) e Nik,
xj + xk < 1, for j e I, l e K, (k) e NjJ.
The redundant constraints can be eliminated without changing the quality of LP-bound giving a reduced pair-wise non overlapping formulation.
In many applied problems nesting circles inside one another is permitted. For example, in [5, 7, 21] nesting is considered in the context of packing pipes of different diameters into a shipping container. Nesting is also essential for storing different cylinders one over another in the form of cylindrical towers.
To consider nesting circles inside one another, we only need to modify the non-overlapping constraints. In order to the circle Ck assigned to the point ibe non-overlapping with other circles being packed (including circles placed inside this circle), it is necessary that xj = 0 for j e I, l e K, such the Rk - R, < dy < Rk + R, for Rk > R. Let
^tk = {j,l: i * j, Rk - Rj < dj< Rk + Rj, Rk > Rj}.
Then the non-overlapping constraints for packing circles with nesting can be stated in the form
xk + xj < 1, for i e I; k e K; (J, l) e D.ik. (1.8)
Constraints (1.3) have to be relaxed in case of nesting.
If nesting is permitted, e.g., in the case of packing plastic pipes [5, 7, 21], it may be necessary to take into account the thickness of the pipe, i.e. the difference between external and internal size of the object. To consider nesting-subject-to-thi
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.