The paper considers mathematical and software for automated design of rational schemes of cutting rectangular materials into flat geometric objects with a complex configuration of external contours. To solve this problem successfully, it is divided into the following four tasks: construction of a set of dense tabs for each of the flat geometric objects; generating a rational cutting scheme (sections) for each of the flat geometric objects; dense placement of sections in the cutting scheme; interactive adjustment of the received cutting scheme. For each of these four problems, mathematical models and methods for solving them are proposed. The tasks were implemented in software for the design of rational schemes for cutting rectangular materials on flat geometric objects with a complex configuration of external contours.
In any industry, the issue of material consumption in production has always been very relevant. High material consumption and significant cost of materials used make the task of minimizing costs especially important for the footwear industry. Rational and economic costs of material and energy resources, as well as protection of the environment from pollution by waste, which arise during the cutting of materials are important tasks of production. Automated design of rational cutting schemes will allow rational use of materials when cutting parts, reduce the amount of waste that pollutes the environment, reduce the cost of products.
Many works have been devoted to the design of rational schemes for cutting materials into flat geometric objects. Mathematical models of compact arrangement of convex flat geometric objects are presented in [1-3]. Guo et al. [1] proposed a tree representation called O-tree: Two ordered trees for the horizontal and vertical directions are used to represent a coded solution Chang et al. [2] extended the result by Guo et al. [1]. They proposed another tree representation called B*-tree; it is easy to implement this data structure and a decoding algorithm for B*-tree runs in linear time with respect to the number of items. Sakanushi et al. [3] proposed another coding scheme called quarter-state sequence. They utilized a string of items and labels to represent a solution and their decoding algorithm runs in linear time of the number of items. But in most cases, the details of the shoes are not convex flat geometric objects.
Okano[4] designed his algorithm for the irregular two-dimensional bin packing problem; however, his technique is also useful for treating the irregular strip packing problem. Lesh et al. [5] proposed a stochastic search variation of the bottom left heuristics for the strip packing problem. Their algorithm outperforms other heuristic and meta heuristic algorithms based on the bottom left strategy reported in the literature. Imahori et al. [6] proposed an improved meta heuristic algorithm based on sequence pair representation. Meta heuristic algorithms generate numer-ous number of coded solutions and evaluate all of them. Hence, the efficiency of meta heuristic algorithms strongly depends on the time complexity of decoding algorithms.
Genetic algorithms are used in [7-10]. But these algorithms do not always give a satisfactory result in a limited time. Therefore, the task of this work is to develop a method of automatic design of rational schemes of cutting materials by any configuration of the outer contour for flat geometric objects with a complex configuration of outer contours. But the problem of automated design of rational schemes of cutting rectangular materials into flat geometric objects was not considered in such a statement. The technological formulation of this problem is as follows: on a roll of material of limited length to place a given set of flat geometric objects taking into account technological requirements (orientation of these objects, minimum technological distance Δ between two neigh boring objects in the cutting scheme), so that waste was the smallest.
The mathematical formulation of this problem is as follows: for a given set of flat geometric objects Si and a given number of these objects Ňi, where i = 1..q, from the set of admissible layouts in a rectangular region of length DlMat and width ShMat find such a rational layout, which provided the maximum value of the goal function: q S i N ij
i F = max{F j } , where F j = and j = 1,2...
DlMat j ShMat DlMat j − the length of the rectangular area occupied by j rational layout.
This takes into account the technological requirements (orientation of these objects, the minimum technological distance Δ between two neigh boring objects in a rational layout).
Based on the practice of cutting in light industry, consider such a simplified mathematical model of the problem. Consider three consecutive tasks:
Task A – System placement N ij ( N ij Ňi) of flat geometric objects Si, i = 1..q in a rectangular region of fixed width ShMat (Section);
Task B - Designing a cutting scheme from sections (Scheme);
Task C - Interactive adjustment of the scheme of the designed cutting scheme (Interactive adjustment).
We give a mathematical formulation of each of these three problems.
Task A - Section. For Nij ( N ij Ňi) flat geometric objects from the set of sysL* = L( * ) = min(L( )) .
Task C - Interactive adjustment. In many cases, it is not possible to automatically build cutting schemes that would meet the technological requirements. Therefore it is necessary to adjust the received schemes or to build new in an interactive mode. To successfully solve this problem, you need to solve two problems: the placement of flat geometric objects in a rectangular area of given size with control:
- belonging of a flat geometric object to a rectangular area of specified dimensions;
- not the intersection of the active flat geometric object with already placed in the rectangular area of flat geometric objects; remove any previously placed flat geometric object from the cutting scheme.
Since flat geometric objects in most cases have a complex configuration of the outer contour, which cannot be described analytically, we will approximate it. For the approximation, we choose the piecewise-linear method of approximation as one that does not impose restrictions on the outer contour of a flat geometric object. In a piecewise linear approximation, the outer contour of a flat geometric object will be approximated by a polygon with vertex coordinates. Therefore, in what follows we will assume that flat geometric objects are polygons with a known number of vertices and their coordinates.
Determine the maximum values of the coordinates of the vertices of the approximate polygon for a flat geometric object:
MaxXi = maxX ij
After listing the coordinates of the approximating polygons we obtain the following expressions for:
MaxXi = −MinXi = MX i = (MaxXi + MinXi ) / 2
MaxYi = −MinYi = MYi (MaxYi + MinYi ) / 2 List the coordinates of the approximating polygons as follows:
MMianxXYii == mmianxXYjiij, j = 1..ki MinYi = minYji
.
X ij = X ij − (MaxXi + MinXi ) / 2 Y ji = Y ji − (MaxYi + MinYi ) / 2 , j = 1..ki
After recalculating the coordinates of the vertices of the approximating polygons for flat geometric objects Si, i = 1..q the coordinates of the vertices of the approximating polygon will be determined relative to the centre of the rectangles described around the flat geometric objects Si. These points are called the poles of flat geometric objects Si.
To generate a set of system schemes of cutting for a flat geometric object, it is necessary to generate a set of lattice dense stacks, as a set of prototypes of cutting schemes. 3.1
int Si int S j = 0 A system of flat geometric objects Si, i=1,2..p forms a stack on the plane, if for each pair of these flat geometric objects the condition of their mutual intersection is fulfilled. This condition can be represented as follows:
Si S j 0
, where int Si = Si − Si Snm , n,m and Si − the boundary of a flat geometric object Si .
We denote by S + a a flat geometric object that arises when each point of a flat geometric object is moved to a vector, and we will call this flat geometric object S a translation of a flat geometric object a .
Set of vectors
r = na1 + ma2 , n, m = 0,1,2,, (
is called a lattice with basis a1 , a2 , where a1 , a2 − linearly independent vectors, and is denoted = (a1 , a2 ) .
Consider a system of flat geometric objects
n, m = 0,1,2,,
(
into lattice vectors = (a1 , a2 ) .
If the system (
In the future, only those flat geometric objects that can be translated into each
other by translation to some vector will be considered the same. From this point of
view, the basic flat geometric object S (0) and the same flat geometric object S ( ) ,
= S + na1 + ma2 of a flat geometric object S
but rotated by 180o are further considered as different. Let's make from these figures
dense single-row placements:
(S (0) + na), (S ( ) + na), n = 0,1,2, , . (
By alternating the formed rows and pressing them tightly, we create a laying W on the plane so that the mutual arrangement of the row consisting of flat geometric objects S (0) , in relation to the adjacent rows of flat geometric objects S ( ) , in the whole laying was the same (Fig. 1). .
Laying W is a combination of two lattice layouts made on lattices = (a, b ) with the
S (0) + na + mb and n,m S ( ) + na + mb , where n, m = 0,1,2, n,m
same basis a, b . Therefore, the layout W of the form is called double lattice laying of flat geometric objects S (0) and S ( ) .
A system consisting of two simultaneously defined on the plane identical but not coinciding lattices with nodes points Qj, j = 1,2..m and Pi, i = 1,2..n one of which is a translation of the second to some vector, is called double lattice and is denoted W = W (a, b , q) . Here is the basis of each of the lattices of the system and the vec tor of their mutual displacement. (Q1Q2 = =P2P3, Q1Q5 = P2P5 and q = Q6P4 (Fig. 1).
The problem of generating a set of dense tabs is considered in detail in [11]. To reproduce dense lattice laying = (a, b ) on a single lattice it is necessary to determine two lattice vectors a, b . To reproduce dense lattice laying on a double lattice W = W (a, b , q) it is necessary to determine two lattice vectors a, b and the lattice shift vector q. 3.2
The source information for generating the set of allowable sections for a flat geometric object S i will be the set of allowable dense stacks built on single
p = (a p ,bp ), p = 1,2... p0 and double lattices Wr = W (ar , br , qr ), r = 1,2...r0 .
To successfully solve the problem Section it is necessary to describe its structural components, namely: - analytical description of the rectangular area і and the size ShMat x Dl_Si, in which it is necessary to tightly place flat geometric objects S i ; - determination of parameters that unambiguously determine the position of a flat geometric object S i in a rectangular region і and given dimensions; - conditions under which a flat geometric object S i is in the middle of the rectangular region і ; - mathematical description of the set of admissible solutions; - goal function.
We will connect the coordinate system with a material that has a rectangular
shape (rolls or sheets). Let the origin be in the lower left corner of the material. Then
the allowable area (Fig. 2), where flat geometric objects can be placed can be
represented as a system of inequalities:
0 X Dl _ Si , (
To unambiguously display a flat geometric object on the material, you need to know the following information:
i is the code of the flat geometric object S i that is placed (in our case 1,2..q); i = Хрm, Ypm, m = 1,2..t - coordinates of the pole of a flat geometric object S i relative to the coordinate system associated with the rectangular region і, on which is located
Pr - a sign of the position of the part (in our case: 0 - the main position; 1 - a flat geometric object rotated 180o relative to the main position)
We find the conditions under which a flat geometric object S i is inside the
rectangular region і. Obviously, if the pole of a flat geometric object S i inside the
rectangle ABCD, then this flat geometric object will be inside the rectangular region
і (Fig. 2) Then it is obvious that if the inequality holds
MX i Xpm Dl _ Si − MX i ,
MYi Ypm Sh − MYi
(
For any lattice W = W (a, b, q) , the values of the functionals
N (
the goal function can be written as: N (a, b , q) = N (
N (
Often the cutting scheme consists of separate schemes, which we will call sections. These sections are combined as rectangles described around them when constructing the cutting scheme. And this is not always rational, as in this case the sections are not aligned tightly everywhere (Fig. 3).
Let the length of the j-th section be equal to Dl_Sj and the coordinates of the poles of the parts be where k = 1,2..nj. To tightly align the j-th and i-th sections, it is necessary to find new coordinates Xp ki , where k = 1,2..ni. Their initial value can be defined as Xp ki = Xp ki + Dl _ s j , that is for alignment without taking into account the possibility of tight alignment of sections. For tight alignment of sections it is necessary to find the right boundary of the j-th section and the left boundary of the i-th section after the previous alignment. By the right boundary of a flat geometric object, t = 1,2… tR we mean the contours of this object, which are to the right of the reference line drawn from the right edge of the j-th section at a distance Dl_dj / 2 parallel to the axis 0Y , where Dl_dj is the length of the rectangle, which is described around a flat geometric object Sj (Fig. 3).
The sides of the rectangle are parallel to the sides of the j-th layout. By the left boundary G L
it , t=1,2…tL of the flat geometric object, t = 1,2… tL, we mean the contour of the flat geometric object which is to the left of the reference line, drawn from the left edge of the i-th section at a distance Dl_di / 2 parallel to the axis 0Y, where Dl_di is the length of the rectangle , which is described around a flat geometric object Si (Fig. 3). The sides of the rectangle are parallel to the sides i-th layout. The right boundary of the j-th section consists of the right boundaries G Rjt , t=1,2…tR t = 1,2… tR of flat geometric objects, for which the inequality holds Xpkj Dl _ s j − Dl _ d j , where Dl _ s j is the length of the j-th section (Fig. 3). The left boundary of the i-th layout consists of the left boundaries G L it , t = 1,2… tL of flat geometric objects, ,for which the inequality holds Xp ki Dl _ d i (Fig. 3). To closely match the j-th and i-th layouts, it is necessary to tightly align the right boundary of the j-th section and the left boundary of the i-th section (Fig. 4).
To do this first we select the left boundary G L it , t = 1,2… tL for each flat geometric object Si of the i-th section, the poles of which satisfy the condition Xp ki Dl _ di and the right boundary G Rjt , t = 1,2… tR for each flat geometric object Sj j-th sections whose poles satisfy the condition Xpkj Dl _ s j − Dl _ d j . Then the left boundary GiL for the i-th section can be represented as the union of tL the left boundaries of flat geometric objects Si, that is GiL = GiLt . Similarly, the right boundary G Rj for the j-th section can be represented as the union of the right tR boundaries of flat geometric objects Sj, that is G Rj = G r . For each left boundary it t=1 GiL we find points for which the X coordinate reaches a local minimum. Let it be an array of points Ak (Xak, Yak), k = 1,2..ki (Fig. 4). For each right boundary G Rj we find points for which the X coordinate reaches a local maximum. Let it be an array of points Bk (Xbk, Ybk), k = 1,2..kj. Draw from each point Ak (Bk) a straight line parallel to the axis OX to the intersection with the left boundary GiL (right boundary G R
j ) i-th (j-th) section (Fig. 3-5). Find the length of the segments AkOk = δk1, k = 1,2..kj (BkOk = δk2, k = 1,2..ki).
We will find ji = min( 1 , 2 ), where 1 = min( k1 ) , 2 = min( k2 ) . The k =1,2..k j k =1,2..ki found value of δji will be the value by which you want to shift the i-th layout so that it fits snugly with the j-th layout (Fig. 5). Then the coordinates of the poles of the parts in the i-th section after close alignment with the j-th section will take the following form:
XpkHobi = Xp ki + Dl _ s j − ji and YpkHobi = Ypki , where k = 1,2, .. hi.
Now we can always closely match the two layouts (sections) Ŝi and Ŝj by calculating δіj, but we must remember that δіj determines the tight fit when Ŝi the layout is on the left and Ŝj the layout is on the right, δji determines the tight fit when Ŝj layout is on the left, and Ŝi layout is on the right, as δіj ≠ δjі. 4.2
The mathematical model of this problem can be represented as follows. You need to minimize the function:
q q q
L = Dl _ si − ij xij
i=1 i=1 j=1
(
.
q q q q q Lk = Dl _ si − ij xij = Lo − ij xij = i=1 i=1 j=1 i=1 j=1
q q L q q = ( o − ij ) xij ) = ij xij i=1 j=1 q i=1 j=1 ij =
L q0 − ij .
Then where lows:
After that, the mathematical model of the problem can be represented as fol(12) (13) (14) (10) (11) q q
L*k = min (Lk ) = i=1 j=1 ij xij with the following restrictions: q xij = 1 i=1 q xij = 1 j=1 0 xij = 1 This is a mathematical model of the problem of the salesman. 5
In many cases, it is not possible to automatically build cutting schemes that would meet the technological requirements. Therefore it is necessary to adjust the received schemes or to build new in an interactive mode. To successfully solve this problem, you need to solve the following problems: • placement of parts on the material of the specified dimensions and not crossing the boundaries of the material details; • removal of any previously placed part from the cutting scheme; • not the intersection of parts when placing them.
Let's dwell in more detail on each of the above tasks. The problem of placing parts on the material of a given size and not crossing the boundaries of the material details was discussed in detail in the first section.
To remove any previously placed part from the cutting scheme, it is necessary to identify the part that needs to be removed. To do this, you must decide whether the point is inside a convex-concave polygon. To speed up the algorithm for determining the mutual location of the point O(X0, Y0) and the polygon A, consider the problem of mutual placement of the point O(X0, Y0) and the rectangle described around the polygon P. Let this rectangle be defined by a system of inequalities: X ma in x X ma ax Ymain y Ymaax (15) Then the point O(X0, Y0) is located outside the polygon A, if it does not satisfy the system of inequalities (15), otherwise the point O may or may not belong to the polygon A(рис. 5). To clarify this fact, we use the method of angles[12].
Consider the method of angles [12] to solve the problem of belonging to a point. In this approach, it is necessary to define the concept of an angle with a sign. Suppose we have a vector OAi and a vector OAi+1 . Denote the angle between them by і=АіОАі+1, where і=1,2...np-1. The angle і will be with a plus sign, when rotating the vector OAi around the point O the closest path to the vector OAi+1 will be when rotating the vector OAi counterclockwise, otherwise this angle і will be negative. The np −1 point O will be outside the polygon A, if i = 0o (fig. 5.a). The point O is inside the polygon A, if np −1 i = 360o (fig. 5.b). i=1
Fig. 5. Location of the point a) outside the polygon b) in the polygon
To determine the total angle, it is necessary to find the elementary angles. Elementary angles will have a sign. To determine the sign of the elementary angle i use the module of the vector product:
Determine the angle between the vectors OAi and OAi+1. To do this, we find the modulus of the vector product and the scalar product of the vectors OAi and OAi+1.. We introduce the notation: ai= OAi=(Xai, Yai)=(Xi-X0, Yi-Y0); bi= OAi+1 =(Xai+1, Yai+1)=(Xi+1-X0, Yi+1-Y0); Then [OAі x OAі +1]= [aix bi] =
Xai Xbi
Yai = Xai Ybi − Xbi Yai =
Ybi =ai۰bi۰sin i, (OAі+1۰ OAі+1)=(ai۰ bi)=Xai۰Xbi+ Yai۰Ybi = ai۰bi۰cos i.
From here:: sin i = (Xai۰Ybi- Yai۰Хbi)/( ai۰bi),
cos i=(Xai۰Xbi- Yai۰Ybi)/( ai۰bi), where ai= ( X i − Xo)2 + (Yi − Yo)2 and bi = ( X i+1 − Xo) 2 + (Yi+1 − Yo) 2 .
If [OAi x OAi+1] = [aix bi]>0, then the angle will be positive.
If [OAi x OAi+1] = [aix bi]<0 , then the angle will be negative.
Then: if cos i>0, then j=arctg( [ai x bi]/(ai۰ bi); if cos i=0 та sin i=1, then i=/2; if cos i=0 та sin i=-1, then i=-/2; if cos i<0 та sin i≥0, then i=+ arctg( [ai x bi]/(ai۰ bi); if cos i<0 та sin i<0, then i=-- arctg( [ai x bi]/ (ai۰ bi)).
Fig. 6. An example of the designed rational scheme of cutting To find out the intersection of two plane geometric objects, it is necessary to find out the intersection of the polygons P and Q, which approximate these objects.
The above-mentioned problems A-С were implemented in software for automated design of rational schemes of cutting rectangular materials into flat geometric objects of arbitrary shape of the outer contour, taking into account the need for these objects. An example of the designed rational scheme of cutting by means of the developed software is presented in fig. 6. 6
The article considers the task of computer-aided design of rational schemes for
cutting rectangular materials onto flat geometric objects with a complex configuration of
the external contour. For its successful solution, the task was divided into three
consecutive tasks: task A – Section; task B – Scheme; task C - Interactive adjustment.
For their tasks, methods and algorithms for solving them were proposed. The
proposed mathematical models and algorithms allowed to develop software for
automated design of rational schemes of cutting rectangular materials into flat geometric
objects with a complex configuration of the outer contour. This software can be used
in various fields, where it is necessary to rationally cut rectangular materials into flat
geometric objects and will increase the efficiency of materials in cutting.
10. Zhang, D., Chen, , C., Lin, Y.: An improved heuristic recursine strategy based on genetic
algoritm for the strip rectangular packing problem. Acta Automatica Sinica. 33(