# Optimized Packing Clusters of Objects in a Rectangular Container

Authors: T. Romanova; A. Pankratov; I. Litvinchev; Yu. Pankratova; I. Urniaieva
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

A packing (layout) problem for a number of clusters (groups) composed of convex objects (e.g., circles, ellipses, or convex polygons) is considered. The clusters have to be packed into a given rectangular container subject to nonoverlapping between objects within a cluster. Each cluster is represented by the convex hull of objects that form the cluster. Two clusters are said to be nonoverlapping if their convex hulls do not overlap. A cluster is said to be entirely in the container if so is its convex hull. All objects in the cluster have the same shape (different sizes are allowed) and can be continuously translated and rotated. The objective of optimized packing is constructing a maximum sparse layout for clusters subject to nonoverlapping and containment conditions for clusters and objects. Here the term sparse means that clusters are sufficiently distant one from another. New quasi-phi-functions and phi-functions to describe analytically nonoverlapping, containment and distance constraints for clusters are introduced. The layout problem is then formulated as a nonlinear nonconvex continuous problem. A novel algorithm to search for locally optimal solutions is developed. Computational results are provided to demonstrate the efficiency of our approach. This research is motivated by a container-loading problem; however similar problems arise naturally in many other packing/cutting/clustering issues.


---

## Body

## 1. Introduction

A two-dimensional packing problem of objects in a container is NP-hard [1]. This problem is typical in logistics (transporting rolls of wallpaper, pipes, boxes, paint buckets, etc.,) and also has important applications in computer science, industrial engineering, manufacturing and production processes, healthcare, project portfolio selection, nanophysics, and agriculture (see, e.g., [2] and the references therein).Various shapes of objects were studied. In particular, cutting and packing problems for ellipses are presented in [3–6], circular packing problems are investigated in [7–13], and packing problems for convex polygons are considered in [11–16]. Papers [17–21] are devoted to irregular packing involving arbitrary shaped objects.In many cases the objects are not independent and have to be grouped in a number of certain clusters of nonoverlapping objects. This is typical, for example, for a container loading problem [22], where the objects in a large maritime container may form various clusters according to a type of objects (similar shapes, parts of the same machine). Similarly, clusters can be formed according to a supplier or a client (final destination) to facilitate loading/unloading the container.While the composition of the cluster (number of objects and their shapes) is typically predefined, the overall shape of the cluster is frequently not specified. Bearing in mind a cluster as a number of objects placed in a flexible sack we define the shape of a cluster as a convex hull of the objects in the cluster. Note that the objects are nonoverlapping and the shape of the cluster (convex hull) depends on the layout of the objects in the cluster.Throughout this paper it is assumed homogeneous clusters composed of the same shapes (different sizes are allowed). The number of clusters as well as the number of objects and their shapes and sizes is given. The shape of the cluster is represented by the convex hull of the objects in the cluster. A feasible clusters layout has to meet the following conditions: (a) objects in the cluster are mutually nonoverlapping and (b) clusters are mutually nonoverlapping and nonoverlapping with the complement of the rectangular container.Concerning optimized packing of clusters, different objectives can be used. For example, we may look for the “densest” layout fixing one dimension of the rectangular container and minimizing the other subject to feasibility of the clusters layout. On the contrary, we may fix both dimensions of the container and look for a “sparsest” layout maximizing a certain “distance” between the clusters. This objective is motivated by the need of more space between clusters to facilitate access for their loading/unloading. In this paper the latter approach is used.To the best of our knowledge the problem of optimized packing for clusters of objects was never considered before. The main contributions of the paper are (1) new formulation of the layout problem for clusters of objects; (2) new mathematical modeling tools for representing nonoverlapping and containment of clusters; (3) novel NLP model for optimized packing of clusters; and (4) new algorithm to get initial feasible solution to accelerate a local optimization procedure.The paper is organized as follows. In Section2 a layout problem for clusters of objects is formulated. Section 3 provides nonoverlapping and containment conditions for clusters obtained by phi-function technique. Mathematical model for the optimized layout problem is stated in Section 4. Solution algorithm and numerical experiments are presented in Sections 5 and 6, respectively. Conclusions in Section 7 complete this paper.


## 2. Problem Formulation

LetΩ={(x,y)∈R2:0≤x≤l,0≤y≤w} be a rectangular domain (a container) and Ti, i∈{1,2,…,n}=In, be an ordered collection ofconvex objects. Each object Ti is defined by its metrical characteristics. In particular, an ellipse Ei is defined by its semiaxes ai and bi, a circle Ci is defined by its radius ri, and a convex polygon Ki is defined by its vertices pik=(pikx,piky), k=1,…,li.The position of the objectTi is characterized by the vector of variable placement parameters ui=(vi,θi), where vi=(xi,yi) is a translation vector and θi is a rotation angle. The center of the object coincides with the origin of its local coordinate system. Rotated by an angle θi and translated by a vector vi an object Ti is defined as Ti(ui)={p∈R2:p=vi+M(θi)·p0,∀p0∈Ti0}, where Ti0 denotes nontranslated and nonrotated object Ti and M(θi)=cos⁡θisin⁡θi-sin⁡θicos⁡θi is a standard rotation matrix.Remark 1.
The position of a circleCi is characterized by the motion vector ui=(vi,0)=(xi,yi,0).In this paper we define acluster of objects (or simply acluster) as a group of objects having the same shape. The ordered collection of objects Ti, i=1,…,n, is divided into N clusters Λ1={T1,…,Tn1}, Λ2={Tn1+1,…,Tn2},…,ΛN={TnN-1+1,…,Tn} with respect to index sets Ξ1={1,…,n1}, and Ξ2={n1+1,…,n2},…,ΞN={nN-1+1,…,n}, n=∑q=1Nmq, where mq=card(Ξq), q∈{1,2,…,N}=JN.We introduce vectors ofplacement parameters of clustersΛ1,Λ2,…,ΛN in the form z1=(u1,…,un1), z2=(un1+1,…,un2),…,zN=(unN-1+1,…,un) and use notation Λq(zq) for a cluster Λq that involves moving objects Ti(ui), i∈Ξq.With each clusterΛq(zq)=⋃i∈ΞqTi(ui) we associate the convex hull of objects Ti(ui), i∈Ξq, denoted by Λ⌢q(zq)=convΛq(zq), q∈JN.Throughout this paper the following definitions are used: (1) two clustersΛq(zq) and Λg(zg) do not overlap each other if their convex hulls Λ⌢q(zq) and Λ⌢g(zg) do not overlap, q>g∈JN; (2) a cluster Λq(zq) belongs to a container Ω if its convex hull Λ⌢q(zq) belongs to a container Ω, q∈IN.Cluster Layout Problem CLP. Arrange the collection ofclustersΛq(zq), q∈JN, sufficiently distant one from another into a rectangular container Ω, such that (1)int⁡Tiui∩int⁡Tjuj=⌀,fori>j,i,j∈Σq×Σq,q∈JN,(2)int⁡Λ⌢qzq∩int⁡Λ⌢gzg=⌀,forq>g∈JN,(3)Λ⌢qzq⊂Ωforeachq∈IN,The first constraint assures nonoverlapping of objects within the same cluster and the second guarantees nonoverlapping of clusters, while the third relation presents containment conditions for clusters into Ω.


## 3. Tools of Mathematical Modeling

In this study, we use phi-function technique as a constructive tool for mathematical modeling of placement constraints within the field of Packing&Cutting (see, e.g., [3, 23–25]). For the reader’s convenience we provide definitions of a phi-function (normalized phi-function) and a quasi-phi-function (normalized quasi-phi-function) in the appendix. In this section we introduce new tools to describe placement constraints (2) and (3) analytically.


### 3.1. Nonoverlapping of Objects within a Cluster

To describe relation (1) we use phi-functions and quasi-phi-functions for a pair of different shapes of convex objects.Let us consider two objectsTi(ui) and Tj(uj) that belong to a cluster Λq(zq), i>j, (i,j)∈Σq×Σq, q∈JN.According to the definition of a phi-function [23], we have that ΦTiTj(ui,uj)≥0 if and only if int⁡Ti(ui)∩int⁡Tj(uj)=⌀.From the main property of a quasi-phi-function [3] it follows that if Φ′TiTj(ui,uj,uij)≥0 for some uij, then int⁡Ti(ui)∩int⁡Tj(uj)=⌀, where uij is a vector of extra variables.In particular, we provide nonoverlapping tools for a pair of ellipses, circles, and convex polygons.Quasi-Phi-Function for Two Ellipses. Let Ei(ui) and Ej(uj) be ellipses given by their semiaxes (ai,bi) and (aj,bj), with placement parameters ui=(xi,yi,θi) and uj=(xj,yj,θj).A quasi-phi-function forEi(ui) and Ej(uj) can be defined as(4)Φ′EiEjui,uj,uij=ϕij=x′ijvi,ϕij-x′jivj,ϕij-dijθi,ϕij+djiθj,ϕij,where(5)x′ijvi,ϕij=xicos⁡ϕij-yisin⁡ϕij,x′jivj,ϕij=xjcos⁡ϕij-yjsin⁡ϕij,dijθi,ϕij=bi2+ai2-bi2cos2⁡θi-ϕij,djiθj,ϕij=bj2+aj2-bj2cos2⁡θj-ϕij,ϕij∈R1 is an auxiliary variable (an angle between a straight line passing through the origin of the global coordinate system XOY and axis OX).Phi-Function for Two Circles. Let Ci(vi) and Cj(vj) be circles given by their radii ri and rj with placement parameters vi=(xi,yi) and vj=(xj,yj).A phi-function forC(vi) and Cj(vj) has the form [23] (6)ΦCiCjvi,vj=xi-xj2+yi-yj2-ri+rj2.Quasi-Phi-Function for Two Convex Polygons. Let convex polygons Ki(ui) and Kj(uj) be defined by their vertices pik=(pikx,piky), k=1,…,li, pjk=(pjkx,pjky), k=1,…,lj, with placement parameters ui=(xi,yi,θi) and uj=(xj,yj,θj) and let P(uij)={(x,y):μij=cos⁡ϕij·x+sin⁡ϕij·y+γij≤0} be a half plane.Based on [26] a quasi-phi-function for Ki(ui) and Kj(uj) can be derived in the form(7)Φ′KiKjui,uj,uij=min⁡ΦKiPui,uij,ΦKjP∗uj,uij,where uij=(ϕij,γij)∈R2 is a vector of auxiliary variables,(8)ΦKiPui,uij=min1≤k≤li⁡μijpikis a phi-function for Ki(ui) and P(uij) and(9)ΦKjP∗uj,uij=min1≤k≤lj⁡-μijpjkis a phi-function for Kj(uj) and P∗uij=R2∖int⁡P(uij).


### 3.2. Nonoverlapping of Clusters

Let us describe analytically the placement constraint (2). To this aim we introduce a quasi-phi-function for two objects Λ⌢q(zq) and Λ⌢g(zg).Now we consider an extension of the phi-function technique to convex hulls of clusters of objects. Note that convex hull of objects in a cluster has variable shape and variable metrical characteristics that depend on variable placement parameters of objects in the cluster.LetPqg=x,y:μqgx,y=cos⁡φqg·x+sin⁡φqg·y+γqg≥0 be a half plane with variable placement parameters (φqg,γqg).Proposition 2.
A continuous and everywhere defined function(10)Φ′Λ⌢qΛ⌢gzq,zg,φqg,γqg=min⁡ΦΛ⌢qPqgzq,φqg,γqg,ΦΛ⌢gPqg∗zg,φqg,γqgis a quasi-phi-function for Λ⌢q(zq) and Λ⌢g(zg), where ΦΛ⌢qPqg(zq,φqg,γqg) is a phi-function of Λ⌢q(zq) and a half plane Pqg, ΦΛ⌢gPqg∗(zg,φqg,γqg) is a phi-function of Λ⌢g(zg) and the half plane Pqg∗=R2\int⁡Pqg.Proof.
Based on the properties of a quasi-phi-function [3] defined for two convex objects we can conclude that Φ′Λ⌢qΛ⌢g(zq,zg,φqg,γqg)≥0 if and only if there exists at least one separated line Lqg{(x,y):μqg(x,y)=0} for some φqg, γqg such that Λ⌢q(zq)⊂Pqg and Λ⌢g(zg)⊂Pqg∗ and therefore Λ⌢q(zq)∩Λ⌢g(zg)=⌀ for q>g∈JN.
Next we define a phi-function ofΛ⌢q(zq) and a half plane Pqg in (10) in the form(11)ΦΛ⌢qPqgzq,φqg,γqg=min⁡ΦTiPqgui,φqg,γqg,i∈Ξq,where ΦTiPqg(ui,φqg,γqg) is a phi-function of an object Ti(ui) and half plane Pqg, i∈Ξq.
It follows from the properties of the convex hull ofΛq(zq)=⋃i∈ΞqTi(ui) and characteristics of a separating line between two convex objects that
(1)Λ⌢q(zq)∩Pqg=⌀⇔Λq(zq)∩Pqg=⌀ and therefore Ti(ui)∩Pqg=⌀, for all i∈Ξq. It implies that min⁡{ΦTiPqg(ui,φqg,γqg),i∈Ξq}>0.
(2)int⁡Λ⌢q(zq)∩int⁡Pqg≠⌀⇔int⁡Λq(zq)∩int⁡Pqg≠⌀ and therefore there exists at least one object Ti(ui), such that int⁡Ti(ui)∩int⁡Pqg≠⌀, i∈Ξq. It implies that min⁡{ΦTiPqg(ui,φqg,γqg),i∈Ξq}<0.
(3)int⁡Λ⌢qzq∩int⁡Pqg=⌀∧frΛ⌢qzq∩frPqg≠⌀⇔
( int ⁡ Λ q ( z q ) ∩ int ⁡ P q g = ⌀ ) ∧ f r  Λ q z q ∩ f r P q g ≠ ⌀ and therefore int⁡Ti(ui)∩int⁡Pqg=⌀, for all i∈Ξq, and there exists at least one object Ti(ui), such that frTi(ui)∩frPqg≠⌀, i∈Ξq. It implies that min⁡{ΦTiPqg(ui,φqg,γqg),i∈Ξq}=0.
Thus, the functionΦΛ⌢qPqg(zq,φqg,γqg) defined in (11) is a phi-function for Λ⌢q and a half plane Pqg.
Similarly a phi-function ofΛ⌢g(zg) and a half plane Pqg∗=R2∖int⁡Pqg takes the form(12)ΦΛ⌢gPqg∗zg,φqg,γqg=min⁡ΦTjPqg∗uj,φqg,γqg,j∈Ξg,where ΦTjPqg∗(uj,φqg,γqg) is a phi-function of object Tj(uj), j∈Ξg, and the half plane Pqg∗.
Thus,ΦΛ⌢qPqg(zq,φqg,γqg)≥0 if and only if ΦTiPqg(ui,φqg,γqg)≥0 for each i∈Ξq.
Now we can conclude thatmax(φqg,γqg)⁡Φ′Λ⌢qΛ⌢g(zq,zg,φqg,γqg) is a phi-function for Λ⌢q(zq) and Λ⌢g(zg) and therefore Φ′Λ⌢qΛ⌢g(zq,zg,φqg,γqg) is a quasi-phi-function for the objects.
It should be noted that a quasi-phi-function(13)Φ′Λ⌢qΛ⌢gzq,zg,φqg,γqg-0.5ρis a normalized quasi-phi-function for Λ⌢q(zq) and Λ⌢g(zg) (see the appendix for more details). It means that if ρ>0 is the distance between Λ⌢q(zq) and Λ⌢g(zg), defined in the standard way as a minimum Euclidean pointwise distance, then the inequality Φ′Λ⌢qΛ⌢g(zq,zg,φqg,γqg)-0.5ρ≥0 implies distΛ⌢qzq,Λ⌢gzg≥ρ.Remark 3.
We do not construct convex hulls of clusters to describe nonoverlapping (2) in our problem.
Further we provide nonoverlapping tools (phi-functions) for a half planePqg=x,y:μqgx,y=cos⁡φqg·x+sin⁡φqg·y+γqg≥0 and the following types of objects Ti(ui), i∈Ξq: an ellipse Ei(ui); a circle Ci(vi); and a convex polygon Ki(ui).
Phi-Function for an Ellipse and Half Plane P q g . A phi-function for an ellipse Ei(ui) given by its semiaxes (ai,bi) and half plane Pqg can be defined in the form:(14)ΦEiPqgui,φqg,γqg=xicos⁡φqg+yisin⁡φqg+γqg-ai2-bi2·cos2⁡θi+φqg+bi2.
Phi-Function for a Circle and Half Plane P q g . The phi-function for a circle Ci(vi) given by its radius ri and half plane Pqg is defined in [24] and has the form(15)ΦCiPqgvi,φqg,γqg=xicos⁡φqg+yisin⁡φqg+γqg-ri.
Phi-Function for a Convex Polygon and Half Plane P q g . The phi-function for a convex polygon Ki(ui) given by its vertices pik=(pikx,piky), k=1,…,li, and half plane Pqg is defined in [24] and has the form:(16)ΦKiPqgui,φqg,γqg=mink=1,…,li⁡pikxcos⁡φqg+pikysin⁡φqg+γqg.


### 3.3. Containment of Clusters into a Container

Let us derive a phi-function representing analytically the containment constraint (3), Λ⌢qzq⊂Ω⇔int⁡Λ⌢qzq∩Ω∗=⌀ for each q∈IN, where Ω∗=R2∖int⁡Ω.LetΦTiΩ∗(ui) be a phi-function of objects Ti(ui) and Ω∗, i∈Ξq.Proposition 4.
A continuous and everywhere defined function(17)ΦΛ⌢qΩ∗zq=min⁡ΦTiΩ∗ui,i∈Ξqis a phi-function of Λ⌢q(zq) and the object Ω∗.Proof.
We show that ifΛ⌢q(zq)⊂Ω then Ti⊂Ω⇔int⁡Ti(ui)∩Ω∗=⌀, i∈Ξq.
We assume thatΩ∗=Ω1∗∪Ω2∗∪Ω3∗∪Ω4∗, where Ωs∗={x,y∣gs(x,y)≤0} is a half plane, s=1,2,3,4, g1(x,y)=xi, g2(x,y)=y, g3(x,y)=-x+l, and g4(x,y)=-y+w,
For each half planeΩs∗ we can conclude that
(1)Λ⌢q(zq)∩Ωs∗=⌀⇔Λq(zq)∩Ωs∗=⌀ and therefore Ti(ui)∩Ωs∗=⌀, for all i∈Ξq;
(2)int⁡Λ⌢q∩int⁡Ωs∗≠⌀⇔int⁡Λq(zq)∩int⁡Ωs∗≠⌀ and therefore there exists at least one object Ti(ui), such that int⁡Ti(ui)∩int⁡Ωs∗≠⌀, i∈Ξq;
(3)(int⁡Λ⌢q(zq)∩int⁡Ωs∗=⌀)∧(frΛ⌢q∩frΩs∗≠⌀)⇔(int⁡Λq(zq)∩int⁡Ωs∗=⌀)∧(frΛq(zq)∩frΩs∗≠⌀) and therefore int⁡Ti(ui)∩int⁡Ωs∗=⌀, for all i∈Ξq, and there exists at least one object Ti(ui), such that frTi(ui)∩frΩs∗≠⌀, i∈Ξq.
Thus,Λ⌢q(zq)⊂Ω⇔int⁡Ti(ui)∩Ω∗=⌀, i∈Ξq. It means that ΦΛ⌢qΩ∗(zq)≥0 if and only if ΦTiΩ∗(ui)≥0 for each i∈Ξq.
Now we state by phi-functions containment conditions for the objectΩ∗ and the following types of objects Ti(ui), i∈Ξq: an ellipse Ei(ui); a circle Ci(vi); and a convex polygon Ki(ui).
Phi-Function for an Ellipse Containment. A phi-function for an ellipse E(ui) given by its semiaxes (ai,bi) and the object Ω∗ can be defined in the form (18)ΦEiΩ∗ui=mins=1,…,4⁡gisui,gi1ui=xi-bi2+ai2-bi2cos2⁡θi,gi2ui=yi-bi2+ai2-bi2sin2⁡θi,gi3ui=l-xi-bi2+ai2-bi2cos2⁡θi,gi4ui=w-yi-bi2+ai2-bi2sin2⁡θi.The inequality ΦEiΩ∗(ui)≥0 guarantees that Ei(ui)⊂Ω. We define the phi-function based on the idea of nonoverlapping of an ellipse and half plane introduced in [5].
Phi-Function for a Circle Containment. A phi-function for a circle C(ui) given by its radius ri and the object Ω∗ has the form(19)ΦCiΩ∗ui=mins=1,…,4⁡fisui,gi1ui=xi-ri,gi2ui=yi-ri,gi3ui=-xi+l-ri,gi4ui=-yi+w-ri,The inequality ΦCiΩ∗(ui)≥0 guarantees that Ci(vi)⊂Ω.
Phi-Function for a Convex Polygon Containment. A phi-function for a convex polygon K(ui) given by its vertices pik=(pikx,piky), k=1,…,li, and the object Ω∗ has the form(20)ΦKiΩ∗ui=mins=1,…,4k=1,…,li⁡gspikx,piky.The inequality ΦKiΩ∗(ui)≥0 guarantees that Ki(ui)⊂Ω.


## 3.1. Nonoverlapping of Objects within a Cluster

To describe relation (1) we use phi-functions and quasi-phi-functions for a pair of different shapes of convex objects.Let us consider two objectsTi(ui) and Tj(uj) that belong to a cluster Λq(zq), i>j, (i,j)∈Σq×Σq, q∈JN.According to the definition of a phi-function [23], we have that ΦTiTj(ui,uj)≥0 if and only if int⁡Ti(ui)∩int⁡Tj(uj)=⌀.From the main property of a quasi-phi-function [3] it follows that if Φ′TiTj(ui,uj,uij)≥0 for some uij, then int⁡Ti(ui)∩int⁡Tj(uj)=⌀, where uij is a vector of extra variables.In particular, we provide nonoverlapping tools for a pair of ellipses, circles, and convex polygons.Quasi-Phi-Function for Two Ellipses. Let Ei(ui) and Ej(uj) be ellipses given by their semiaxes (ai,bi) and (aj,bj), with placement parameters ui=(xi,yi,θi) and uj=(xj,yj,θj).A quasi-phi-function forEi(ui) and Ej(uj) can be defined as(4)Φ′EiEjui,uj,uij=ϕij=x′ijvi,ϕij-x′jivj,ϕij-dijθi,ϕij+djiθj,ϕij,where(5)x′ijvi,ϕij=xicos⁡ϕij-yisin⁡ϕij,x′jivj,ϕij=xjcos⁡ϕij-yjsin⁡ϕij,dijθi,ϕij=bi2+ai2-bi2cos2⁡θi-ϕij,djiθj,ϕij=bj2+aj2-bj2cos2⁡θj-ϕij,ϕij∈R1 is an auxiliary variable (an angle between a straight line passing through the origin of the global coordinate system XOY and axis OX).Phi-Function for Two Circles. Let Ci(vi) and Cj(vj) be circles given by their radii ri and rj with placement parameters vi=(xi,yi) and vj=(xj,yj).A phi-function forC(vi) and Cj(vj) has the form [23] (6)ΦCiCjvi,vj=xi-xj2+yi-yj2-ri+rj2.Quasi-Phi-Function for Two Convex Polygons. Let convex polygons Ki(ui) and Kj(uj) be defined by their vertices pik=(pikx,piky), k=1,…,li, pjk=(pjkx,pjky), k=1,…,lj, with placement parameters ui=(xi,yi,θi) and uj=(xj,yj,θj) and let P(uij)={(x,y):μij=cos⁡ϕij·x+sin⁡ϕij·y+γij≤0} be a half plane.Based on [26] a quasi-phi-function for Ki(ui) and Kj(uj) can be derived in the form(7)Φ′KiKjui,uj,uij=min⁡ΦKiPui,uij,ΦKjP∗uj,uij,where uij=(ϕij,γij)∈R2 is a vector of auxiliary variables,(8)ΦKiPui,uij=min1≤k≤li⁡μijpikis a phi-function for Ki(ui) and P(uij) and(9)ΦKjP∗uj,uij=min1≤k≤lj⁡-μijpjkis a phi-function for Kj(uj) and P∗uij=R2∖int⁡P(uij).


## 3.2. Nonoverlapping of Clusters

Let us describe analytically the placement constraint (2). To this aim we introduce a quasi-phi-function for two objects Λ⌢q(zq) and Λ⌢g(zg).Now we consider an extension of the phi-function technique to convex hulls of clusters of objects. Note that convex hull of objects in a cluster has variable shape and variable metrical characteristics that depend on variable placement parameters of objects in the cluster.LetPqg=x,y:μqgx,y=cos⁡φqg·x+sin⁡φqg·y+γqg≥0 be a half plane with variable placement parameters (φqg,γqg).Proposition 2.
A continuous and everywhere defined function(10)Φ′Λ⌢qΛ⌢gzq,zg,φqg,γqg=min⁡ΦΛ⌢qPqgzq,φqg,γqg,ΦΛ⌢gPqg∗zg,φqg,γqgis a quasi-phi-function for Λ⌢q(zq) and Λ⌢g(zg), where ΦΛ⌢qPqg(zq,φqg,γqg) is a phi-function of Λ⌢q(zq) and a half plane Pqg, ΦΛ⌢gPqg∗(zg,φqg,γqg) is a phi-function of Λ⌢g(zg) and the half plane Pqg∗=R2\int⁡Pqg.Proof.
Based on the properties of a quasi-phi-function [3] defined for two convex objects we can conclude that Φ′Λ⌢qΛ⌢g(zq,zg,φqg,γqg)≥0 if and only if there exists at least one separated line Lqg{(x,y):μqg(x,y)=0} for some φqg, γqg such that Λ⌢q(zq)⊂Pqg and Λ⌢g(zg)⊂Pqg∗ and therefore Λ⌢q(zq)∩Λ⌢g(zg)=⌀ for q>g∈JN.
Next we define a phi-function ofΛ⌢q(zq) and a half plane Pqg in (10) in the form(11)ΦΛ⌢qPqgzq,φqg,γqg=min⁡ΦTiPqgui,φqg,γqg,i∈Ξq,where ΦTiPqg(ui,φqg,γqg) is a phi-function of an object Ti(ui) and half plane Pqg, i∈Ξq.
It follows from the properties of the convex hull ofΛq(zq)=⋃i∈ΞqTi(ui) and characteristics of a separating line between two convex objects that
(1)Λ⌢q(zq)∩Pqg=⌀⇔Λq(zq)∩Pqg=⌀ and therefore Ti(ui)∩Pqg=⌀, for all i∈Ξq. It implies that min⁡{ΦTiPqg(ui,φqg,γqg),i∈Ξq}>0.
(2)int⁡Λ⌢q(zq)∩int⁡Pqg≠⌀⇔int⁡Λq(zq)∩int⁡Pqg≠⌀ and therefore there exists at least one object Ti(ui), such that int⁡Ti(ui)∩int⁡Pqg≠⌀, i∈Ξq. It implies that min⁡{ΦTiPqg(ui,φqg,γqg),i∈Ξq}<0.
(3)int⁡Λ⌢qzq∩int⁡Pqg=⌀∧frΛ⌢qzq∩frPqg≠⌀⇔
( int ⁡ Λ q ( z q ) ∩ int ⁡ P q g = ⌀ ) ∧ f r  Λ q z q ∩ f r P q g ≠ ⌀ and therefore int⁡Ti(ui)∩int⁡Pqg=⌀, for all i∈Ξq, and there exists at least one object Ti(ui), such that frTi(ui)∩frPqg≠⌀, i∈Ξq. It implies that min⁡{ΦTiPqg(ui,φqg,γqg),i∈Ξq}=0.
Thus, the functionΦΛ⌢qPqg(zq,φqg,γqg) defined in (11) is a phi-function for Λ⌢q and a half plane Pqg.
Similarly a phi-function ofΛ⌢g(zg) and a half plane Pqg∗=R2∖int⁡Pqg takes the form(12)ΦΛ⌢gPqg∗zg,φqg,γqg=min⁡ΦTjPqg∗uj,φqg,γqg,j∈Ξg,where ΦTjPqg∗(uj,φqg,γqg) is a phi-function of object Tj(uj), j∈Ξg, and the half plane Pqg∗.
Thus,ΦΛ⌢qPqg(zq,φqg,γqg)≥0 if and only if ΦTiPqg(ui,φqg,γqg)≥0 for each i∈Ξq.
Now we can conclude thatmax(φqg,γqg)⁡Φ′Λ⌢qΛ⌢g(zq,zg,φqg,γqg) is a phi-function for Λ⌢q(zq) and Λ⌢g(zg) and therefore Φ′Λ⌢qΛ⌢g(zq,zg,φqg,γqg) is a quasi-phi-function for the objects.
It should be noted that a quasi-phi-function(13)Φ′Λ⌢qΛ⌢gzq,zg,φqg,γqg-0.5ρis a normalized quasi-phi-function for Λ⌢q(zq) and Λ⌢g(zg) (see the appendix for more details). It means that if ρ>0 is the distance between Λ⌢q(zq) and Λ⌢g(zg), defined in the standard way as a minimum Euclidean pointwise distance, then the inequality Φ′Λ⌢qΛ⌢g(zq,zg,φqg,γqg)-0.5ρ≥0 implies distΛ⌢qzq,Λ⌢gzg≥ρ.Remark 3.
We do not construct convex hulls of clusters to describe nonoverlapping (2) in our problem.
Further we provide nonoverlapping tools (phi-functions) for a half planePqg=x,y:μqgx,y=cos⁡φqg·x+sin⁡φqg·y+γqg≥0 and the following types of objects Ti(ui), i∈Ξq: an ellipse Ei(ui); a circle Ci(vi); and a convex polygon Ki(ui).
Phi-Function for an Ellipse and Half Plane P q g . A phi-function for an ellipse Ei(ui) given by its semiaxes (ai,bi) and half plane Pqg can be defined in the form:(14)ΦEiPqgui,φqg,γqg=xicos⁡φqg+yisin⁡φqg+γqg-ai2-bi2·cos2⁡θi+φqg+bi2.
Phi-Function for a Circle and Half Plane P q g . The phi-function for a circle Ci(vi) given by its radius ri and half plane Pqg is defined in [24] and has the form(15)ΦCiPqgvi,φqg,γqg=xicos⁡φqg+yisin⁡φqg+γqg-ri.
Phi-Function for a Convex Polygon and Half Plane P q g . The phi-function for a convex polygon Ki(ui) given by its vertices pik=(pikx,piky), k=1,…,li, and half plane Pqg is defined in [24] and has the form:(16)ΦKiPqgui,φqg,γqg=mink=1,…,li⁡pikxcos⁡φqg+pikysin⁡φqg+γqg.


## 3.3. Containment of Clusters into a Container

Let us derive a phi-function representing analytically the containment constraint (3), Λ⌢qzq⊂Ω⇔int⁡Λ⌢qzq∩Ω∗=⌀ for each q∈IN, where Ω∗=R2∖int⁡Ω.LetΦTiΩ∗(ui) be a phi-function of objects Ti(ui) and Ω∗, i∈Ξq.Proposition 4.
A continuous and everywhere defined function(17)ΦΛ⌢qΩ∗zq=min⁡ΦTiΩ∗ui,i∈Ξqis a phi-function of Λ⌢q(zq) and the object Ω∗.Proof.
We show that ifΛ⌢q(zq)⊂Ω then Ti⊂Ω⇔int⁡Ti(ui)∩Ω∗=⌀, i∈Ξq.
We assume thatΩ∗=Ω1∗∪Ω2∗∪Ω3∗∪Ω4∗, where Ωs∗={x,y∣gs(x,y)≤0} is a half plane, s=1,2,3,4, g1(x,y)=xi, g2(x,y)=y, g3(x,y)=-x+l, and g4(x,y)=-y+w,
For each half planeΩs∗ we can conclude that
(1)Λ⌢q(zq)∩Ωs∗=⌀⇔Λq(zq)∩Ωs∗=⌀ and therefore Ti(ui)∩Ωs∗=⌀, for all i∈Ξq;
(2)int⁡Λ⌢q∩int⁡Ωs∗≠⌀⇔int⁡Λq(zq)∩int⁡Ωs∗≠⌀ and therefore there exists at least one object Ti(ui), such that int⁡Ti(ui)∩int⁡Ωs∗≠⌀, i∈Ξq;
(3)(int⁡Λ⌢q(zq)∩int⁡Ωs∗=⌀)∧(frΛ⌢q∩frΩs∗≠⌀)⇔(int⁡Λq(zq)∩int⁡Ωs∗=⌀)∧(frΛq(zq)∩frΩs∗≠⌀) and therefore int⁡Ti(ui)∩int⁡Ωs∗=⌀, for all i∈Ξq, and there exists at least one object Ti(ui), such that frTi(ui)∩frΩs∗≠⌀, i∈Ξq.
Thus,Λ⌢q(zq)⊂Ω⇔int⁡Ti(ui)∩Ω∗=⌀, i∈Ξq. It means that ΦΛ⌢qΩ∗(zq)≥0 if and only if ΦTiΩ∗(ui)≥0 for each i∈Ξq.
Now we state by phi-functions containment conditions for the objectΩ∗ and the following types of objects Ti(ui), i∈Ξq: an ellipse Ei(ui); a circle Ci(vi); and a convex polygon Ki(ui).
Phi-Function for an Ellipse Containment. A phi-function for an ellipse E(ui) given by its semiaxes (ai,bi) and the object Ω∗ can be defined in the form (18)ΦEiΩ∗ui=mins=1,…,4⁡gisui,gi1ui=xi-bi2+ai2-bi2cos2⁡θi,gi2ui=yi-bi2+ai2-bi2sin2⁡θi,gi3ui=l-xi-bi2+ai2-bi2cos2⁡θi,gi4ui=w-yi-bi2+ai2-bi2sin2⁡θi.The inequality ΦEiΩ∗(ui)≥0 guarantees that Ei(ui)⊂Ω. We define the phi-function based on the idea of nonoverlapping of an ellipse and half plane introduced in [5].
Phi-Function for a Circle Containment. A phi-function for a circle C(ui) given by its radius ri and the object Ω∗ has the form(19)ΦCiΩ∗ui=mins=1,…,4⁡fisui,gi1ui=xi-ri,gi2ui=yi-ri,gi3ui=-xi+l-ri,gi4ui=-yi+w-ri,The inequality ΦCiΩ∗(ui)≥0 guarantees that Ci(vi)⊂Ω.
Phi-Function for a Convex Polygon Containment. A phi-function for a convex polygon K(ui) given by its vertices pik=(pikx,piky), k=1,…,li, and the object Ω∗ has the form(20)ΦKiΩ∗ui=mins=1,…,4k=1,…,li⁡gspikx,piky.The inequality ΦKiΩ∗(ui)≥0 guarantees that Ki(ui)⊂Ω.


## 4. Mathematical Model

A mathematical model for layout clusters of objects in a rectangular domain Ω can be formulated in the form(21)maxu,ϕ,ψ,ρ∈W⊂Rσ⁡ρ,(22)W=u,ϕ,ψ,ρ∈Rσ:Φ′Λ⌢qΛ⌢gzq,zg,φqg,γqg-0.5ρ≥0,q>g∈IN,ρ≥0,Φ′TiTjui,uj,uij≥0,i>j,i,j∈Ξq×Ξq,q∈IN,ΦTiΩ∗ui≥0,i∈In,where ρ is considered as a distance between convex hulls Λ⌢q(zq) and Λ⌢g(zg), u=(u1,u2,…,un) is a vector of placement parameters, ui=(vi,θi), vi=(xi,yi), ψ=(φqg,γqg,q>g∈JN) is a vector of auxiliary variables in a quasi-phi-function of convex hulls Λ⌢q(zq) and Λ⌢g(zg), ϕ=(uij,(i,j)∈Ξq×Ξq,q∈IN) is vector of auxiliary variables in a quasi-phi-function of objects Ti(ui) and Tj(uj), Φ′TiTj(ui,uj,uij) is a quasi-phi-function of objects Ti(ui) and Tj(uj), ΦTiΩ∗(ui) is a phi-function of objects Ti(ui) and Ω∗ defined in (17), Φ′Λ⌢qΛ⌢g(zq,zg,φqg,γqg) is a quasi-phi-function of convex hulls Λ⌢q(zq) and Λ⌢g(zg) defined in (10), and σ=1+3n+τq/2∑q=1Nmq(mq-1)+N(N-1) is the number of the problem variables. τq is a number of auxiliary variables for a function that describes nonoverlapping constraints for a pair of objects Ti(ui) and Tj(uj), (i,j)∈Ξq×Ξq, q∈IN. In particular, τq=0 for two circles, τq=1 for two ellipses, and τq=2 for two convex polygons (see Section 3.1).Remark 5.
In the case of two circlesCi(ui) and Cj(uj) we use a phi-function ΦCiCj(ui,uj) instead of a quasi-phi-function Φ′TiTj(ui,uj,uij).
The feasible regionW given by (22) is defined by a system of inequalities with differentiable functions. Our models (21)-(22) are a nonconvex and continuous nonlinear programming problem. This is an exact formulation in the sense that it gives all optimal solutions to the layout problem.
The models (21)-(22) involve O∑q=1Nmq2+ON2 nonlinear inequalities and O(∑q=1Nmq2)+ON2 variables due to the auxiliary variables in quasi-phi-functions.
We develop an efficient approach that employs a new algorithm for generating initial feasible solutions to search for local extrema of problems (21)-(22).


## 5. Solution Algorithm

Our solution strategy is based on the multistart algorithm and consists of three major stages: (1) generate a set of feasible starting points for the problems (21)-(22); (2) search for a set of local maxima for the problems (21)-(22) starting from each feasible point obtained at Stage (1); (3) choose the best local maxima from those found at Stage (2).To generate feasible starting points of the problems (21)-(22) we develop a special algorithmCSPA (ClusterStartingPointsAlgorithm) that involves the followingSteps.Step 1.
With each clusterΛq(zq) we associate a circular region λCq with variable center point vq=(xq,yq) and variable radius λRq, where λ is a scaling parameter and Rq=∑i∈ΞqSi, Si is the area of object Ti, i∈Ξq, q∈IN.Step 2.
Then we grow up all circular regionsλCq, q∈IN, within a rectangular container Ω as much as possible, solving the following NLP subproblem:(23)maxv,λ∈V⁡λ,(24)V=v,λ∈R2N+1:ΦCqCgvq,vg,λ≥0,q>g∈IN,ΦCqΩ∗vq,λ≥0,q∈IN,λ≥0,where v=(v1,v2,…,vN) is a vector of variable placement parameters of circular areas λCq, q∈IN;
Φ C q C g ( v q , v g , λ ) is a phi-function of circular areas λCq and λCg with center points vq=(xq,yq) and vg=(xg,yg) and appropriate radii λRq and λRg, q>g∈IN, (25)ΦCqCgvq,vg,λ=xq-xg2+yq-yg2-λRq+λRg2;ΦCqΩ∗(vq,λ) is a phi-function of a circular area λCq and the object Ω∗=R2∖int⁡Ω, q∈IN,(26)ΦCqΩ∗vq,λ=mins=1,…,4⁡fqsvq,λ,fq1vq,λ=xq-λRq,fq2vq,λ=yq-λRq,fq3vq,λ=l-xq-λRq,fq4vq,λ=w-yq-λRq.We search for a local maximum of problems (23)-(24) starting from a feasible point (v0=(v10,v20,…,vN0),λ0=0), where vq0∈Ω and q∈IN are randomly generated points. Denote a local maximum point of problems (23)-(24) by (v∗,λ∗).Step 3.
Next we derive starting values of variablesφqg0, γqg0 (obtained by trivial geometrical calculations); for each quasi-phi-function Φ′Λ⌢qΛ⌢g(zq,zg,φqg,γqg), q>g∈IN in the problems (21)-(22). These variables are considered as parameters of separating lines between each pair of circular areas λ∗Cq and λ∗Cg of radii λ∗Rq and λ∗Rg with center points vq∗ and vg∗, q>g∈IN.Step 4.
Then we search for feasible points of the problems (21)-(22) solving the following NLP subproblem:(27)maxu,ϕ,ψ,β∈G⁡β,(28)G=u,ϕ,ψ,β∈Rσ:Φ′Λ⌢qΛ⌢gzq,zg,φqg,γqg,β≥0,q>g∈IN,0≤β≤1,Φ′TiTjui,uj,uij,β≥0,i>j,i,j∈Ξq×Ξq,q∈IN,ΦTiΩ∗ui,μ≥0,i∈In,where u=(u1,u2,…,un), ui=(vi,θi), vi=(xi,yi), and ψ=(φqg,γqg,q>g∈JN); β is a scaling parameter of our objects; ϕ=(uij,(i,j)∈Ξq×Ξq,q∈IN) is a vector of auxiliary variables in a quasi-phi-function of objects βTi(ui) and βTj(uj); Φ′TiTj(ui,uj,uij,β) is a quasi-phi-function of objects βTi(ui) and βTj(uj); ΦTiΩ∗(ui) is a phi-function of objects βTi(ui) and Ω∗;Φ′Λ⌢qΛ⌢g(zq,zg,φqg,γqg,β) is a quasi-phi-function for two clusters defined in (10); σ=1+3n+τq/2∑q=1Nmq(mq-1)+N(N-1) is the number of the problem variables, and τq is the number of auxiliary variables.We use a feasible starting point(u0,ϕ0,ψ0,β0=0) to solve the problems (27)-(28), where ψ0=(φqg0,γqg0,q>g∈JN) is obtained at Step 3; vi0=(xi0,yi0)∈Cq is a vector of random generated translation parameters and θi0∈[0,2π] is a randomly generated rotation parameter of object βTi(ui) for i∈Ξq, q∈IN; ϕ0=(uij0,(i,j)∈Ξq×Ξq,q∈IN), and a vector uij0 of auxiliary variables is found from the trivial geometrical calculations depending on the object shape (except circles) such that Φ′TiTj(ui0,uj0,uij0,β0=0)≥0. In particular, for two ellipses uij0=ϕij0 and for two convex polygons uij0=(ϕij0,γij0) (see Section 3.1).Global maximum of the problems (27)-(28) (i.e., β∗=1) provides a feasible solution of the problems (21)-(22). A point of global maximum can be used as a starting point to search for local maximum of the problems (21)-(22).Remark 6.
Application of the decomposition algorithm described in [3] is recommended to solve the problem (21)-(22), when mq≥11 for clusters Λq(zq), q∈JN, in order to reduce the computational costs (time and memory).


## 6. Computational Results

Here we present a number of examples to demonstrate the efficiency of our methodology. We have run all experiments on an AMD FX(tm)-6100, 3.30 GHz computer, Programming Language C++, Windows 7. For the local optimisation we use the IPOPT code https://projects.coin-or.org/Ipopt), developed in [27]. Default options were used for running this software.We present our new instances for the layout problem in a rectangular containerΩ={(x,y)∈R2:0≤x≤l=15,0≤y≤w=15}. We run our program 100 times for each example.Example 1.
An ordered collection ofn=30 ellipses is given. The collection of ellipses is divided into N=3 clusters Λq(zq), q=1,2,3:m1=10, m2=10, and m3=10.
All ellipses are defined by their sizesai,bi,i=1,…,30 = (2.0 1.5), (1.8 1.5), (1.6 1.5), (1.5 1.2), (1.3 1.0), (1.2 0.9), (1.1 0.8), (1.0 0.75), (0.9 0.6), (0.8 0.5), (0.7 0.3), (2.0 1.5), (1.8 1.5), (1.6 1.5), (1.5 1.2), (1.3 1.0), (1.2 0.9), (1.1 0.8), (1.0 0.75), (0.9 0.6), (0.8 0.5), (0.7 0.3), (2.0 1.5), (1.8 1.5), (1.6 1.5), (1.5 1.2), (1.3 1.0), (1.2 0.9), (1.1 0.8), (1.0 0.75).
Our Result
Placement Parameters of Ellipses. x i , y i , θ i , i = 1 , … , 30 = (10.469949 12.267537 2.244218), (7.279733 12.352075 2.063582), (2.471444 12.548774 13.249926), (8.464111 9.691723 0.145847), (12.920038 11.433172 5.530417), (4.909339 12.890715 1.640578), (4.716335 10.894489 0.195532), (13.092110 13.335890 6.393843), (10.806375 9.993924 -0.401328), (6.267221 10.149879 6.032813), (0.813462 5.582920 1.582319), (2.129866 4.016161 2.043699), (4.516627 2.106510 5.713416), (2.014535 8.617626 4.606157), (5.875381 7.080877 1.710554), (5.246435 4.663067 0.181324), (3.712908 6.439680 3.845887), (1.613133 1.313706 6.313737), (4.250763 8.301450 4.942235), (1.768064 6.435263 0.065954), (13.527926 1.206001 2.906999), (10.087641 4.308896 2.501728), (12.390656 5.699737 2.716022), (8.409176 2.472279 4.931800), (9.003824 5.818192 1.638294), (13.004545 2.937130 5.336177), (13.095024 8.392657 -0.572537), (10.944860 1.726727 0.720864), (10.969680 7.572605 5.373848), (10.898378 3.513018 -0.101262).
The value of objective function isρ∗= 2.109291, while the computational time is 7131.446 sec.
Corresponding optimized layout is presented in Figure1.Figure 1
Local optimal arrangement of clusters in Example1.Example 2.
An ordered collection ofn=36 circles is given. The collection of circles is divided into N=4 clusters Λq(zq), q=1,2,3,4:m1=10, m2=10, m3=8, and m4=8.
All circles are defined by their radii:
r i , i = 1 , … , 36 = (1.495), (1.500), (1.501), (1.206), (1.009), (0.912), (0.815), (0.765), (0.621), (0.524), (0.336), (1.550), (1.533), (1.512), (1.239), (1.042), (0.945), (0.848), (0.7925), (0.654), (0.557), (0.380), (1.605), (1.566), (1.523), (1.272), (1.075), (0.978), (0.881), (0.820), (0.687), (0.590), (0.424), (1.660), (1.599), (1.534)
Our Result
Placement Parameters of Circles. { ( x i , y i ) , i = 1 , … , 36 }=(13.089089 1.910911), (9.282866 1.915911), (11.652953 4.566297), (13.378089 7.152616), (9.147148 4.421237), (11.269926 6.948703), (9.688888 6.189878), (13.819089 5.231585), (13.954597 3.846912), (11.189529 2.595038), (3.381819 14.237068), (4.209528 11.030014), (6.318116 8.780847), (1.927911 13.072089), (2.506044 8.821697), (6.003824 12.979437), (1.360911 10.681408), (6.604792 11.144527), (4.222026 13.460604), (4.247002 8.078382), (3.849810 0.972911), (4.971098 4.766312), (5.740826 2.020911), (1.981911 1.981911), (1.938911 5.681867), (6.544523 5.269738), (3.814234 3.883877), (4.418702 6.006885), (13.509939 9.758354), (11.287589 11.489670), (11.993830 10.158402), (13.994089 11.147396), (11.771968 9.049173), (9.264512 12.924089), (9.777002 9.600308), (13.050089 13.050089).
The value of objective function isρ∗=0.415912, while the computational time is 484.461sec.
Corresponding optimized layout is presented in Figure2.Figure 2
Local optimal arrangement of clusters in Example2.Example 3.
An ordered collection ofn=36 objects is given. The collection of ellipses is divided into N=4 clusters Λq(zq), q=1,2,3,4:m1=10 circles, m2=10 circles, m3=8 ellipses, and m4=8 ellipses.
All circles are defined by their radii:
{ ( r i ) , i = 1 , … , 20 }=(1.5), (1.5), (1.5), (1.2), (1.0), (0.9), (0.8), (0.75), (0.6), (0.5), (0.3), (1.5), (1.5), (1.5), (1.2), (1.0), (0.9), (0.8), (0.75), (0.6)
All ellipses are defined by their semi axes:
{ ( a i , b i ) , i = 21 , … , 36 }=(0.8 0.5), (0.7 0.3), (2.0 1.5), (1.8 1.5), (1.6 1.5), (1.5 1.2), (1.3 1.0), (1.2 0.9), (1.1 0.8), (1.0 0.75), (0.9 0.6), (0.8 0.5), (0.7 0.3), (2.0 1.5), (1.8 1.5), (1.6 1.5).
Our Result
Placement Parameters of Circles. { ( x i , y i ) , i = 1 , . . , 20 }=(5.969333, 5.831559), (1.910221, 4.910224), (1.910221, 1.910223), (4.593503, 1.610221), (3.633171, 6.721701), (3.920715, 3.599532), (5.620213, 3.558210), (1.160222, 7.031545), (4.001869, 5.097335), (6.120123, 2.358173), (11.629726, 8.900163), (13.089779, 13.089779), (13.089779 10.089779), (8.950916, 11.115733), (10.406497,13.389779), (7.836995, 8.063426), (9.688425, 8.490281), (10.812773, 9.765367), (11.294872, 11.568861), (7.474932, 9.621922).
Placement Parameters of Ellipses. { ( x i , y i , θ i ) , i = 21 , . . , 36 }=(11.912729 0.916670 9.295412), (10.183793 0.775760 -0.039353), (9.620035 5.473407 -0.639827), (11.012582 2.782653 -3.922661), (12.998276 6.515842 -3.441852), (8.195878 1.909350 1.627631), (13.574899 3.775017 13.927174), (13.533974 1.475715 3.943306), (4.818922 13.635480 -0.705039), (6.200920 12.630733 3.035222), (6.736535 13.971098 -0.026565), (3.486483 11.514966 5.442422), (4.430982 12.359577 0.186450), (4.973013 10.072013 -1.233481), (2.113962 12.981281 2.518350), (1.910433 9.773977 17.233423).
The value of objective function isρ∗= 0.410222, while the computational time is 1344.9 sec.
Corresponding optimized layout is presented in Figure3.Figure 3
Local optimal arrangement of clusters in Example3.Example 4.
An ordered collection ofn=36 objects is given. The collection of objects is divided into N=4 clusters Λq(zq), q=1,2,3,4; m1=10 circles, m2=10 circles, m3=8 ellipses, and m4=8 ellipses.
All circles are defined by their radii:
{ ( r i ) , i = 1 , … , 20 }=(1.625), (1.575), (1.525), (1.275), (1.075), (0.975), (0.875), (0.8125), (0.675), (0.575), (0.400), (1.625), (1.575), (1.525), (1.275), (1.075), (0.975), (0.875), (0.8125), (0.675)
All ellipses are defined by their semi axes:
{ ( a i , b i ) , i = 21 , … , 36 }=(0.8 0.5), (0.7 0.3), (2.0 1.5), (1.8 1.5), (1.6 1.5), (1.5 1.2), (1.3 1.0), (1.2 0.9), (1.1 0.8), (1.0 0.75), (0.9 0.6), (0.8 0.5), (0.7 0.3), (2.0 1.5), (1.8 1.5), (1.6 1.5).
Our Result
Placement Parameters of Circles. { ( x i , y i ) , i = 1 , … , 20 } = (5.025933 1.876324), (1.826324 1.826324), (3.974219 6.518053), (6.563760 7.583078), (3.350845 3.993889), (1.451364 5.929808), (6.228908 4.078766), (1.109501 4.136463), (6.051897 5.654399), (4.881146 4.620133), (2.547234 11.199363), (1.876324 13.109992), (1.826324 9.360637), (7.011083 11.353004), (4.211329 11.390181), (8.183466 13.673676), (4.390190 13.773676), (6.234106 13.623755), (4.213121 9.302682), (5.668491 9.610177).
Placement Parameters of Ellipses. { ( x i , y i , θ i ) , i = 21 , … , 36 } = (11.954503 13.951223 14.239492), (11.755667 12.554007 2.556380), (9.866202 7.871985 -11.985510), (13.200316 7.946103 4.316218), (11.218788 10.594559 -25.265057), (13.543329 13.252969 -23.435600), (10.483036 13.231361 1.774510), (13.776518 10.616527 16.797305), (8.189442 2.594354 -21.480649), (7.771967 1.076809 22.539607), (14.052522 1.182705 20.790155), (9.223332 1.011216 -8.266075), (14.056688 2.541830 -19.537970), (11.441889 1.774003 -12.367135), (12.971454 4.412810 -15.416986), (9.596560 4.458588 44.002983).
The value of objective function isρ∗=0.251325, while the computational time is 1285.73 sec.
Corresponding optimized layout is presented in Figure4.Figure 4
Local optimal arrangement of clusters in Example4.Example 5.
An ordered collection ofn=36 objects is given. The collection of objects is divided into N=4 clusters Λq(zq), q=1,2,3,4: m1=10 convex polygons, m2=10 circles, m3=8 ellipses, and m4=8 ellipses.
All polygons are defined by their vertices:
p i k x , p i k y , k = 1 , . . . , 6 , i = 1 , … , 10 =(1.975377 0.234652), (0.716736 1.400371), (-1.258641 1.165719), (-1.975377 -0.234652), (-0.716736 -1.400371), (1.258641 -1.165719), (1.711902 0.463525), (0.374241 1.467221), (-1.337661 1.003696), (-1.711902 -0.463525), (-0.374241 -1.467221), (1.337661 -1.003696), (1.425610 0.680986), (0.083738 1.497944), (-1.341873 0.816959), (-1.425610 -0.680986), (-0.083738 -1.497944), (1.341873 -0.816959), (1.213525 0.705342), (-0.156793 1.193426), (-1.370318 0.488084), (-1.213525 -0.705342), (0.156793 -1.193426), (1.370318 -0.488084), {(0.919239 0.707107), (-0.336465 0.965926), (-1.255704 0.258819), (-0.919239 -0.707107), (0.336465 -0.965926), (1.255704 -0.258819), (0.705342 0.728115), (-0.488084 0.822191), (-1.193426 0.094076), (-0.705342 -0.728115), (0.488084 -0.822191), (1.193426 -0.094076), (0.499390 0.712805), (-0.599103 0.670936), (-1.098492 -0.041869), (-0.499390 -0.712805), (0.599103 -0.670936), (1.098492 0.041869), (0.309017 0.713292), (-0.669131 0.557359), (-0.978148 -0.155934), (-0.309017 -0.713292), (0.669131 -0.557359), (0.978148 0.155934), (0.140791 0.592613), (-0.699431 0.377592), (-0.840222 -0.215021), (-0.140791 -0.592613), (0.699431 -0.377592), (0.840222 0.215021), (0.062767 0.498459), (-0.659301 0.283203), (-0.722068 -0.215256), (-0.062767 -0.498459), (0.659301 -0.283203), (0.722068 0.215256).
All circles are defined by their radii:
{ r i , i = 11 , … , 20 }=(0.336, 1.55, 1.533, 1.512, 1.239, 1.042, 0.945, 0.848, 0.7925, 0.654
All ellipses are defined by their semi axes:
a i , b i , i = 21 , … , 36=(0.8 0.5), (0.7 0.3), (2.0 1.5), (1.8 1.5), (1.6 1.5), (1.5 1.2), (1.3 1.0), (1.2 0.9), (1.1 0.8), (1.0 0.75), (0.9 0.6), (0.8 0.5), (0.7 0.3), (2.0 1.5), (1.8 1.5), (1.6 1.5).
Our Result
Placement Parameters of Polygons. { ( x i , y i , θ i ) , i = 1 , … , 10 } = (3.447806 9.597127 2.606907), (4.632826 12.154203 6.031453), (1.935707 13.328641 2.695960), (7.137488 11.281372 4.553086), (6.594090 13.766083 3.344861), (6.187148 9.257646 -0.386618), (1.270813 11.108185 0.670004), (5.355596 7.966335 0.229233), (4.062287 14.055842 3.636614), (7.862803 9.559287 6.671758)
Placement Parameters of Circles. { ( x i , y i ) , i = 11 , … , 20 } = (14.242145 4.607830), (11.278663 1.905800), (8.391616 6.969211), (9.039026 3.993831), (11.103865 5.862139), (13.546072 3.321421), (13.699200 1.300800), (8.985716 1.203801), (13.126975 5.194957), (11.917846 4.076973).
Placement Parameters of Ellipses. { ( x i , y i , θ i ) , i = 21 , … , 36 } = ((3.646227 1.155469 1.533947), (1.038618 8.531725 0.246199), (2.256484 6.610724 0.489860), (5.799650 1.865204 6.453077), (5.363840 4.958834 1.597596), (1.798943 1.623608 5.811350), (1.423676 4.102206 7.386076), (3.423022 3.445736 4.374109), (9.931251 9.996600 5.101874), (11.636070 11.136792 2.665959), (13.383614 11.035564 2.838929), (13.844824 7.219741 6.333814), (14.343409 10.348285 1.605276), (12.459639 8.974386 0.003111), (9.963431 12.848701 1.699000), (13.051879 13.13605 10.285045).
The value of objective function isρ∗=0.355801, while the computational time is 4625.15 sec.
Corresponding optimized layout is presented in Figure5.Figure 5
Local optimal arrangement of clusters in Example5.Example 6.
An ordered collection ofn=30 objects is given. The collection of objects is divided into N=3 clusters Λq(zq), q=1,2,3:m1=10 convex polygons, m2=10 circles, and m3=10 ellipses.
All polygons are defined by their vertices:
p i k x , p i k y , k = 1 , … , 6 , i = 1 , … , 10 = (2.000000 0.000000), (1.000000 1.732051), (-1.000000 1.732051), (-2.000000 0.000000), (-1.000000 -1.732051), (1.000000 -1.732051), (1.800000 0.000000), (0.900000 1.558846), (-0.900000 1.558846), (-1.800000 0.000000), (-0.900000 -1.558846), (0.900000 -1.558846), (1.700000 0.000000), (0.850000 1.472243), (-0.850000 1.472243), (-1.700000 0.000000), (-0.850000 -1.472243), (0.850000 -1.472243), (1.600000 0.000000), (0.800000 1.385641), (-0.800000 1.385641), (-1.600000 0.000000), (-0.800000 -1.385641), (0.800000 -1.385641), (1.400000 0.000000), (0.700000 1.212436), (-0.700000 1.212436), (-1.400000 0.000000), (-0.700000 -1.212436), (0.700000 -1.212436), (1.300000 0.000000), (0.650000 1.125833), (-0.650000 1.125833), (-1.300000 0.000000), (-0.650000 -1.125833), (0.650000 -1.125833), 1.200000 0.000000), (0.600000 1.039230), (-0.600000 1.039230), (-1.200000 0.000000), (-0.600000 -1.039230), (0.600000 -1.039230), (1.100000 0.000000), (0.550000 0.952628), (-0.550000 0.952628), (-1.100000 0.000000), (-0.550000 -0.952628), (0.550000 -0.952628), (1.000000 0.000000), (0.500000 0.866025), (-0.500000 0.866025), (-1.000000 0.000000), (-0.500000 -0.866025), (0.500000 -0.866025), (0.900000 0.000000), (0.450000 0.779423), (-0.450000 0.779423), (-0.900000 0.000000), (-0.450000 -0.779423), (0.450000 -0.779423).
All circles are defined by their radii:
{ r i , i = 11 , … , 20 }= 0.336, 1.55, 1.533, 1.524, 1.513, 1.242, 1.23, 1.048, 0.951, 0.854.
All ellipses are defined by their semi axes:
{ ( a i , b i ) , i = 21 , … , 30 }=(0.8 0.5), (0.7 0.3), (2.0 1.5), (1.9 1.6), (1.8 1.5), (1.6 1.5), (1.5 1.2), (1.3 1.0), (1.2 0.9), (1.1 0.8).
Our Result
Placement Parameters of Polygons. x i , y i , θ i , i = 1 , … , 10 = (13.006728 7.204303 2.567940), (7.917914 11.613054 4.423250), (13.314400 11.008183 4.712389) (11.061231 13.271814 2.094380), (10.629721 10.486177 3.665191), (10.185459 8.006747 3.615137), (13.586642 13.747413 3.141592), (13.807690 4.598105 2.567940), (8.341396 9.221119 3.376054) (8.985800 14.007219 6.283185)
Placement Parameters of Circles. { ( x i , y i ) , i = 11 , … , 20 } = (8.537177 3.208783), (12.787093 1.765862), (9.700995 1.746357), (4.878381 1.737357), (7.206433 6.712881), (5.794319 4.347302), (9.055276 4.686597), (11.178919 3.862321), (7.286139 1.164357), (7.371932 2.967318).
Placement Parameters of Ellipses. { ( x i , y i , θ i ) , i = 21 , … , 30 } = (0.720674 11.248417 4.850299), (4.490215 8.752444 3.338436), (1.734800 2.740444 1.764414), (1.981734 9.367337 5.537979), (4.912270 13.064601 2.125433), (1.778636 13.250446 3.779380), (1.425379 6.137135 4.902743), (3.677896 7.396278 2.407474), (4.702453 10.211496 2.031648), (3.268506 5.159948 1.494571).
The value of objective function isρ∗= 0.213358, while the computational time is 7986.627 sec.
Corresponding optimized layout is presented in Figure6.Figure 6
Local optimal arrangement of clusters in Example6.


## 7. Conclusions

We consider a new packing (layout) problem for a number of clusters of convex objects. This research is motivated by a container-loading problem; however, we think that similar problems arise naturally in many other packing/cutting/clustering issues. The layout is considered for a rectangular container of a given size subject to nonoverlapping of (continuously translated and rotated) objects within a cluster. The objects are specified by their sizes and have the same shape for the appropriate cluster. Each cluster is represented by the convex hull of objects that form this cluster. It is assumed that two clusters do not overlap each other if so are their convex hulls and a cluster belongs to a rectangular container if the corresponding convex hull does. New tools of mathematical modeling of nonoverlapping and containment for clusters are provided. An extension of the phi-function technique to the cluster convex hulls is presented taking into account variability of their shapes and metrical characteristics. New quasi-phi-functions and phi-functions are introduced. These functions avoid constructing convex hull for each cluster. A novel mathematical model for optimized layout of clusters is considered and stated as a nonlinear continuous problem. A novel algorithm for searching for initial feasible solutions to accelerate a local optimization procedure is developed. Computational results are provided to demonstrate the efficiency of our approach. The computational results are presented for new instances of the layout problem for clusters involving ellipses, circles, and convex polygons.



---

*Source: 4136430-2019-02-05.xml*