Optimized Packings in Space Engineering Applications: Part II

Abstract

This chapter, dedicated to a specific packing optimization scenario of considerable interest in space engineering and logistics, follows a previous one appearing in this volume [1]. Although it is presented as the second part of the whole topical discussion proposed, it can be read independently.

The layout optimization, with balancing conditions, of a given set of 3D-objects, in a container partitioned by horizontal planes into subcontainers, is considered.

We define special combinatorial configurations describing the specific structure of the problem. A mathematical model, based on the combination of the phi-function technique and the introduced configurations, is provided. The model takes into account not only the placement constraints (i.e., nonoverlapping, containment) and the mechanical characteristics of the system but also the combinatorial features relevant to the partitions of the set of objects placed inside the subcontainers. The solution strategy is proposed and the results of numerical experiments are presented.

1 Introduction

Layout instances with balancing conditions belong to the class of NP-hard problems and are a subject of study in computational geometry and operations research [2, 3], where the methods adopted for their solution represent quite a recent branch.

The essence of the problem lies in the search for the optimal placement of a given set of 3D-objects in a container, ensuring the balancing of the system under consideration.

The necessity of taking into account the assigned balancing constraints in optimization layout problems arises in various applied science fields and technologies, such as, for example, in engineering concerning the design of aircraft, ships, submarines, devices, and components, in logistics problems (when packing goods for transportation or storage) [4, 5]. Rocket design and space technology represent an area of particular interest in this class of problems.

At the initial stages of the layout definition of a spacecraft, it is necessary to take into account special constraints on static and dynamic characteristics (center of mass, axial and centrifugal moments of inertia), as described in [6].

In [7,8,9,10], the problems of the layout of cylinders in a cylindrical container with balancing constraints are considered. These publications provide mathematical models with different objective functions. To solve these problems, heuristic algorithms, based on the specific features of each mathematical model, are proposed. Papers [11,12,13] consider mathematical models and methods for solving the layout problem of a given set of objects, with balancing conditions.

In [3], the authors study (NP-hard) placement optimization problems, which cover a wide spectrum of industrial applications, including space engineering. The present chapter considers mathematical modelling tools and a solution strategy for placement problems. A class of 2D/3D geometric objects, called phi-objects, is introduced and considered as mathematical models of real items. The concept of phi-functions is used to describe nonoverlapping and containment constraints. A mathematical model of a basic placement issue is constructed as a constrained optimization problem that takes into account allowable distances between objects. A solution strategy is proposed. As an example, a placement optimization problem with balancing conditions arising in space engineering is considered. This consists in the placement of cylinders and cuboids of given weights and sizes in a parabolic container, divided by parallel axial circles minimizing the deviation of the system center of gravity from a given point. The chapter also provides a number of computational results for 2D and 3D applications.

Paper [13] studies the layout optimization problem, called BLP, of 3D-objects (solid spheres, straight circular cylinders, spherocylinders, straight regular prisms, cuboids, and tori) in a container (with cylindrical, parabolic, or truncated conical shapes) partitioned into sectors by parallel axial circles. The problem takes into account given minimum and maximum allowable distances between objects, as well as balancing conditions in terms of equilibrium, moments of inertia, and stability constraints. A continuous nonlinear programming (NLP) model of the problem is developed using the phi-function technique. The abovementioned paper also considers several BLP variants, providing appropriate mathematical models and solution algorithms, based on nonlinear programming and nonsmooth optimization methods, as well as the relevant computational analysis. In this work, however, the assignment of objects to the container sectors is assumed to be established a priori.

The innovative contribution of this chapter relates to the following points:

• 1. We extend the formulation of the layout optimization problem discussed in [13]. Our new formulation, called CBLP, takes into account not only placement and balancing constraints of the system but also combinatorial features of the problem. These consist, in particular, in the assignment (no longer established a priori) of the given items to the system sectors.

• 2. We investigate the concept of combinatorial configurations to handle the discrete structure of the CBLP problem.

• 3. We define mathematical modelling tools for placement constraints, with both continuous and discrete variables, called D-phi-function and quasi-D-phi-function.

• 4. We provide a mathematical model formulation of the CBLP problem that involves both continuous and discrete variables.

• 5. We propose a solution strategy that uses the novel algorithm for the combinatorial configuration generation.

2 Problem Formulation

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 fixed coordinate system Oxyz, where Oz is the longitudinal axis of symmetry. We assume that container Ω is divided by horizontal planes into subcontainers Ω^j, j ∈ J _m = {1,  … , m}. We denote distances between circles S _j and S _j + 1 by t _j, j ∈ J _m, $\sum \limits_{j=1}^m{t}_j=H$. The center of the base of container Ω is located in the origin of the coordinate system Oxyz.

Let $A=\left\{{𝕋}_i,i\in J_n\right\}$ be a set of homogeneous 3D-objects given by their metrical characteristics. Each object ${𝕋}_i$ of height h _i and mass m _i is defined in its local coordinate system O _i x _i y _i z _i, i ∈ J _n. The location of object ${𝕋}_i$ inside container Ω is defined by vector u _i = (v _i, z _i, θ_i), where (v _i, z _i) is a translation vector in the coordinate system Oxyz, θ_i is a rotation angle of object ${𝕋}_i$ in the plane O _i x _i y _i, where v _i = (x _i, y _i), and the value of z _i, i ∈ J _n, is uniquely defined by subcontainer Ω^j, j ∈ J _m, in which object ${𝕋}_i$ will be placed.

In the BLP problem, the requirement for placing objects in specific subcontainers Ω^j, j ∈ J _m, is known a priori. In this study, the issue of the balanced layout of objects is formulated, considering the 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 circle S _j inside subcontainer Ω^j.

Regarding the placement of object ${𝕋}_i$, i ∈ J _n, inside subcontainer Ω^j the following constraints are imposed:

$$ {z}_i=\sum \limits_{l=1}^j{t}_{l-1}+{h}_i, $$

(1)

where j ∈ J _m.We consider that t ₀ = 0 and ∀i ∈ J _n there exists j ^∗ ∈ J _m: ${h}_i\le {t}_{j^{\ast }}.$

Let ${J}_n^j\subseteq {J}_n$ be a set of indexes of objects which are placed in subcontainer Ω^j, j ∈ J _m:

$$ \underset{j=1}{\overset{m}{\cup }}{J}_n^j={J}_n,\kern0.48em {J}_n^i\cap {J}_n^j=\varnothing, i\ne j\in {J}_m; $$

(2)

$k_j = \vert A^{j}\vert$ is the number of objects which are placed in subcontainer Ω^j, k _j > 0, j ∈ J _m:

$$ \sum \limits_{j=1}^m{k}_j=n. $$

(3)

In addition, the following placement constraints have to be taken into account:

$$int{\mathbb{𝕋}}_{i_1}\cap int{\mathbb{𝕋}}_{i_2}=\varnothing ,i_1<i_2\in J_n^j,j\in J_m,$$

(4)

$${\mathbb{𝕋}}_i\subset {\mathrm{\Omega }}^j,i\in J_n^j,j\in J_m,$$

(5)

$$ {h}^j\le {t}_j,{h}^j=\max \left\{{h}_i^j,i\in {J}_n^j\right\},j\in {J}_m. $$

(6)

We designate a system, formed as a result of the placement of objects ${𝕋}_i$ of the set А in container Ω by Ω_A, and a reference frame of Ω_A by O _s XYZ, where O _s = (x _s(v), y _s(v), z _s(v)) is the mass center of Ω_A:

$$ {x}_s(v)=\frac{\sum \limits_{i=1}^n{m}_i{x}_i}{M},{y}_s(v)=\frac{\sum \limits_{i=1}^n{m}_i{y}_i}{M},{z}_s=\frac{\sum \limits_{i=1}^n{m}_i{z}_i}{M}, $$

(7)

$M=\sum \limits_{i=1}^n{m}_i$ is the mass of system Ω_A and O _s X‖Ox, O _s Y‖Oy, O _s Z‖Oz.

We consider the deviation of the center of mass O _s of system Ω_A from the given point (x ₀, y ₀, z ₀) as the objective function.

Combinatorial Balanced Layout Problem (CBLP)

Define a partition of set A into nonempty subsets A ^j, j ∈ J _m, and the corresponding placement parameters u _i = (v _i, z _i, θ_i) of objects ${𝕋}_i$, i ∈ J _n, such that the objective function is minimized, taking into account relations (2)–(6).

We assume that the problem has at least one feasible solution.

N.B Restrictions on the axial and centrifugal moments of the system and allowable distances between objects may also be given.

3 Mathematical Model

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, for instance, in [14,15,16].

The possibilities of partitioning set A into nonempty 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 subcontainers and the assumed corresponding sets of objects A ^j, j ∈ J _m. Then, the tuple of natural numbers (k ₁, k ₂,  … , k _m), such that $\sum \limits_{j=1}^m{k}_j=n$, denotes the number k _j of objects associated with each subcontainer Ω^j.

The number of all such tuples is equal to the number of compositions of the number n of length m [17], which is $\frac{\left(n-1\right)!}{\left(m-1\right)!\left(n-m\right)!}$.

We shall derive how it is possible to partition a set A of n objects into m subcontainers Ω^j, j ∈ J _m, containing k ₁, k ₂, … , k _m items, respectively, with no ordering condition within each Ω^j. We denote subsets of objects that are placed inside corresponding subcontainers Ω^j by A ^j, j ∈ J _m.

Without loss of generality, we will distinguish the objects with the same values of metrical characteristics, height h _i and mass m _i (for example, providing them with different identification numbers).

We order the elements of set A. We assign to each object the number of the subcontainer 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 k ₁ times, the second element is repeated k ₂ times, ..., the last element is repeated k _m times.

The total number of permutations is equal to:

$$ P\left(n,{k}_1,{k}_2,\dots, {k}_m\right)=\frac{n!}{k_1!\cdot {k}_2!\cdot \dots \cdot {k}_m!}. $$

(8)

Therefore, the total number of partitions of n objects into m subcontainers Ω^j, provided that each Ω^j contains at least one object and the order in which objects are placed inside Ω^j is not considered, is equal to:

$$ \sum \limits_{k_1+{k}_2+\dots +{k}_m=n}P\left(n,{k}_1,{k}_2,\dots, {k}_m\right)=\sum \limits_{k_1+{k}_2+\dots +{k}_m=n}\frac{n!}{k_1!\cdot {k}_2!\cdot \dots \cdot {k}_m!} $$

(9)

Note that the number of summands in (9) is equal to $N=\left|{C}_{n-1}^{m-1}\right|=\frac{\left(n-1\right)!}{\left(m-1\right)!\left(n-m\right)!}.$

To generate subsets A ^j, j ∈ J _m, we introduce a special combinatorial configuration [18].

Rather complex combinatorial configurations can formally be described and generated using compositional κ-images of combinatorial sets (κ-sets) introduced in [19]. A combinatorial set is a set of tuples that are constructed from a finite set of arbitrary elements (so-called generating elements), according to certain rules. Permutations, combinations, and binary sequences are examples of classical combinatorial sets. We describe the concept of κ-sets.

The basic idea of κ-sets generation is introduced in [19]. However, the problem of generating κ-sets of more complicated combinatorial structure remains an open problem. One of these special cases is studied in [20].

The problem of generating κ-sets is based on special techniques of generating basic combinatorial sets. The basic sets can be defined as combinatorial sets with the given features, i.e., both classical combinatorial sets (e.g., permutations, combinations, compositions, partitions, and n-tuples) and nonclassical combinatorial sets (e.g., permutations of tuples, compositions of permutations, and permutations with a prescribed number of cycles). Generation algorithms for basic combinatorial sets are described, e.g., in [21,22,23,24,25].

A generation strategy for the compositional κ-images of combinatorial sets (κ-sets).

We denote as ℂ _ℙ(n, m) the set of compositions of the number n of length m (which corresponds to the partition of different objects from set A into m subcontainers Ω^j, j ∈ J _m), provided that each subcontainer contains at least one object and the order of objects inside the subcontainer is not considered, where, $\left|{\mathbb{C}}_{\mathbb{P}}\left(n,m\right)\right|=N=\left|{C}_{n-1}^{m-1}\right|$.

Let $\mathbb d{k}=\left({k}_1,{k}_2,\dots, {k}_m\right)\in {\mathbb{C}}_{\mathbb{P}}\left(n,m\right)$, $\sum \limits_{j=1}^m{k}_j=n$, k _j ≥ 1, j ∈ J _m.

We introduce a combinatorial set $\mathrm{\mathbb{Q}}\left(\mathbb d{k}\right)$ that is a composition image of combinatorial sets (κ-set) ℂ _ℙ(n, m); ${C}_n^{k_1}$, ${C}_{n_1}^{k_2}$, ${C}_{n_2}^{k_3}$, …, ${C}_{n_{m-1}}^{k_m}$, generated by sets ${I}_{n_0}$, ${I}_{n_1}$, ${I}_{n_2}$, …, ${I}_{n_{m-1}}$, where n _i = n − k ₁ −  …  − k _i, i ∈ J _m − 1,

$$ {I}_{n_0}={J}_n, $$

$$ {I}_{n_1}={I}_{n_0}\backslash \left\{{j}_1^{n_0},{j}_2^{n_0},\dots, {j}_{k_1}^{n_0}\right\},\left({j}_1^{n_0},{j}_2^{n_0},\dots, {j}_{k_1}^{n_0}\right)\in {C}_n^{k_1}, $$

$$ {I}_{n_2}={I}_{n_1}\backslash \left\{{j}_1^{n_1},{j}_2^{n_1},\dots, {j}_{k_2}^{n_1}\right\},\left({j}_1^{n_1},{j}_2^{n_1},\dots, {j}_{k_2}^{n_1}\right)\in {C}_{n_1}^{k_2}, $$

$$ \dots $$

$$ {I}_{n_{m-1}}={I}_{n_{m-2}}\backslash \left\{{j}_1^{n_{m-2}},{j}_2^{n_{m-2}},\dots, {j}_{k_{m-1}}^{n_{m-2}}\right\},\left({j}_1^{n_{m-2}},{j}_2^{n_{m-2}},\dots, {j}_{k_{m-1}}^{n_{m-2}}\right)\in {C}_{n_{m-2}}^{k_{m-1}}, $$

$$ {I}_{n_{m-1}}=\left\{{j}_1^{n_{m-1}},{j}_2^{n_{m-1}},\dots, {j}_{k_m}^{n_{m-1}}\right\},\left({j}_1^{n_{m-1}},{j}_2^{n_{m-1}},\dots, {j}_{k_m}^{n_{m-1}}\right)\in {C}_{n_{m-1}}^{k_m}. $$

Note that

$$ {I}_{n_0}\cup {I}_{n_1}\cup \dots \cup {I}_{n_{m-1}}={J}_n=\left\{1,2,\dots, n\right\}, $$

$$ {I}_{n_s}\cap {I}_{n_t}=\varnothing, s\ne t\in {J}_{m-1}^0=\left\{0,1,\dots, m-1\right\}. $$

Each element $q\left(\mathbb d{k}\right)\in \mathrm{\mathbb{Q}}\left(\mathbb d{k}\right)$ can be described in the form:

$$ q\left(\mathbb d{k}\right)=\left({q}_1,\dots, {q}_{k_1}\left|{q}_{k_1+1},\dots, {q}_{k_1+{k}_2}\right.\left|,\dots, \right.\left|{q}_{k_1+\dots +{k}_{m-1}},\dots, {q}_{k_{m-1}+{k}_m}\right.\right), $$

where $\left({q}_1,\dots, {q}_{k_1}\right)=\left({j}_1^{n_0},{j}_2^{n_0},\dots, {j}_{k_1}^{n_0}\right)\in {C}_n^{k_1}$,

$$ \left({q}_{k_1+1},\dots, {q}_{k_1+{k}_2}\right)=\left({j}_1^{n_1},{j}_2^{n_1},\dots, {j}_{k_2}^{n_1}\right)\in {C}_{n_1}^{k_2}, $$

$$ \dots $$

$$ \left({q}_{k_1+\dots +{k}_{m-1}},\dots, {q}_{k_{m-1}+{k}_m}\right)=\left({j}_1^{n_{m-1}},{j}_2^{n_{m-1}},\dots, {j}_{k_m}^{n_{m-1}}\right)\in {C}_{n_{m-1}}^{k_m}. $$

The cardinality of set $\mathrm{\mathbb{Q}}\left(\mathbb d{k}\right)$ is derived by (9).

An element $q\left(\mathbb d{k}\right)$ of the set $\mathrm{\mathbb{Q}}\left(\mathbb d{k}\right)$ 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 = (v ₁,  … , v _n) ∈ R ²ⁿ, θ = (θ₁,  … , θ_n) ∈ R ⁿ, v _i = (x _i, y _i) ∈ R ², x _i, y _i, θ_i are continuous variables, and z = (z ₁,  … , z _n) ∈ R ⁿ, z _i, i ∈ J _n, are discrete variables defined by (1).

The values of variables z _i, i ∈ J _n, are determined in the order given by elements $q\left(\mathbb d{k}\right)$ of combinatorial set $\mathrm{\mathbb{Q}}\left(\mathbb d{k}\right)$:

$$ {z}_{q_i}=\sum \limits_{l=1}^s{t}_{l-1}+{h}_{q_i}, $$

(10)

where:

$$ s=\left\{\begin{array}{l}1,\mathrm{if}\kern1em i\le {k}_1,\\ {}2,\mathrm{if}\kern1em {k}_1<i\le {k}_1+{k}_2,\\ {}\dots \\ {}m,\mathrm{if}\kern0.75em {k}_1+{k}_2+\dots +{k}_{m-1}<i\le {k}_1+{k}_2+\dots +{k}_m,\end{array}\right. $$

i = 1, 2, .., n, q _i ∈ {1, 2, .., n}, $q\left(\mathbb d{k}\right)\in \mathrm{\mathbb{Q}}\left(\mathbb d{k}\right).$

Let us formalize placement constraints (4)–(6), using the phi-function technique.

We consider two objects ${𝕋}_1$ and ${𝕋}_2$ with variable parameters u ₁ = (v ₁, z ₁, θ₁) ∈R ³, u ₂ = (v ₂, z ₂, θ₂) ∈R ³, where v ₁ = (x ₁, y ₁), v ₂ = (x ₂, y ₂), x ₁, y ₁, θ₁ x ₂, y ₂, θ₂ are continuous variables and z ₁, z ₂ are discrete variables.

By definition [2, 3], a phi-function is a continuous function, therefore we extend the concept to discrete variables z ₁, z ₂.

Definition 1

Function ϒ₁₂(u ₁, u ₂) is called a D-phi-function of 3D-objects ${𝕋}_1$ and ${𝕋}_2$ if function ${\Upsilon}_{12}\left({v}_1,{z}_1^0,{\uptheta}_1,{v}_2,{z}_2^0,{\uptheta}_2\right)$ is a phi-function ${\Phi}_{12}\left({v}_1,{z}_1^0,{\uptheta}_1,{v}_2,{z}_2^0,{\uptheta}_2\right)$ of objects ${𝕋}_1$ and ${𝕋}_2$ for fixed values ${z}_1={z}_1^0$ and ${z}_2={z}_2^0$.

Definition 2

Function ${\Upsilon}_{12}^{\prime}\left({u}_1,{u}_2,{u}_{12}\right)$ is called a quasi-D-phi-function of 3D-objects, ${𝕋}_1$ and ${𝕋}_2$ if function ${\Upsilon}_{12}^{\prime}\left({v}_1,{z}_1^0,{\uptheta}_1,{v}_2,{z}_2^0,{\uptheta}_2,{u}_{12}\right)$ is a quasi-phi-function ${\Phi}_{12}^{\prime}\left({v}_1,{z}_1^0,{\uptheta}_1,{v}_2,{z}_2^0,{\uptheta}_2,{u}_{12}\right)$ of objects ${𝕋}_1$ and ${𝕋}_2$ for fixed values ${z}_1={z}_1^0$ and ${z}_2={z}_2^0$.

Here, u ₁₂ is the vector of auxiliary continuous variables that is used to construct a quasi-phi-function of objects ${𝕋}_1$ and ${𝕋}_2$.

The placement constraints (4)–(6) are described by the system of inequalities ϒ₁(u, τ) ≥ 0, ${\Upsilon}_2^{\ast }(u)\ge 0$, where the inequality ϒ₁(u, τ) ≥ 0 describes the nonoverlapping constraints and the inequality ${\Upsilon}_2^{\ast }(u)\ge 0$ describes the containment constraints:

$$ {\Upsilon}_1\left(u,\tau \right)=\min \left\{{\Upsilon}_1^j\left(u,\tau \right),j\in {J}_m\right\}, $$

$$ {\Upsilon}_1^j\left(u,\tau \right)=\min \left\{{\Upsilon}_{q_1{q}_2}^j\left({u}_{q_1},{u}_{q_2},{u}_{q_1{q}_2}\right),{q}_1<{q}_2\in {J}_n^j\right\}, $$

(11)

$$ \tau =\left({u}_{q_1{q}_2},{q}_1<{q}_2\in {J}_n^j\right), $$

$$ {\Upsilon}_2^{\ast }(u)=\min \left\{{\Upsilon}_2^{\ast j}(u),j\in {J}_m\right\},{\Upsilon}_2^{\ast j}(u)=\min \left\{{\Upsilon}_{q_i}^{\ast}\left({u}_{q_i}\right),{q}_i\in {J}_n^j\right\}, $$

(12)

${\Upsilon}_{q_1{q}_2}^j\left({u}_{q_1},{u}_{q_2},{u}_{q_1{q}_2}\right)$ is the function that describes the nonoverlapping condition between objects ${𝕋}_{q_1}$ and ${𝕋}_{q_2}$, and ${u}_{q_1}=\left({x}_{q_1},{y}_{q_1},{z}_{q_1},{\uptheta}_{q_1}\right),$ ${u}_{q_2}=\left({x}_{q_2},{y}_{q_2},{z}_{q_2},{\uptheta}_{q_2}\right),$ ${\Upsilon}_{q_i}^{\ast}\left({u}_{q_i}\right)$ is the function that describes the nonoverlapping condition between objects ${𝕋}_{q_i}$ and Ω^∗j = R ³/ int Ω^j.

Thus, in expressions (11) and (12) for fixed values ${z}_{q_1}$ and ${z}_{q_2}$, we have: ${\Upsilon}_{q_1{q}_2}^j\left({u}_{q_1},{u}_{q_2}\right)$ is a phi-function [26] ${\Phi}_{q_1{q}_2}^{\mathbb{TT}}\left({u}_{q_1},{u}_{q_2}\right)$ for objects ${𝕋}_{q_1}$ and ${𝕋}_{q_2}$ or a quasi-phi-function [27] ${\Phi^{\prime}}_{q_1{q}_2}^{\mathbb{TT}}\left({u}_{q_1},{u}_{q_2},{u}_{q_1{q}_2}\right)$ for objects ${𝕋}_{q_1}$ and ${𝕋}_{q_2}$; ${\Upsilon}_{q_i}^{\ast}\left({u}_{q_i}\right)$ is a phi-function for objects ${\mathbb{\mathbb{T}}}_{{q}_{i}}$ and ${\Omega}^{\ast j}.$

If a minimum allowable distance condition between objects is given, adjusted phi-functions (quasi-phi-functions) are used for the corresponding pairs of objects [26, 27].

The mathematical model of the CBLP problem can be defined as follows:

$$ F\left({u}^{\ast },{\tau}^{\ast}\right)=\min F\left(u,\tau \right)\kern0.37em \mathrm{s}.\mathrm{t}.\left(u,\tau \right)\in W, $$

(13)

$$ W=\left\{\left(u,\tau \right)\in {\mathbf{R}}^{\sigma }:{\Upsilon}_1\left(u,\tau \right)\ge 0,{\Upsilon}_2^{\ast }(u)\ge 0,\mu (u)\ge 0\right\}, $$

(14)

where:

$$ F(u)=d={\left({x}_s\left(v,z\right)-{x}_0\right)}^2+{\left({y}_s\left(v,z\right)-{y}_0\right)}^2+{\left({z}_s-{z}_0\right)}^2 $$

u = (v, z, θ), v = (v ₁,  … , v _n), θ = (θ₁,  … , θ_n), v _i = (x _i, y _i), i ∈ J _n, v = (v ₁,  … , v _n), θ = (θ₁,  … , θ_n), v _i = (x _i, y _i), i ∈ J _n, z = (z ₁,  … , z _n), function ϒ₁(u, τ) is described by (11) with $\Xi =\underset{j=1}{\overset{m}{\cup }}{\Xi}^j$, ${\Xi}^j=\left\{\left({q}_1,{q}_2\right):{q}_1<{q}_2\in {J}_n^j\right\}$, $\tau =\left({\tau}_1,\dots, {\tau}_s\right)=\left({u}_{q_1{q}_2},{q}_1<{q}_2\in {J}_n^j\right)$ is a vector of auxiliary variables for quasi-phi-functions, s = |Ξ|, function ${\Upsilon}_2^{\ast }(u)$ is defined by (12), elements of vector z are given by (10), and μ(u) ≥ 0 describes the given balancing constraints.

For example, problem (13) and (14) for the layout of cylinders in a cylindrical container takes the form:

$$ \min d,\mathrm{s}.\mathrm{t}.u=\left(v,z\right)\in W, $$

(15)

where:

$$ v=\left({x}_1,{y}_1,\dots, {x}_n,{y}_n\right),\mathrm{z}=\left({z}_1,\dots, {z}_n\right), $$

$$ d={\left[\sum \limits_{i=1}^n{m}_i^{\prime }{x}_i\right]}^2+{\left[\sum \limits_{i=1}^n{m}_i^{\prime }{y}_i\right]}^2+{\left[\sum \limits_{i=1}^n{m}_i^{\prime }{z}_i-{z}_0\right]}^2, $$

and the feasible region W is described by the inequality system:

$$ \left\{\begin{array}{l}{\left({x}_{q_2}-{x}_{q_1}\right)}^2+{\left({y}_{q_2}-{y}_{q_1}\right)}^2-{\left({r}_{q_2}+{r}_{q_1}\right)}^2\ge 0,\\ {}{q}_1,{q}_2\in {\Xi}^j,j\in {J}_m,\\ {}-{x_{q_i}}^2-{y_{q_i}}^2+{\left({R}_{q_i}^z-{r}_{q_i}\right)}^2\ge 0,\\ {}{q}_i\in {\Xi}^j,j\in {J}_m.\end{array}\right. $$

(16)

Note, that ${m}_i^{\prime }=\frac{m_i}{M}= const$, $M=\sum \limits_{i=1}^n{m}_i= const$.

The problem of packing cylinders into cylindrical containers, with balancing conditions, is considered, for instance, in [11, 13].

The CBLP problem can be represented as a mixed integer programming (MIP) problem, using Boolean variables. However, unlike (13) and (14), this approach increases the number of discrete variables and therefore increases the dimension of the CBLP problem.

4 Solution Strategy

The following strategy is used to solve CBLP problems:

• 1. Generate a subset ${\left\{q\left(\mathbb d{k}\right)\right\}}_{\chi}\subset \mathrm{\mathbb{Q}}\left(\mathbb d{k}\right)$ using the concept of the Nested Combinatorial κ-sets.

• 2. Construct a subset ${\left\{{q}^{\prime}\left(\mathbb d{k}\right)\right\}}_{\chi^{\prime }}\subseteq {\left\{q\left(\mathbb d{k}\right)\right\}}_{\chi }$ of tuples that satisfy (6). If ${\left\{{q}^{\prime}\left(\mathbb d{k}\right)\right\}}_{\chi^{\prime }}$ =∅, then go to Step 1.

• 3. Construct a set of feasible starting points $\left\{{u}_0^{\prime}\right\}$ for each tuple from the set ${\left\{{q}^{\prime}\left(\mathbb d{k}\right)\right\}}_{\chi^{\prime }}$, using the algorithm presented in [13].

• 4. Search for a local extremum of problem (13) and (14) for each starting point ${u}_0^{\prime}\in W$ with respect to ${q}^{\prime}\left(\mathbb d{k}\right)\in$ ${\left\{{q}^{\prime}\left(\mathbb d{k}\right)\right\}}_{\chi^{\prime }}$.

• 5. Choose the best of the local extrema found for all tuples of the set ${\left\{{q}^{\prime}\left(\mathbb d{k}\right)\right\}}_{\chi^{\prime }}$ and feasible starting points $\left\{{u}_0^{\prime}\right\}$ as a local optimal solution of problem (13) and (14).

To solve nonlinear programming problems, IPOPT is used, being available as an open noncommercial resource (https://projects.coin-or.org/Ipopt). IPOPT is based on the internal point method described in [28].

4.1 Generation Algorithm of a Subset ${\left\{q\left(\mathbb d{k}\right)\right\}}_{\chi}\subset \mathrm{\mathbb{Q}}\left(\mathbb d{k}\right)$

In order to generate a subset ${\left\{q\left(\mathbb d{k}\right)\right\}}_{\chi}\subset \mathrm{\mathbb{Q}}\left(\mathbb d{k}\right)$, we use the concept of the Nested Combinatorial κ-sets.

Concept of the Nested Combinatorial κ-Sets

To define a structure of the nested combinatorial κ-set, we use the κ-level tree.

Let $i\in {J}_{\upkappa}^0=\left\{0,1,\dots, \upkappa \right\}$, where κ is the number of levels of the tree. At each level of the tree, we have η _i nodes.

And, let

$$ {Y}_{01} \vspace*{-12pt}$$

$$ {Y}_{11},{Y}_{12},\dots, {Y}_{1{\eta}_1}\vspace*{-12pt} $$

$$ {Y}_{21},{Y}_{22},\dots, {Y}_{2{\eta}_2} \vspace*{-16pt} $$

(17)

$$ \dots \vspace*{-16pt} $$

$$ {Y}_{\upkappa 1},{Y}_{\upkappa 2},\dots, {Y}_{\upkappa {\eta}_{\upkappa}} $$

be combinatorial sets that correspond to the nodes of the i-th level of the κ-level tree, i = 0, 1, … , κ.

Each combinatorial set Y _ij of the tree is defined by a finite set β _ij of generative elements of Y _ij, i = 0, 1, … , κ, j = 1, … , η _i. We denote the number of elements of β _ij by n _ij, therefore:

$$ {\eta}_0=1,{\eta}_1=n,{\eta}_2=\sum \limits_{j=1}^{\eta_1}{n}_{2j},{\eta}_3=\sum \limits_{j=1}^{\eta_2}{n}_{3j},\cdots, {\eta}_i=\sum \limits_{j=1}^{\eta_{i-1}}{n}_{ij},{\eta}_{\upkappa}=\sum \limits_{j=1}^{\eta_{\upkappa -1}}{n}_{\upkappa j}. $$

The core idea of the Nested Combinatorial κ-set is based on relationships between generative elements β _ij of each combinatorial set Y _ij of i-th level and elements of combinatorial sets of (i + 1)-th level, using the following correspondence:

$$ \beta \in {\beta}_{ij}\leftrightarrow \left({y}_1,{y}_2,\dots, {y}_{n_l}\right)\in {Y}_{i+1,l},l\in \left\{1,\dots, {\eta}_{i+1}\right\},i\in \left\{0,1,\dots, \upkappa -1\right\}. $$

(18)

A nested combinatorial κ-set is a composed combinatorial set produced by means of the tree structure (17) and correspondence (18) (see [19] for formal definition).

Let us consider an example to make clear the concept. We denote a nested combinatorial κ-set by T _κ.

Example 1

Let T _κ have a two-level structure (17), where Y ₀₁ is a permutation set P(a,b) generated by β ₀₁ = {a, b}; Y ₁₁ is a combination set ${C}_3^2\left(c,d,e\right)$ generated by β ₁₁ = {c, d, e}; and Y ₁₂ is a permutation set P(g,h) generated by β ₁₂ = {g, h} (see Figure1). Therefore, n ₀₁ = 2, n ₁₁ = 3, n ₁₂ = 2, η ₀ = 1, η ₁ = 2.

Figure 1

Two-level structure (17) of the nested combinatorial κ-set T _κ

In order to produce the nested combinatorial set T _κ, we replace the generative elements a, b in each element of P(a,b) by each element of the combinatorial sets ${C}_3^2\left(c,d,e\right)$ and P(g,h) consequently, using correspondence (18) (see Figure 2). Terminal nodes of the tree correspond to elements of the combinatorial set T _κ:(cdgh), (cdhg), (cegh), (cehg), (degh), (dehg), (ghcd), (ghce), (ghde), (hgcd), (hgce), (hgde).

Figure 2

Elements of the combinatorial set T _κ

Details of algorithm for generating a nested combinatorial κ-set are represented in [25].

Now, we consider an example of the algorithm generating $q\left(\mathbb d{k}\right)$.

Example 2

Let the basic sets ℂ _ℙ(5, 2), ${C}_5^{k_1}$, ${C}_{5-{k}_1}^{k_2}$ generated by elements {q ₁, q ₂, q ₃, q ₄, q ₅} be given, k ₁ + k ₂ = n = 5.

Since ${\mathbb{C}}_{\mathbb{P}}\left(5,2\right)=\left\{\left({k}_1^i,{k}_2^i\right)\right\}=\left\{\left(1,4\right),\left(2,3\right),\left(3,2\right),\left(4,1\right)\right\}$, then we have:

• 1. k ₁ = 1,  k ₂ = 4

  ${C}_5^{k_1}={C}_5^1=\left\{\left({q}_1\right),\left({q}_2\right),\left({q}_3\right),\left({q}_4\right),\left({q}_5\right)\right\}$

  ${\displaystyle \begin{array}{l}{C}_{5-{k}_1}^{k_2}={C}_4^4:\left\{\left({q}_2,{q}_3,{q}_4,{q}_5\right)\right\},\left\{\left({q}_1,{q}_3,{q}_4,{q}_5\right)\right\},\left\{\left({q}_1,{q}_2,{q}_4,{q}_5\right)\right\},\\ {}\left\{\left({q}_1,{q}_2,{q}_3,{q}_5\right)\right\},\left\{\left({q}_1,{q}_2,{q}_3,{q}_4\right)\right\}\end{array}}$

• 2. k ₁ = 4,  k ₂ = 1

  ${C}_5^{k_1}={C}_5^4=\Big\{\left({q}_1,{q}_2,{q}_3,{q}_4\right),\left({q}_1,{q}_2,{q}_3,{q}_5\right),\left({q}_1,{q}_2,{q}_4,{q}_5\right),$

  (q ₁, q ₃, q ₄, q ₅), (q ₂, q ₃, q ₄, q ₅)}

  ${C}_{5-{k}_1}^{k_2}={C}_1^1:\left\{\left({q}_5\right)\right\},\left\{\left({q}_4\right)\right\},\left\{\left({q}_3\right)\right\},\left\{\left({q}_2\right)\right\},\left\{\left({q}_1\right)\right\}$

• 3. k ₁ = 2,  k ₂ = 3

  ${C}_5^{k_1}={C}_5^2=\Big\{\left({q}_1,{q}_2\right),\left({q}_1,{q}_3\right),\left({q}_1,{q}_4\right),\left({q}_1,{q}_5\right),\left({q}_2,{q}_3\right),$

  (q ₂, q ₄), (q ₂, q ₅), (q ₃, q ₄), (q ₃, q ₅), (q ₄, q ₅)}

  ${C}_{5-{k}_1}^{k_2}={C}_3^3:\left\{\left({q}_3,{q}_4,{q}_5\right)\right\},\left\{\left({q}_2,{q}_4,{q}_5\right)\right\},\left\{\left({q}_2,{q}_3,{q}_5\right)\right\},$

  {(q ₂, q ₃, q ₄)}, {(q ₁, q ₄, q ₅)}, {(q ₁, q ₃, q ₅)}, {(q ₁, q ₃, q ₄)},

  {(q ₁, q ₂, q ₅)}, {(q ₁, q ₂, q ₄)}, {(q ₁, q ₂, q ₃)}

• 4. k ₁ = 3,  k ₂ = 2

  ${C}_5^{k_1}\!=\!{C}_5^3\!=\!\Big\{\left({q}_1,{q}_2,{q}_3\right),\left({q}_1,{q}_2,{q}_4\right),\left({q}_1,{q}_2,{q}_5\right),\left({q}_1,{q}_3,{q}_4\right),\left({q}_1,{q}_3,{q}_5\right)\!,$

  (q ₁, q ₄, q ₅), (q ₂, q ₃, q ₄), (q ₂, q ₃, q ₅), (q ₂, q ₄, q ₅), (q ₃, q ₄, q ₅)}

  ${C}_{5-{k}_1}^{k_2}={C}_2^2:\left\{\left({q}_4,{q}_5\right)\right\},\left\{\left({q}_3,{q}_5\right)\right\},\left\{\left({q}_3,{q}_4\right)\right\},\left\{\left({q}_2,{q}_5\right)\right\},\left\{\left({q}_2,{q}_4\right)\right\},$

  {(q ₂, q ₃)}, {(q ₁, q ₅)}, {(q ₁, q ₄)}, {(q ₁, q ₃)}, {(q ₁, q ₂)}

Example 3

We show here the κ-set of compositions of two combinations ${C}_5^{k_1}$, ${C}_{5-{k}_1}^{k_2}$ generated by elements {q ₁, q ₂, q ₃, q ₄, q ₅}, k ₁ + k ₂ = n = 5, using the Gen_κ-set algorithm and the results of Example 1. Then, κ=1 and Y ₀ is the set of compositions ℂ _ℙ(5, 2), ${Y}_{11}={C}_5^{k_1}$, ${Y}_{12}={C}_{5-{k}_1}^{k_2}$. Let us present the structure of the κ-set constructed in Example~2.

In the set Y ₀₁, the first generating element k ₁ will be replaced with the unique element of the set Y ₁₁, i.e., with the tuple $\left({q}_{i_1},{q}_{i_2},\dots, {q}_{i_{k_1}}\right)\in {C}_5^{k_1}$, and element k ₂ with the tuple $\left({q}_{j_1},{q}_{j_2},\dots, {q}_{j_{k_2}}\right)\in {C}_5^{k_2}$.

We apply the algorithm presented in [25] to generate all elements of the set $\mathrm{\mathbb{Q}}\left(\mathbb d{k}\right)$ (see Table 1). According to (9), the number of elements in the set $\mathrm{\mathbb{Q}}\left(\mathbb d{k}\right)$ is equal to 30.

Table 1 Data for Example 3 and appropriate elements of set $\mathrm{\mathbb{Q}}\left(\mathbb d{k}\right)$

5 Computational Results

Example 4

We consider the problem (15) and (16) for cylinders ℂ _i, i ∈ J _n that have to be placed into the cylindrical container Ω with one separation plane (circle) in order to minimize the deviation of the center of mass of Ω_A from the given point (x ₀, y ₀, z ₀). Characteristics of cylinders are given in Table 2.

Table 2 Characteristics of cylinders in Example 4

Let m = 2, H = 6, R = 2.5, t ₁ = 3 be the parameters characterizing our cylindrical container and (x ₀, y ₀, z ₀) = (0, 0, 3).

The values of the objective function for all n = 30 tuples of the partition $q\left(\mathbb d{k}\right)\in \mathrm{\mathbb{Q}}\left(\mathbb d{k}\right)$ and appropriate compositions $\mathbb d{k}$ are presented in Table 3.

Table 3 Output data in Example 4

Figure 3 shows the local optimal placements of cylinders in the two subcontainers found by our algorithm that correspond to the tuples: (a) q¹($\mathbb d{k}$), (b) q¹⁸($\mathbb d{k}$) in Example 4.

Figure 3

Balanced layout of cylinders and relevant item projections on the base of the container and separation circle corresponding to tuples: (a) q¹($\mathbb d{k}$), (b) q¹⁸($\mathbb d{k}$) in Example 4

The best value of the objective function in Example 4 is 0.0003 that corresponds to two tuples q¹($\mathbb d{k}$) = (1| 2 3 4 5) and q¹⁸($\mathbb d{k}$) = (3 4| 1 2 5).

Example 5

Let us consider the problem (13) and (14). Let Ω be a cylindrical container of height H = 1 and the basis radius R = 0.55. The container has two separation circles. We assume that t ₁ = t ₂ = 0.35. Let m ₀ = 500 be the mass and (x ₀, y ₀, z ₀) = (0, 0, 0.5) be the center of mass of the cylindrical container Ω.

We consider the collection of 3D-objects of six shapes (Figure 4): $A=\{{𝕊}_i,i=1,\dots ,6,$ ℂ _i, i = 7, … , 13, ℚ _i, i= 14...17, ${𝕊}_{\mathit{ℂi}},i=18,\mathrm{...}21,$ ${\mathbb{P}}_i,i=22,23,24\mathit{c},$ ${𝕂}_{25}\}$ with the following characteristics:

Figure 4

Shapes of objects in Example 5: ${𝕊}_i,$ ℂ _i, ℚ _i, ${𝕊}_{\mathit{ℂi}},$ ℙ _i, ${𝕂}_i$

{m _i, i = 1, .., 25}= {20.944, 15.2681, 27.8764, 20.944, 20.944, 34.5575, 63.7115, 41.8146, 30.4106, 6.28319, 20.1062, 31.4159, 28.4245, 49.9649, 24.8714, 38.6888, 26.2637, 20.7764, 17.2159, 16.8756, 52.8, 52.8, 52.8, 23.1489} are the given masses of the 3D-objects;

r ₁ = 0.1, r ₂ = 0.09, r ₃ = 0.11, r ₄ = 0.11, r ₅ = 0.1, r ₆ = 0.1 are the radii of spheres ${𝕊}_i,i=1,\dots ,6;$

r ₇ = 0.1, h ₇ = 0.11, r ₈ = 0.13, h ₈ = 0.12, r ₉ = 0.11, h ₉ = 0.11, r ₁₀ = 0.11, h ₁₀ = 0.08, r ₁₁ = 0.05, h ₁₁ = 0.08, r ₁₂ = 0.08, h ₁₂ = 0.1, r ₁₃ = 0.1, h ₁₃ = 0.1 are the radii and half-heights of cylinders ℂ _i, i = 7, … , 13;

r ₁₄ = 0.08, h ₁₄ = 0.07, r ₁₅ = 0.09, h ₁₅ = 0.075, r ₁₆ = 0.07, h ₁₆ = 0.06, r ₁₇ = 0.08, h ₁₇ = 0.07 are the radii of the generating circles and half-heights of tori ℚ _i, i= 14...17;

r ₁₈ = 0.1, h ₁₈ = 0.05, l ₁₈ = 0.07, r ₁₉ = 0.05, h ₁₉ = 0.05, l ₁₉ = 0.08, r ₂₀ = 0.08, h ₂₀ = 0.05, l ₂₀ = 0.06, r ₂₁ = 0.08, h ₂₁ = 0.04, l ₂₁ = 0.07 are the radii, half-heights of cylinders, and heights of spherical segments for spherocylinders ${𝕊}_{\mathit{ℂi}},i=18,\mathrm{...}21;$

w _i = 0.11, l _i = 0.1, h _i = 0.12, i = 22, 23, 24 are the half-widths, half-lengths, and half-heights of cuboids ℙ _i, i = 22, 23, 24;

r ₂₅ = 0.09, h ₂₅ = 0.11 are the length of the basis side and half-height of the right hexagonal prism ${𝕂}_{25}$.

The values of the objective function for three chosen tuples of the partition $q\left(\mathbb d{k}\right)\in \mathrm{\mathbb{Q}}\left(\mathbb d{k}\right)$ and appropriate compositions $\mathbb d{k}$ are presented in Table 4.

Table 4 Output data in Example 5

Figure 5 shows the local optimal placement of 3D-objects in subcontainers and the relative object projections onto the separation circles corresponding to tuples: (a) q¹($\mathbb d{k}$), (b) q²($\mathbb d{k}$), (c) q³($\mathbb d{k}$) given in Table 4.

Figure 5

Local optimal placement of 3D-objects and the relative object projections onto the separation circles corresponding to tuples: (a) q¹($\mathbb d{k}$), (b) q²($\mathbb d{k}$), (c) q³($\mathbb d{k}$) in Example 5

The best values found for the objective function in Example 5 is 0.943362 × 10⁻⁷ that corresponds to tuple q³($\mathbb d{k}$) = (1,5,10,17,19,21,22,25|2,4,6,9,12,13,14,18| 3,7,8,11,15,16,20,23,24).

6 Concluding Remarks

This chapter discusses the problem of placing 3D-objects into a container, partitioned into sectors by parallel separation planes, minimizing the distance of the overall center of mass from an assigned position.

The mathematical model formulated for the purpose, on the basis of the phi-function methodology, is illustrated in detail. It takes into account not only the geometrical and balancing constraints, but also the combinatorial features relevant to the assignment of items to sectors.

A solution strategy is provided, which includes the following procedures: generation of partition tuples, based on combinatorial configurations, construction of feasible starting points, and local optimization. This approach implements the multi-start strategy to search for “good” feasible solutions. The results of the numerical experiments show the efficiency of the proposed approach for the class of layout problems considered.