The paper studies the optimal layout problem of 3D-objects. The problem takes into account placement constraints, as well as, behaviour characteristics of the mechanical system. We construct a mathematical model of the problem in the form of a multicriteria optimisation problem and call the problem Multicriteria Balanced Layout Problem (MBLP).
I. INTRODUCTION
3D layout optimisation problems have a wide spectrum of
practical applications. In particular, these problems arise in
space engineering for rocketry design. Their distinctive
feature consists of taking into account behaviour constraints
of a satellite system. Behaviour constraints specify the
requirements for system’s mechanical properties such as
equilibrium, inertia, and stability. Many publications analyze
problems of the equipment layout in modules of spacecraft or
satellites [
In the research we consider the balance layout problem in
the following statement: arrange 3D-objects in a container
taking into account special placement and behaviour
constraints so that the objective function attains its extreme
value [
We consider here an extension of the balanced layout of
3D-objects considered in [
The aim of this study is to develop a mathematical model of 3D layout optimisation problem taking into account behavior constraints in the form of multicriteria optimisation problem. We call the problem the Multicriteria Balanced Layout Problem (MBLP).
To describe placement constraints (non-overlapping of
objects, containment of objects in a container with regard for
the minimal and maximal allowable distances) analytically
we employ phi-function technique [
The variety of forms of objective functions and combinations of placement and behaviour constraints generates various variants of the MBLP problem.
Let Ω ={(x, y, z) ∈ 3 : G(x, y, z) ≥ 0} be a container of given height H . We consider the following types of containers: 1) Ω ≡ C , C is a straight circular cylinder with a base of radius R , G(x, y, z) =min{−x 2 − y 2 + R 2 , −z + H, z} ; 2) Ω ≡ Λ , Λ is a paraboloid of revolution with a base of radius R = H , G(x, y, z) =min{−z − x 2 − y 2 + H, z} ; 3) Ω ≡ Ε , Ε is a
R1 straight circular blunted cone with lower and upper bases of radii and respectively, R 2 < R1 G(x, y, z) =min{−z − H ( x 2 + y 2 − R1) (R1 − R 2 ), −z + H, z} .
Ω is divided by circular racks
Sk , k =2, 1, ..., m + 1 , into subcontainers Ω k , k = 1, 2, ..., m .
We assume that S1 is a base of Ω . Between racks Sk and
={A i , i ∈ I n } , I n = {1, 2, .., n} , involves the following shapes of objects: solid spheres i of radius ri ; straight circular cylinders i of radius ri and height 2h i ; tori i with metric characteristics (ri , h i ) , where ri is the distance from the center of generating circle to the axis of revolution, 2h i is the height of i , h i is the radius of the generating circle; spherocylinders i with metric characteristics (li , ri , h i ) , where li is the height of ball segments, ri is the radius and 2h i is the height of cylinder; straight regular prisms and cuboids i with metric characteristics (h i , v il , ) , where 2h i is the height of i , v il = (x il , y il ) , l = 1, ..., s i , are vertices of the base of i (which is a convex polygon
MBLP: Pack 3D-objects A i ∈ A , i ∈ I n ={1, 2, ..., n} , inside container Ω , so that the vector function attains its extreme value with regard for placement and behaviour constraints.
The placement constraints in the MBLP problem are generated by non-overlapping of objects A i , A j , i > j∈ I n , which have to be placed inside container Ω , and containment of object A i in container Ω , i ∈ I n . In addition, the minimal ρi−j and maximal ρi+j ≥ ρi−j allowable distances between objects A i , A j , i > j∈ I n , may be specified. Also, the minimal allowable distance ρi− between object A i ∈ A , i ∈ I n , and the lateral surface of container Ω may be given. Without loss of generality we set ρi−j =0 (or ρi+j =ϖ ) if a minimal (or a maximal) allowable distance between objects A i and A j is not given, i > j∈ I n . Here ϖ is a given sufficiently great number. In particular, the condition ρij =ρi−j provides the arrangment of objects + A i and A j on the exact distance. We also set ρi− =0 if a minimal allowable distance between object A i and the lateral surface of container Ω is not given.
Placement constraints in the MBLP problem may be presented as the following: ρi−j ≤ dist( A i , A j ) ≤ ρi+j , i > j∈ I n , and dist( A i , Ω*) ≥ ρi− , i = 1, ..., n , where Ω* =3 \ int Ω .
To describe the placement constraints analytically we
employ the phi-function technique [
Let us consider the constraints of mechanical characteristics of system Ω A .
The equilibrium constaints are defined by the following system of inequalities: µ11(u) =min{−(x s (u) − x e ) + ∆x e , (x s (u) − x e ) + ∆x e} ≥ 0 µ12 (u) =min{−(ys (u) − y e ) + ∆y e , (ys (u) − y e ) + ∆y e} ≥ 0 , µ13 (u) =min{−(z s (u) − z e ) + ∆z e , (z s (u) − z e ) + ∆z e} ≥ 0 , where (x e , y e , z e ) is the expected position of Os , (∆x e , ∆y e , ∆z e ) are admissible deviations from the point (x e , y e , z e ) .
The constraints of moments of inertia are defined as the following: µ 21(u) = −J X (u) + ∆J X ≥ 0 , µ 22 (u) = −J Y (u) + ∆J Y ≥ 0 , µ 23 (u) = −J Z (u) + ∆J Z ≥ 0 , where J X (u), J Y (u), J Z (u) are the moments of inertia of the system Ω A with respect to the axes of coordinate system
∆J X , ∆J Y , ∆J Z J X (u), J Y (u), J Z (u) , where are admissible values for
n n J X (u) =J x0 + ∑i1 (J xi cos2 θi + J yi sin 2 θi ) + ∑ (yi2 + zi2 )mi − M(ys2 + zs2 ) , = i =1 n n J Y (u) =J y0 + ∑ (J xi sin 2 θi + J yi cos 2 θi ) + ∑ (x i2 + zi2 )mi − M(x s2 + zs2 ) i =1 i =1 n n J Z (u) = ∑ J zi + ∑ (yi2 + z i2 )mi − M(x s2 + ys2 ) ,
i =0 i =1 J x 0 , J y0 , J z0
are the moments of inertia of container Ω with respect to the axes of the coordinate system Oxyz , J x i , J yi , J zi , i ∈ I n , are the moments of inertia of object А i with respect to the axes of coordinate system Oi x i yiz i .
The stability constraints are defined by the following system of inequalities: µ31(u) =min{−J XY (u) + ∆J XY , J XY (u) + ∆J XY} ≥ 0 , µ32 (u) =min{−J YZ (u) + ∆J YZ , J YZ (u) + ∆J YZ} ≥ 0 , µ33 (u) =min{−J XZ (u) + ∆J XZ , J XZ (u) + ∆J XZ} ≥ 0 , where J XY (u), J YZ (u), J XZ (u) are the products of inertia of system Ω A with respect to the axes of the coordinate system OsXYZ , ∆J XY , ∆J YZ , ∆J XZ are admissible values for J XY (u), J YZ (u), J XZ (u) , respectively, J XY (u)
1 n n =2∑i1 =yi (J x i − J ) sin 2θi + ∑i1 =yimi− x i Mx s y s , n J YZ (u) =∑yiz imi − My sz s , i=1 n J XZ (u) =∑x iz imi − Mx sz s .
i=1
Behaviour constraints of the BLP problem we define as the system of inequalities
µ1(u) ≥ 0, µ 2 (u) ≥ 0, µ3 (u) ≥ 0 , where µ1(u) = min{µ11(u), µ12 (u), µ13 (u)}, µ 2 (u) = min{µ 21(u), µ 22 (u), µ 23 (u)} , µ3 (u) = min{µ31(u), µ32 (u), µ33 (u)}. (1) (2) (3) Here Os = (x s , ys , z s ) is the center of mass of system Ω A , x s (u) = 1 n
∑ mi x i , ys (u) = M i=1 1 n
∑ mi yi , M i=1 z s (u) = 1 n n
∑ m iz i , M = ∑ mi is the mass of system Ω A .
M i=1 i=0
A mathematical model of the MBLP problem can be presented in the form
extrF ( p, u) s.t. (u, p) ∈W (4) W ={(u, p) ∈ ξ : ϒ(u, p) ≥ 0, µ(u, p) ≥ 0, ζ ≥ 0} , (5) where F ( p, u) = (F1( p, u), F2 ( p, u), ..., Fk ( p, u)) , ϒ(u, p) describes placement constraints, ϒ(u, p) = min{ϒ1(u), ϒ 2 (u, p)} , ϒ1(u) is responsible for non-overlapping constraints, ϒ 2 (u, p) is responsible for containment constraints, µ(u) = min{µ s (u), s ∈U t } constraints,
U t ∈ P(U ) , is responsible for
behavior
P(U ) is the power set of U = {1, 2, 3} , functions µ1(u), µ 2 (u), µ 3 (u) are given by (1)(3), ζ ≥ 0 is the system of additional constraints of metric characteristics of container Ω and placement parameters of objects. If s = ∅ , i.e. behavior constraints are not involved in (5), then our objective function F (u) meets mechanical characteristics of system Ω A .
Depending on the different combinations of objective
functions F1( p, u), F2 ( p, u), ..., Fk ( p, u) different variants
of mathematical model (4)-(5) can be generated. The most
frequently occurring objective functions found in related
publications are the following: 1) size of container Ω ; 2)
deviation of the center of mass of system Ω A from a given
point; 3) moments of inertia of system Ω A [
Let us consider some of realisations of model (4) - (5): • F ( p, u) =s.t. p ( p, u) ∈W ⊂ ξ , ={( p, u) ∈ ξ : ϒ1(u) ≥ 0, ϒ 2 ( p, u) ≥ 0,
µ( p, u) ≥ 0, ζ ≥ 0} • F (u)
=d, ( p, u) ∈W ⊂ ξ , d = (xs (u) − xe ) 2 + ( y s (u) − ye ) 2 + (z s (u) − ze ) 2 , ={( p, u) ∈ ξ : ϒ1(u) ≥ 0, ϒ 2 ( p, u) ≥ 0, µ 2 ( p, u) ≥ 0, µ 3 ( p, u) ≥ 0, ζ ≥ 0} ; • F ( p, u) = (F1( p, u) = p, F2 ( p, u) = d ) , ( p, u) ∈W ⊂ ξ ,
={( p, u) ∈ ξ : ϒ1(u) ≥ 0, ϒ 2 ( p, u) ≥ 0, µ 2 ( p, u) ≥ 0, • F ( p, u) = (F1( p, u) = J X ( p, u), F2 ( p, u) = J Y ( p, u), µ 3 ( p, u) ≥ 0, ζ ≥ 0} ; F3 ( p, u) = J Z ( p, u))
( p, u) ∈W ⊂ ξ , µ 3 ( p, u) ≥ 0, ζ ≥ 0} .
={( p, u) ∈ ξ : ϒ1(u) ≥ 0, ϒ 2 ( p, u) ≥ 0, µ1( p, u) ≥ 0, In this paper we formulate the optimisation layout problem of 3D-objects into a container taking into account placement (non-overlapping, containment, distance) and behaviour (equilibrium, inertia and stability) constraints. We call the problem as Multicriteria Balance Layout Problem (MBLP). In order to describe placement constraints analytically we employ phi-function technique. A mathematical model of the problem in the form of multicriteria optimisation problem is proposed.
We also consider some variants of the MBLP problem depending on the forms of the objective functions, shapes of objects and containers, combinations of placement and behavior constraints.
IV. COMPUTATIONAL RESULTS Instance (xe , ye , ze ) (0, 0, 0.275) , t1 0.3 , n 10 , { zi , i 1,...,10 }={0.19, 0.4, 0.19, 0.41, 0.24, 0.35, 0.19, r4 0.11 , r5 0.1 , h5 0.11 , h6 0.12 , r7 0.11 , r8 0.11 , h8 0.08 , r9 0.08 , h9 0.07 , r10 0.09 , vi1 (0.11, 0.1) , vi2 (0.11, 0.1) , vi3 (0.11, 0.1) , vi4 (0.11, 0.1) , i 17,18,19 , The local optimal solution found by NLP-solver in CAS Math 9 is F(u*, u * ) 0.001911 (Fig. 2). A1 { i , i 1,..,16, i , i 65,.., 68} , A1 { i , i 17, .., 32, i , i 69,..., 72} , A2 { i , i 49,..., 64, i , i=77, ..., 80} , A2 { i , i 33,..., 48, i , i 73,..., 76} , vi2 (1.8, 1.8) , vi3 (0.5, 0.5) , vi1 (2.1, 2.1) , vi4 (2.1, 2.1) , vi2 (1.3, 1.3) , vi3 (1.8,1.8) , vi1 (0.5, 0.5) , vi4 (0.5, 0.5) , vi2 (2.1, 2.1) , i 67, 71, 75, 79 , vi3 (1.3,1.3) , vi4 (1.8,1.8) , vi2 (0.5, 0.5) , vi1 (1.3, 1.3) , 3.0, 1.5, 1.5, 1.5, 3.0, 1.5, 3.0, 1.5, 3.0, 3.0, 1.5, 1.5, 1.5, 3.0, 1.5, 3.0, 1.5, 1.5, 3.0, 1.5, 1.5, 3.0, 1.5, 1.5, 3.0, 1.5, 1.5, 1.5, 3.0, 1.5, 1.5, 1.5, 3.0, 1.5, 1.5, 1.5, 3.0, 1.5, 1.5, 1.5, 3.0, 3.0, 1.5, 1.5, 1.5, 3.0, 1.5, 3.0, 1.5, 1.5, 3.0, 1.5, 1.5, 3.0, 1.5, 1.5, 3.0, { hi , i 63,..., 80 }={1.5}, { mi , i 1,..., 80 }={86, 72,