The optimization of the balanced layout of a set of 3D-objects in a container is considered. We define combinatorial configurations describing the combinatorial structure of the problem. A mathematical model of the problem is presented. The model takes into account the placement constraints, the mechanical characteristics and the combinatorial features of the problem.
I. INTRODUCTION
Balanced layout problems belong to the class of NP-hard placement problems [1] and are the subject of the study of computational geometry, and the methods for their solution are a new branch of the theory of operations research [2, 3]. The essence of the problem lays in the search for the optimal placement of a given set of 3D-objects in a container, taking into account, so called, behavior constraints, which ensure the balance of the system under consideration [4], [5].
Let Ω be a container of height H that can take the form of a cuboid, cylinder, paraboloid of rotation, or truncated cone. The container Ω is defined in the global coordinate system Oxyz , where Oz is the longitudinal axis of symmetry. We assume that container Ω is divided by horizontal j ∈ J m
racks into sub-containers ={1, ..., m} . We denote distances between racks S j Ω j , m and S j+1 by t j , j ∈ J m , ∑ t j = H . The center of the j=1 lower base of container Ω is located in the origin of the global coordinate system Oxyz .
Let А ={ i , i ∈ J n} be a set of homogeneous 3D-objects given by their metrical characteristics. Each object i of height hi and mass mi , is defined in its local coordinate system Oi xi yi zi , i ∈ J n . The location of object i inside container Ω is defined by vector ui =(vi , zi , θi ) , where (vi , zi ) is a translation vector in the global coordinate system Oxyz , θi is a rotation angle of object i in the plane Oi xi yi , where vi = (xi , yi ) , and the value of zi , i ∈ J n , is uniquely defined by sub-container Ω j , j ∈ J m , in which object i will need to be placed.
In contrast to the BLP problems, where a priori the requirement for placing objects in specific sub-containers Ω j , j ∈ J m , is known, in this study the problem of the balanced layout of objects is formulated, which involves generation and selection of a partition of the set A into nonempty subsets A j , j ∈ J m . Here A j is a subset of objects which have to be placed on rack S j inside Ω j .
On placement of object i , i ∈ J n , inside subcontainer Ω j the following constraints are imposed
j
zi =∑ tl−1 + hi , (
l=1 where j ∈ J m. We consider that t0 = 0 and ∀i ∈ J n there exists j * ∈ J m : hi ≤ t j* .
Let J nj ⊆ J n be a set of indexes of objects which are placed in sub-container Ω j , j ∈ J m , m J nj = J n , J ni J nj = ∅ , i ≠ j ∈ J m ; j=1 k j = | A j | is the number of objects which are placed in sub-container Ω j , k j > 0 , j ∈ J m , m ∑ k j = n .
j=1
In addition, the following placement constraints have to be taken into account: j int i1 int i2 = ∅ , i1 < i2 ∈ J n , j ∈ J m , i ⊂ Ω j , i ∈ J n , j ∈ J m ,
j h j ≤ t j , h j
=max{hij , i ∈ J nj } , j ∈ J m .
We designate a system, formed as a result of the
placement of objects i of the set А in container Ω by
Ω A , and a system of coordinates of Ω A by Os XYZ , where
Os = (xs (v), y s (v), z s (v)) is the mass center of Ω A
(
i i M Ox , n ∑ m x
i i M n ∑ m y
i i
M
xs (v) = i=1
, y s (v) = i=1
, z s = i=1
, (
i=1 OsY Oy , Os Z Oz .
We consider the deviation of the center of mass Os of system Ω A from given point (x0 , y0 , z0 ) as an objective function.
Combinatorial Balanced layout Problem (CBLP). Define
such variant of the partition of the object set A into
nonempty subsets A j , j ∈ J m , and the corresponding
placement parameters ui =(vi , zi , θi ) of objects i ,
i ∈ J n , taking into account relations (
We assume that the problem has at least one feasible solution.
Note. Restrictions on the axial and centrifugal moments of the system and allowable distances between objects may also be given.
Now we define special combinatorial configurations describing the discrete structure of the CBLP problem. Some basic approaches for mathematical modelling of optimization problems on combinatorial configurations are described in e.g., [6, 7].
The variants of partition of the set A into non-empty subsets A j , j ∈ J m , are determined by both the number of elements in each subset and the order of the subsets.
Let us consider the sub-containers and the assumed corresponding sets of objects A j , j ∈ J m . Then the tuple of natural numbers (k1, k 2 , ..., k m ) , such that m ∑ k j = n , j=1 determines possible number k j of objects in each subcontainer Ω j . The number of all such tuples is equal to the number of compositions of the number n of length m [8], which is Cnm−−11 .
Let us derive in what ways it is possible to decompose n various objects from a set A into m sub-containers Ω j , j ∈ J m , if in sub-containers there are accordingly k1, k 2 , ..., k m objects, and sets of objects
A j , j ∈ J m , inside corresponding sub-containers Ω j , j ∈ J m , are not ordered.
Without loss of generality, we will distinguish the objects with the same values of metrical characteristics, height hi and mass mi (for example, consider them to be different in number).
We order the elements of set A . To each object we assign the number of the sub-container into which it is expected to be placed. We get a tuple consisting of n elements that form a permutation with repetitions from m numbers 1, 2, ..., m, in which the first element is repeated k1 times, the second element is repeated k 2 times, ..., the last
P(n, k1, k 2 , ..., k m ) = element is repeated k m times.
The total number of permutations is equal to
n ! k1 !⋅ k 2 !⋅...⋅ k m !
Then the number of variants of partitions of various objects from set A to m sub-containers Ω j , provided that each sub-container contains at least one object and the order of placing objects inside the sub-container is not important, is equal to
∑ P(n, k1, k 2 , ..., k m ) = ∑ k1+k2 +...+km =n k1+k2 +...+km =n k1 !⋅ k 2 !⋅...⋅ k m !
Note that the number of summands in the sum is equal to n ! .
(
To generate subsets A j , j ∈ J m , we introduce a special combinatorial configuration [9].
Rather complex combinatorial configurations can formally be described and generated using tools of construction of compositional κ -images of combinatorial sets ( κ -sets) proposed in [10]. A combinatorial set is considered as a set of tuples that constructed from a finite set of arbitrary elements (so-called generating elements) according to certain rules. Permutations, combinations, arrangements, and binary sequences are the examples of classical combinatorial sets.
The basic idea of generation of κ -sets is introduced in [10]. However, the problem of generating κ -sets of more complicated combinatorial structure remains the open problem. Just one of such special cases is studied in [11].
The problem of generating κ -sets is based on special techniques of generating base combinatorial sets. The base sets can be defined as combinatorial sets with the known descriptions: both classical combinatorial sets (permutations, combinations, arrangements, tuples) or non-classical combinatorial sets (permutations of tuples, compositions of permutations, permutations with a prescribed number of cycles, etc.). Generation algorithms for some of base combinatorial sets are presented in, e.g., [12-15].
We denote (n, m) the set of compositions of the number n of length m (which corresponds to the partition of different objects from set A to m sub-containers j ∈ J m , provided that each sub-container contains at least one object and the order of objects inside the sub-container is not important). Wherein, (n, m) = N = Cnm−−11 .
Let
m =(k1,..., k m ) ∈ (n, m) , ∑ k j = n , k j ≥ 1 , j ∈ J m .
j=1
We introduce a combinatorial set () that is a composition image of combinatorial sets ( κ -set) (n, m) ; Cnk1 , C k2 , C k3 , …, C km , generated by sets n1 n2 nm−1 I n0 , I n1 , I n2 , …, I nm−1 , where ni = n − k1 − ... − ki , i ∈ J m−1 , I n0 = J n ,
I n1 = I n0 \ { j1n0 , j2n0 , ..., jkn10 } , ( j1n0 , j2n0 , ..., jkn10 ) ∈ Cnk1 , I n2 = I n1 \ { j1n1 , j2n1 , ..., jkn21 } , ( j1n1 , j2n1 , ..., jkn21 ) ∈ Cnk2 , 1 … I nm−1 = I nm−2 \ { j1nm−2 , j2nm−2 , ..., jknmm−−12 } , ( j1nm−2 , j2nm−2 , ..., jknmm−−12 ) ∈ C km−1 ,
nm−2 I nm−1 = { j1nm−1 , j2nm−1 , ..., jknmm−1} , ( j1nm−1 , j2nm−1 , ..., jknmm−1 ) ∈ C km .
nm−1 Note that
I n0 ∪ I n1 ∪ ... ∪ I nm−1 = J n = {1, 2, ..., n}, I ns ∩ I nt
0 =∅ , s ≠ t ∈ J m−1
={0, 1, ..., m −1} .
Each element q() ∈ () can be described in the form q() = (q1, ..., qk1 qk1+1, ..., qk1+k2 , ...,
qk1+...+km−1 , ..., qkm−1+km ), where (q1, ..., qk1 ) =j2n0 ( j1n0 , , ..., jkn10 ) ∈ Cnk1 , i = 1, 2, .., n, qi ∈{1, 2, .., n}, q() ∈ ().
Let us formalize placement constraints (
We consider two objects 1 and 2 with variable parameters u1 =(v1, z1, θ1) ∈ R 3 , u2 =(v2 , z 2 , θ 2 ) ∈ R 3 , where v1 = (x1, y1), v2 = (x2 , y2 ), x1, y1, θ1 x2 , y2 , θ2 are continuous variables and z1 , z2 are discrete variables.
By definition [2, 3] a phi-function is a continuous function, therefore we extend the concept to discrete variables z1 , z2.
Definition 1. Function ϒ12 (u1, u2 ) is called a D-phifunction of 3D-objects and if function values z1 = z10 and z 2 = z 20 .
Definition 2. Function ϒ′12 (u1, u2 , u12 ) is called a quasi
D-phi-function of 3D-objects, 1 and 2 if function
vi
continuous variables, z =(z1, ..., z n ) ∈ R n , zi , i ∈ J n , are
discrete variables defined by (
The values of variables zi , i ∈ J n , are determined in the order given by elements q() of combinatorial set () :
The cardinality of set () is derived by (
An element q() of the set () is said to be a tuple of partition of the set А into subsets A j , j ∈ J m .
Now we define the vector of the basic variables of the problem СBLP: u =(v, z, θ), where v =(v1, ..., vn ) ∈ R 2n , θ = (θ1, ..., θn ) ∈ R n , =(xi , yi ) ∈ R 2 , xi , yi , θi are (qk1+1, ..., qk1+k2 ) =j2n1 ( j1n1 , , ..., jkn21 ) ∈ Cnk2 , fixed values z1 = z10 and z 2 = z 20 .
1 Here u12 is the vector of auxiliary continuous variables … that is used to constructs a quasi phi-function of two objects (qk1+...+km−1 , ..., qkm−1+km ) =j2nm−1 ( j1nm−1 , , ..., jknmm−1 ) ∈ Cnkmm−1 . 1 and 2 .
The placement constraints (
s
=∑l=1 tl−1 + hqi ,
(
q1q 2 (uq1 , uq 2 , uq1q 2 ) is the function that describes non-overlapping of objects q1 and q2 , uq1 =,yq1 (xq1 , zq1 , θq1 ), uq 2 =,yq (xq 2 2 , z q 2 , θ q 2 ), ϒ*q (uq ) is the function that describes non-overlapping of
i i objects qi and Ω* j
=R 3 / int Ω j .
Thus, in relations (
q1q 2 1 2 1 2 q2 ; ϒ*q i (uq i ) is a phi-function Φq iΩ* j (uq i ) for objects qi and Ω* j .
If the minimum allowable distances between objects are given, adjusted phi-functions (quasi-phi-functions) are used for the corresponding pairs of objects [16, 17].
Mathematical model of the CBLP problem can be defined as follows:
F (u *, τ* )
=min F (u, τ) s.t. (u, τ) ∈W ,
(
2 where
F (u) =d =(xs (v, z) − x0 ) 2 + ( y s (v, z) − y0 ) 2 + (z s − z0 ) 2
u =(v, z, θ), v = (v1, ..., vn ) , θ = (θ1, ..., θn ) ,
vi = (xi , yi ) , i ∈ J n , z = (z1, ..., zn ) ,
m
function ϒ1(u, τ) is described by (
={(q1, q2 ) : q1 < q2 ∈ J nj } , τ = (τ1, ..., τ s ) = (uq q , q1 < q2 ∈ J nj )
1 2
auxiliary variables for quasi phi-functions, s = Ξ , function
ϒ*2 (u) is defined by (
CBLP problem can be represented as a mixed integer programming (MIP) problem, using approach with boolean variables.
However, unlike (
IV. CONCLUSION
We study the problem of the balanced layout of 3D-objects within a container divided by horizontal racks onto subcontainers.
A mathematical model has been constructed that takes into account not only the geometrical and behavior constraints, but also combinatorial features of the problem associated with the construction of partitions of the set of placed objects into sub-containers.