=Paper= {{Paper |id=Vol-2667/paper21 |storemode=property |title=Modified genetic algorithm as a new approach for solving the problem of 3d packaging |pdfUrl=https://ceur-ws.org/Vol-2667/paper21.pdf |volume=Vol-2667 |authors=Vladimir Mokshin,Darya Maryashina,Nikita Stadnik,Alexander Zolotukhin,Leonid Sharnin }} ==Modified genetic algorithm as a new approach for solving the problem of 3d packaging == https://ceur-ws.org/Vol-2667/paper21.pdf

Modified genetic algorithm as a new approach for
solving the problem of 3d packaging
Vladimir Mokshin Darya Maryashina Nikita Stadnik
Kazan National Research Technical Kazan National Research Technical Kazan National Research Technical
University named after A. N. Tupolev - University named after A. N. Tupolev - University named after A. N. Tupolev -
KAI KAI KAI
Kazan, Russia Kazan, Russia Kazan, Russia
vladimir.mokshin@gmail.com maryashina.darya@yandex.ru erter.live@gmail.com

Alexander Zolotukhin Leonid Sharnin
Kazan National Research Technical Kazan National Research Technical
University named after A. N. Tupolev - University named after A. N. Tupolev -
KAI KAI
Kazan, Russia Kazan, Russia
avol116@yandex.ru sharnin_lm@mail.ru

Abstract—In this paper, we proposed one of the options for II. EVOLUTIONARY ALGORITHMS
developing a new evolutionary heuristic approach for solving
the three-dimensional packing problem called BPP (Bin A. Ant algorithm
packing problem), as applied to the variation of this problem Ant Algorithm (ACO) is one of the effective bionic
with a single container and a set of boxes of various methods and packaging algorithms. ACO is based on the
dimensions, called the SKP (Single knapsack problem), and the principle of a multi-agent method of intellectual optimization
comparison of 11 basic evolutionary heuristic approaches to
based on modeling the behavior of an ant colony. Each ant
solving the problem of three-dimensional packing of BPP (Bin
packing problem) variations SKP (Single knapsack problem)
individually represents a low-level unit, however, in general,
with the developed new evolutionary heuristic approach to an ant colony is a rational multi-agent system. An ant acts as
solving BPP using modi cited genetic algorithm (MGA). By an agent, looking for an optimal path between its ant hill and
performing correlation and statistical analysis using 10 a food source. The following terms apply to ACO when
randomly created sets of input data for solving BPP, the solving sequential packaging tasks: ACO nodes are the
effectiveness of MGAs was proved in comparison with 11 basic points of space inside the container, and the paths along
evolutionary algorithms for solving BPP. Thus, it was which ants move are the trajectories of the boxes inside the
confirmed that MGA and similar algorithms can be effectively container to the places of their final packaging (nodes). Each
used to solve such logistic NP-difficult problems. ant begins its path from the zero node (ant nest, which is
located in the lower left far corner of the container). If the ant
Keywords—modelling, genetic algorithm, 3d packing cannot pack the boxes in the current node, then it goes to the
next node other than zero. The ants move around the nodes
I. INTRODUCTION until all the boxes are packed in a container with the
In tough competitive market relations, each company maximum possible filling of each node [1].
seeks to reduce the cost of its products without
compromising on quality. One of the factors affecting the B. Annealing simulation algorithm
cost of a product is packaging and distribution. In modern The annealing simulation algorithm (SA) is associated
freight transportation, the packaging problem is an important with the methods of simulation modelling (SM) in statistical
applied section of transport logistics and allows you to solve physics. The algorithm is based on the process of metal
many practical problems in the management, automation and annealing in metallurgy, which consists in slow cooling of
optimization of cargo transportation. the material to increase its strength and reduce defects. The
annealing process in metalworking can be described as
The three-dimensional packing problem is a well-known follows: the temperature of the metal increases until it begins
NP-hard problem, both exact and evolutionary approaches to melt in the heat bath, i.e. until the end of the process of
are used to solve various variations of it. The most popular complete transition of the metal into a liquid state of
variations of the packing problem are RBPP (Residual bin aggregation. After this, the metal in a liquid state is slowly
packing problem), when it is required to pack different box cooled, i.e. its temperature is gradually and carefully reduced
sizes in different containers, and SKP (Single knapsack until the particles return to their original state of aggregation.
problem), when it is required to pack different types of boxes As applied to the problems of three-dimensional packing, the
in one container. This article describes an algorithm for main purpose of applying the annealing simulation algorithm
solving the problem of three-dimensional packing of the SKP is to minimize the free space of the container (i.e., to find the
variation (Single knapsack problem) from one container and best way to pack the boxes into the container). The objective
N boxes. function of the algorithm can be described as follows:
Today, there are a number of evolutionary algorithms (V to ta l  V u s e fu l )  m in , where V to ta l is the total volume
based on the mechanism of biological evolution and used to
solve packaging problems. Let's consider each algorithm of the container; V u s e fu l is the useful volume occupied by the
separately. boxes, i.e. the volume of the figure, consisting of the closest
points of the boxes to coordinate zero and the farthest points
of the boxes from coordinate zero [2], [3].

Copyright © 2020 for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0)
Data Science

C. Tabu Search n algorithm and simple local search is the systematic change in the
Tabu Search (TS) is a mathematical optimization method appearance of the surrounding area during local search. The
that uses the local search method. Unlike the local search basic algorithm for local search with alternating
method, TS has a higher productivity. The prohibition search neighborhoods can be described as follows: for some
process is characterized by a set of states (options for three- preliminary solution to the three-dimensional packing
dimensional packing of boxes in a container), and at each problem (the supposedly optimal variant of packing boxes in
stage (step), a transition is made from the current state to one a container), its many neighborhoods are determined: other
of the neighboring ones. Performance improvements are slightly different options for packing boxes in a container.
achieved through the use of prohibition lists. Once a Then, from this set of neighborhoods, another type of
potential solution (the most optimal option from previously neighborhood is randomly selected. The search for an
found options for three-dimensional packaging of boxes in a improved solution for the selected neighborhood is carried
container) has been found, it is placed in the prohibition list, out using the local search algorithm. At the next stage, the
that is, marked as “taboo”, which reduces the search time due algorithm branches: if an improved solution is found, then
to the ban on “visiting” earlier discovered solutions. After the preliminary solution is replaced by the value of the new
this operation, the local search process continues until a new solution, the search continues in the same neighborhood.
improved solution is found [4]. Otherwise, a new neighborhood is selected from the set of
neighborhoods of the preliminary solution, and the algorithm
D. Guided Local Search continues to run. The stopping criterion for the VNS
Guided Local Search (GLS) is one of the different types algorithm can be the number of iterations in which no
of searches with bans. The basis of GLS is metaheuristics, improvement of the solution was achieved, a certain number
which, like TS, uses memory (a list of previously obtained of iterations, or the fact that the optimal solution was found
solutions) to control the search process. The managed local [6], [7].
search algorithm is a local search option in which G. Greedy randomized adaptive search procedure
components are searched, often leading to a local minimum
of the objective function. As applied to the packing problem, The greedy algorithm with random adaptive search
the objective function of the algorithm can be written as (GRAPS) improves combinatorial solutions obtained by
constructing individual components. The GRAPS algorithm
follows: f( x )  (V to ta l  V u s e fu l ) , where V to ta l is the total can be described in three steps. At the first step, the
volume of the container; V u s e fu l is the useful volume maximum space for filling is selected, i.e. the total volume of
the container. The corners of the container are filled first,
occupied by the boxes, i.e. volume of the figure consisting of then the sides, and at the very end the interior space is filled.
the closest points of the boxes to coordinate zero and the At the second step, from a set of boxes in a lexicographic
farthest points of the boxes from coordinate zero. Then, order, boxes for packaging are selected. The choice is made
solutions using these components are fined, thereby taking into account two criteria: those that fit in the
enhancing the research of the search space, leading to maximum space in the best way and which give the greatest
solutions leading to a global minimum of the objective increase in the total volume of boxes. In the third step, the
function [5]. list of maximum spaces is updated, since any packaging
E. Fast Local Search made of at least one box leads to changes in the maximum
space. The change in the value of the current maximum
Fast Local Search (FLS) is an improved version of
managed local search. Unlike GLS, a Fast Local Search space is calculated by the formula: V m a x  V to ta l  V u s e fu l ,
breaks the container's fillable area into several smaller where V m a x is the current maximum space, V to ta l is the total
subdomains. Each such formed subdomain can be in one of
two states: active or inactive. By default, all subregions are volume of the container, V u s e fu l the useful volume occupied
in an active state. According to a certain order (dynamic or by the boxes, i.e. volume of the figure consisting of the
statistical), the quick local search algorithm visits active closest points of the boxes to coordinate zero and the farthest
regions of the container with the goal of packing boxes into points of the boxes from coordinate zero. After that, the
them. Next, the subdomain is checked for subneighborhood: algorithm cycle returns to the first step and continues the
if there is no better option for the algorithm to move (packing process of packing boxes until all boxes are packed into a
boxes into neighboring subdomains), then the current container [8].
subdomain is filled with boxes and becomes inactive,
otherwise an improving move is performed - visiting another H. Best Fit Decreasing (BFD) and First Fit Decreasing
region. One of the advantages of FLS is the ability to (FFD)
reactivate subdomains. If we assume that a number of The Best Matching Descending (BFD) and First
subregions previously converted to inactive status may Matching Descending (FFD) algorithms are the simplest
contain improving moves, taking into account the just polynomial algorithms used to solve packing problems. Both
completed move, then such subregions can be reactivated - algorithms sort objects by not increasing their volumes and
become active again. When all areas become inactive, the sequentially put them in containers. BFD and FFD differ
best solution to the three-dimensional packing problem will from each other in the way they select the container into
be found, i.e. the FLS algorithm will come to its global which the boxes will be packed. According to the best
minimum [5]. descending algorithm, the boxes will be packed in the
F. Local search with alternating surroundings container that will have the smallest free space after loading.
In the algorithm of the first descending box, the boxes are
Local search with alternating neighborhoods (VNS) is loaded into the first container into which they fit in volume
one of the methods for solving discrete optimization [9].
problems. One of the differences between the VNS method

VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 92
Data Science

I. Particle Swarm Optimization (PSO)
 xi j  W 
The Particle Swarm Optimization Method (PSO) is based    j  0, 7
on modeling the behavior of a flock of birds. The idea of Blocks cannot go beyond:  y ij  D  ,
PSO is that each particle is a possible solution to the z  H 
optimization problem, as applied to the three-dimensional  ij 
packing problem, a possible optimal option for packing  i  1, N .
boxes in a container. Particles “fly” over the solution space
of the function and try to find its global minimum (the best The total volume of blocks may not exceed the volume of
solution to the packaging problem), taking into account their N

own knowledge and the experience of their neighbors. The the container:  V i  W  D  H , where V i is the volume of
principle of “flight” of particles is based on the gradient i 1

descent method, the method of finding a local minimum by the i-th block.
moving the particle along the gradient, and the space of Blocks cannot overlap each other:
vectors indicating the path to the greatest decrease in the
objective function [10].  x ij  x i ( j + k )  x ( i+ 1 ) j 
 
III. ADAPTIVE GENETIC ALGORITHM (GA)  y ij  y i ( j + k )  y ( i+ 1 ) j   j , k  0 , 7 ,  i  1, N ,  k  j .
The genetic algorithm is based on modelling the  z  z  z ( i+ 1 ) j 
 ij i ( j+ k ) 
mechanisms of natural selection in nature. Its main operators
are evolutionary methods such as inheritance, mutation, The collisions of blocks will be determined in accordance
crossingover, and selection. At the initial stage of the with the model’s limitations by checking the condition of
algorithm, an initial population of X chromosomes overlapping blocks on each other by comparing the
(individuals) H is formed, consisting of a set of p genes. coordinates of the farthest corner of an already placed block
Then, two chromosomes Hn and Hn are randomly selected and the nearest corner of the placed (new block). As an
from the original population and two new chromosomes optimization target (objective function), we will use the ratio
Hn
new
and H k
new
are created by crossing (mutually of the usable volume to the volume of the container, which
V u s e fu l
exchanging chromosome regions) chromosomes Hn and Hn. we denote by F   1.
new
At the next step of the algorithm, mutations of the H n and V box

chromosome genes with a random probability 𝜌 Its significance will seek unity with the disappearance of
new
Hk
voids. The modified genetic algorithm (MGA) is based on
occur. Upon completion of the mutation process, the the principles of the genetic algorithm, however, it has
new new
chromosomes H n and H k become a new part of the X modified behavior patterns such as adaptive mutation and the
population. After N steps of this algorithm, the best LBFL model for generating the initial chromosome
chromosomes that have the set of genes describing the population.
optimal solution necessary for solving the optimization The LBFL model (Late-Botton-Front-Left, Late-Lower-
problem are selected from the population X extended by the Front-Left) is an imperfect algorithm for arranging (sorting)
methods of inheritance, mutation, and crossing over. The blocks according to 4 priority levels: unloading time (late-
main problem of packaging problems is their complexity and early), height (lower-upper), depth (front-back), width (left-
the impossibility of solving such problems using right) [11].
deterministic polynomial algorithms due to the large time
and computational costs, therefore, the search and This algorithm generates the order of packing blocks into
development of new methods and algorithms for solving a container according to the priority list. The latest block at
packaging problems do not lose their importance and the time of unloading is always placed at the origin. All
relevance. The article discusses the use of a new modified subsequent blocks, sorted by the time of unloading, are
genetic algorithm, the practical significance of which is sequentially moved to the upper rear right corner, and then
shown by solving the problem of packing rectangular boxes with the help of movement and rotation in 6 variants fill the
in a container with maximum compactness, taking into entire lower level, then the front, then the left [13]. Filling
account the priority of unloading at delivery points. As a these levels as evenly as possible, the blocks fill the
container, we consider a part of three-dimensional space remaining container volume in the same way as a separate
limited by a width W, a depth D, and a height H having a empty container, limited by the maximum width, depth and
volume M. As boxes, we consider N blocks limited by our height available for it, continuing the algorithm of the LBFL
own parameters for the width, depth, and height that must be model. This will continue until all the blocks are laid in a
placed in the volume M. We describe the location of the container and the objective function is maximized. Fig. 1
container in space using eight points shows the result of the generation of the initial chromosome
population using the LBFL model of the arrangement of
 X 0 , Y 0 , Z 0 , ..., X 7 , Y 7 , Z 7  , where X 0 , Y 0 , Z 0 are equal blocks according to the priority list in three-dimensional
to zero, and X 7 , Y 7 , Z 7 are respectively equal to W, D, N. space of width W, depth D and height H.
The arrangement of blocks inside the container is also we As an algorithm for mutating chromosomes, the adaptive
describe eight points  x 0 , y 0 , z 0 , ..., x 7 , y 7 , z 7  according probability of mutation was used. This allowed us to
overcome the high probability of population convergence at
to three conditions: a local optimum.

VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 93
Data Science

Fig. 1. The result of the algorithm of the LBFL model. Fig. 2. The dependence of the adaptive probability of a mutation on the
time of the algorithm.
When using it, the degree of mutation for each individual
varied depending on the average indicator of the objective At the initial stage, the generation of individuals of the
V u s e fu l population occurs (the creation of many blocks, the sizes of
function F  obtained from each of the crossing which are randomly selected from ranges that satisfy the
V box given conditions).
chromosomes.
The next step is the formation of chromosomes - various
The closer this indicator was to the global optimum (the sequences of arrangement of blocks. The number of
best solution to the three-dimensional packing problem, at chromosomes is selected in the range from 2 to 2 ∙ N, where
which F  1 ), the less the mutation probability. And, on the N is the number of blocks.
contrary, the farther the indicator was, the more likely the
chromosome mutation was. Next, the main process of the modified genetic algorithm
V u s e fu l
In mathematical form, the adaptive probability of begins - the calculation of the objective function F 
V box
mutations of the chromosomes x 1k and x 2k of the k-th
for each chromosome, where Vuseful is the net volume
population can be expressed through the eq. (1): occupied by the blocks, i.e. the volume of the figure,
k 1
F ( x1 )  F( x2
k 1
) consisting of the closest points of the blocks to coordinate
 1 zero and the farthest points of the blocks from coordinate
  2  zero, and Vbox is the volume of the container.
To test the effectiveness of this modification of the
MGA, a test of the operation of the MGA algorithm was In addition to the objective function, the density function
carried out on ten canonical independent sets of source data N

is calculated as P   i  1 b o x , where V b o x is a volume of
i
V i
consisting of 50 boxes of 5 different types. During testing,
changes in the adaptive probability of a mutation were V u s e fu ll
evaluated. In Fig. 2. The test results are presented in the form the i-th block, Vuseful is an occupied space after decoding
of a graph of the dependence of the mutation probability on (usable volume). The density function describes the ratio of
the time of the algorithm operation. the total volume of all blocks to the usable volume and tends
to 1 with a decrease in the gaps between the blocks. The next
As applied to the packaging problem, MGA is a step after completing the first cycle of the main GA process
collection of H chromosomes (individuals) consisting of p is the selection of chromosomes (selection of chromosomes
genes. Where each chromosome Hi is an imperfect algorithm with the best values of the objective function from the total
of the i-th arrangement of blocks (boxes), and the pj gene number of chromosomes in the population). In this work, we
are parameters (a tuple of coordinates of all eight points) of used the selection method based on the tournament table: the
the j-th block [11]. The course of the algorithm is a sequence total number of chromosomes is divided into subgroups with
of operations (mutations) over a set of chromosomes, the number of individuals from 2 to 4, and then a
oriented towards achieving the maximum indicator of the chromosome with the best objective function is selected from
optimization function (in relation to the task of three- each subgroup. This method allows you to create a new and
dimensional packaging - achieving the maximum indicator objectively better population for the next cycle of the main
of the objective function of the ratio of usable volume to the GA process.
V u s e fu l
volume of the container F   1 at least one of the After chromosome selection, their crossing follows - the
V box
process of creating two new descendant chromosomes by
chromosomes. combining parts of the parent chromosome genes. For this, a
For a more detailed consideration of the algorithm, it can random gene is selected in the gene chain of each of their
be structurally divided into six stages: generation of parent chromosomes 𝑝𝑟 , first descendant chromosome 𝐻𝑖1 is
individuals, formation of chromosomes, calculation of the made up of genes 𝑝𝑘 ∀𝑘 = ̅̅̅̅1, 𝑟 of the first parent and genes
objective function, selection of chromosomes, crossing and 𝑝𝑚 ∀𝑚 = ̅̅̅̅𝑟, 𝑗 of the second parent, second chromosome
detection of mutations. descendant 𝐻𝑖2 made up of genes 𝑝𝑘 ∀𝑘 = ̅̅̅̅ 𝑟, 𝑗 of first parent
genes and genes 𝑝𝑚 ∀𝑚 = ̅̅̅̅ 1, 𝑟 of the second parent, where j
is a total number of genes in parent chromosomes (number of
blocks).

VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 94
Data Science

The next step after crossing is to add mutations - rare
changes in the gene values at random with an adaptive
probability value 𝜌. The probability 𝜌𝑖𝑗 of the mutation of the
gene 𝜌𝑗 of the chromosome 𝐻𝑖 depends on the fitness of the
individual (chromosome 𝐻𝑖 ), expressed by the value of the
V u s e fu l
objective function F  for this chromosome. The
V box
worse the individual is adapted, i.e. the further the value of
the objective function is from unity, the higher the
probability of mutation of its genes becomes, so that it can
optimize the current value of the objective function. In the
packaging problem under consideration, the adaptive
mutation of the 𝑝𝑗 gene is to move the j-th block to the
beginning of the priority list, regardless of its size and initial Fig. 3. Algorithm runtime evaluation results.
priority of unloading.
For an objective assessment of three-dimensional
IV. COMPARISON OF METHODS packaging methods, it was proposed to introduce a new
A comparison of methods for solving the three- variable (2):
dimensional packing problem showed the following results. i
  0 .0 1  
n

The BFD algorithm proved to be the most resource-intensive   
i0 i
algorithm, having slightly lost in performance to the FFD
algorithm. These algorithms are the simplest heuristic where  i packing time of the i-th set, 𝜌𝑖 is the density of the
approaches to solving the problem of three-dimensional obtained packaging of the i-th set, and n is the number of sets
packaging, therefore, are at the end of the performance list. in the experiment, which mathematically illustrates the
The annealing simulation algorithm (SA) showed the most degree of effectiveness of the three-dimensional packing
expression regarding the FFD algorithm, however, it lost in method (the lower its value, the higher the efficiency of the
performance to the following search algorithms: VNS, TS, algorithm).
GLS, FLS, whose indicators are also sorted in order of Comparison of three-dimensional packaging methods
improving performance, however, they differ slightly from was carried out according to three objective performance
each other. Search algorithms can quickly converge to a local indicators: the total preparation time, average packing
minimum in the neighborhood of solutions, choosing both density and the value of the variable  . The results of the
from the full version (TS, GLS), and segmented (VNS, FLS).
The performance of FLS bypassed the ant colony comparison of three-dimensional packaging methods are
optimization (ACO), which works on the principle of an ant presented in table 1.
colony, with a large gap, followed by the PSO, which
describes the simulation of the life of a "swarm of particles",
in its behavior similar to a bee swarm. GA, GRASP (a
greedy algorithm with random adaptive search, which allows
to find a multitude of local minima of the objective function
and based on them to suggest the optimal solution) and MGA
(a modified genetic algorithm that allowed to increase the
speed of the standard genetic algorithm and get around in
GRASP performance).
To numerically evaluate the effectiveness of the
packaging methods, special test data sets have been
developed depending on the type of problem being solved. In
this work, ten canonical sets were used, consisting of 1000
boxes of 50 types and a single container of constant sizes, Fig. 4. The results of the assessment of the density of the resulting
but different among the examples. Two performance packaging.
indicators were evaluated: the running time of the algorithm
TABLE I. 3D COMPARISON RESULTS
and the density of the resulting packaging in decimal units. Method Total packing Average Value φ
In Fig. 3-4 are comparative graphs of the results of the time (minute) packing density
(%)
assessment of both performance indicators. The indicators MGA 1015 94.56 1073.3926
were evaluated as follows: each of the 12 packaging methods GRASP 1059 91.03 1163.3527
was tested on ten canonical sets independent of each other, GA 1109 92.48 1199.1782
during testing, two performance indicators were evaluated: PSO 1181 89.54 1318.9636
the time the algorithm worked in minutes and the density of ACO 1209 88.73 1362.5606
the resulting package in percent. Then, for each algorithm, FLS 1432 80.25 1784.4237
the total packing time in minutes was calculated from the GLS 1481 82.68 1791.2433
total packing time of all ten sets and the average packing TS 1587 88.31 1797.0785
VNS 1545 85.93 1797.9751
density by the average packing density among all ten sets. SA 1584 84.19 1881.4586
FFD 1650 86.17 1914.8195
BFD 1714 81.56 2101.5204

VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 95
Data Science

V. SOFTWARE IMPLEMENTATION The worst operating time of the MGA was 108 minutes with
input data of set No. 8. The worst packing density was
For the software implementation of the developed MGA, 93.87% with set 9 input.
a C # language application was written in Microsoft Visual
Studio 2017 for a user of 32-bit and 64-bit versions of To objectively prove the effectiveness of the modified
Windows XP and higher, which solves the three-dimensional genetic algorithm with respect to 11 standard evolutionary
packaging problem and graphically illustrates the final result approaches to solving the three-dimensional packaging
as a three-dimensional container model with rectangular problem, we will carry out a correlation analysis of the best
boxes located in it optimally. and worst values of the two criteria for the algorithm's
efficiency: total operating time and packing density among
In the simulated example, the task of packing 50 different 11 standard methods and MGA.
types of boxes in a 40-pound cargo container of ISO standard
was considered. Let 𝜏𝑖𝑗 is a packing time i-th set j-th method, 𝜌𝑖𝑗 is a
density of the resulting package of the i-th set by the j-th
The algorithm of modified genetic algorithm:
 ij
1. Variables Initialization: method,  ij  is the resultant performance indicator of
2. chr is a number of chromosomes (population size) maxiter  ij
is a maximum number of iterations (parameter for while
loop) the j-th method on the i-th set.
3. Begining:
Correlation analysis showed a high level of data
4. k  1
𝑘
correlation between sets, i.e. with a change in the method for
5. Creating an initial population X  k
{𝑥1𝑘 , 𝑥1𝑘 , . . . , 𝑥𝑐ℎ𝑟 } using solving the three-dimensional packing problem in the i-th set,
LBFL model
the resulting performance indicators in the remaining sets
6. The calculation of the objective function F ( x ik ) for
with a change in the method to the same will change
i  1,  , c h r proportionally. This dependence can be clearly seen in Fig.
7. Loop while(𝑥 ∗ = true): 6.
8. The cycle beginning:
9. k  k  1
chr
10. 𝐿𝑜𝑜𝑝 for(iter = 1; iter ≤ ; 𝑖𝑡𝑒𝑟 = 𝑖𝑡𝑒𝑟 + 1):
2
11. The cycle beginning
12. Random selection of two chromosomes 𝑥𝑝 and 𝑥𝑞 of 𝑋 𝑘−1
13. Two new chromosomes creation
14. 𝑥𝑝𝑛𝑒𝑤 и 𝑥𝑞𝑛𝑒𝑤 as crossingover 𝑥𝑝 и 𝑥𝑞 with probability 𝑝𝑐
15. The calculation of the adaptive probability of chromosome
mutations 𝑥𝑝𝑛𝑒𝑤 и 𝑥𝑞𝑛𝑒𝑤
𝐹(𝑥 )+𝐹(𝑥 )
16. 𝑝𝑚 = 1 − 𝑝 𝑞
2
17. Mutation operation 𝑥𝑝𝑛𝑒𝑤 and 𝑥𝑞𝑛𝑒𝑤 with probability 𝑝𝑚
18. Objective functions calculation 𝐹(𝑥𝑝𝑛𝑒𝑤 ) and 𝐹(𝑥𝑞𝑛𝑒𝑤 )
19. Adding 𝑥𝑝𝑛𝑒𝑤 and 𝑥𝑞𝑛𝑒𝑤 into 𝑋 𝑛𝑒𝑤
20. The cycle end.
21. Selecting of the best chromosomes from 𝑋 𝑘−1 and
𝑋 𝑛𝑒𝑤 for 𝑋 𝑘
22. 𝑥 ∗ = the best chromosome in 𝑋 𝑘
23. The cycle 𝑤ℎ𝑖𝑙𝑒(𝑘 ≤ 𝑚𝑎𝑥𝑖𝑡𝑒𝑟 and 𝐹(𝑥 ∗ ) < 1): Fig. 6. Dependence of the distribution of  values on the packaging
24. The cycle beginning: ij

25. Return 𝑥 ∗ method and the set of boxes.
26. End of cycle.
27. End of cycle. Thus, a change in the set practically does not affect the
The result of the MGA: a three-dimensional model of the efficiency of the method for solving the three-dimensional
best individual (the best option for packing boxes in a packing problem; therefore, the effectiveness of the method
container) is shown in Fig. 5. can be taken as an objectively independent value.
Thus, the effectiveness of the developed modified genetic
algorithm for solving the problem of three-dimensional
packing of goods in containers based on a mathematical
model constructed according to optimal conditions is proved
by a series of simulation experiments using a software
application in C #, as well as a correlation analysis of
Fig. 5. The result of MGA work of with input data from the 1st set. simulation results obtained as a result of experiments data.

As a result of the MGA’s work on the first set, 1000 VI. CONCLUSIONS
boxes of 50 types were packed into a 40-foot container, the In this paper, we proposed one of the options for
packing density was 93.96%, and the total algorithm running developing a new evolutionary heuristic approach for solving
time was 99 minutes. The best result for the packing density the three-dimensional packing problem called BPP (Bin
criterion was obtained by the MGA with input data of the 6th packing problem), as applied to the variation of this problem
set, which amounted to 95.16%. The best result for the total with a single container and a set of boxes of various
operating time criterion was obtained by the MGA with input dimensions, called the SKP (Single knapsack problem), and
data of sets No. 5 and No. 9, which amounted to 98 minutes. The comparison of 11 basic evolutionary heuristic

VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 96
Data Science

approaches to solving the problem of three-dimensional [12] V.V. Mokshin, “Parallel genetic algorithm for selecting significant
packing of BPP (Bin packing problem) variations SKP factors affecting the evolution of a complex system,” Bulletin of
Kazan State Technical University. A.N. Tupolev, vol. 3, pp. 89-93,
(Single knapsack problem) with the developed new 2009.
evolutionary heuristic approach to solving BPP using modi [13] V.V. Mokshin, I.R. Saifudinov, L.M. Sharnin, M.V. Trusfus and P.I.
cited genetic algorithm (MGA). By performing correlation Tutubalin, “Parallel genetic algorithm of feature selection for complex
and statistical analysis using 10 randomly created sets of system analysis,” Journal of Physics: Conf. Series, vol. 1096, 012089,
input data for solving BPP, the effectiveness of MGAs was 2018. DOI:10.1088/1742-6596/1096/1/012089.
proved in comparison with 11 basic evolutionary algorithms [14] P. Tutubalin, S. Novikova, A. Semenova, E. Komissarova, N.
for solving BPP. Thus, it was confirmed that MGA and Arutyunova, S. Sotnikov and A. Alexandrov, “Status of creation of
hardware-software complex of automatic control of the insulin
similar algorithms can be effectively used to solve such delivery”, J. Phys.: Conf. Ser., vol. 1368, no. 4, 042006, 2019.
logistic NP-difficult problems. The produced methodology [15] P.I. Tutubalin, V.V. Mokshin, “The Evaluation of the cryptographic
of model analysis also has interest for using in different areas strength of asymmetric encryption algorithms,” Second Russia and
[14-24]. Pacific Conference on Computer Technology and Applications
(RPC), pp. 180-183, 2017. DOI: 10.1109/RPC.2017.8168094.
REFERENCES [16] I. Yakimov, A. Kirpichnikov, V. Mokshin, Z. Yakhina, R. Gainullin,
[1] M. E. Silveira, S. M. Vieira and J.M. Da Costa Sousa, “An ACO “The comparison of structured modeling and simulation modeling of
algorithm for the 3D bin packing problem in the steel industry,” IEA/ queueing systems,” Communications in Computer and Information
AIE, LNCS, vol. 7906, pp. 535-544, 2013. Science (CCIS), vol. 800, 2017. DOI: 10.1007/978–3–319–68069–9
21.
[2] D. Mack, A. Bortfeldt, H. Gehring, “A paralled hybrid local search
algorithm for the container loading problem,” Int Trans Oper Res, vol. [17] I.M. Yakimov, M.V. Trusfus, V.V. Mokshin and A.P. Kirpichnikov,
11, no. 5, pp. 511-533, 2004. “AnyLogic, ExtendSim and Simulink Overview Comparison of
Structural and Simulation Modelling Systems,” 3rd Russian-Pacific
[3] K.K. Lai and J.W.N.Chan, “Developing a simulated annealing Conference on Computer Technology and Applications (RPC), IEEE,
algorithm for the cutting stock problem,” Computers & Industrial 2018. DOI: 10.1109/RPC.2018.8482152.
Engineering, vol. 32, no. 1, pp. 115-127, 1997.
[18] P. Tutubalin, S. Novikova, A. Semenova, E. Komissarova, N.
[4] A. Bortfeldt and H. Gehring, “Applying tabu search to container Arutyunova, S. Sotnikov and A. Alexandrov, “Status of creation of
loading problems,” Symposium on Operations Research, Jena. hardware-software complex of automatic control of the insulin
Operations Research Proceedings, vol. 1997, pp. 533-538, 1998. DOI: delivery,” Journal of Physics: Conference Series, vol. 1368, no. 4,
10.1007/978-3-642-58891-4_84. 2019.
[5] O. Faroe, D. Pisinger and M. Zachariasen, “Guided local search for [19] P. Tutubalin and V. Mokshin, “Structural and Functional Model of the
the three-dimensional bin packing problem,” Tech. Rep. 99-13, On-board Expert Control System for a Prospective Unmanned Aerial
Department of Computer Science, University of Copenhagen, 1999.
Vehicle,” Lecture Notes in Electrical Engineering, vol. 641, pp. 262-
[6] Y. Kochetov and A. Kondakov, “VNS matheuristic for a bin packing 272, 2020.
problem with color constraint,” Electron. Notes Discrete Math., vol.
[20] P.I. Tutubalin, “Application of models and methods of stochastic
58, pp. 39-46, 2017.
matrix games for ensuring information security in mobile distributed
[7] P. Hansen and N. Mladenovic’, “Variable neighborhood search: automated control systems,” Nonlinear World, vol. 9, no. 8, pp. 535-
Principles and applications,” Eur. J. Oper. Res., vol. 130, no. 3, pp. 538, 2011.
449-467, 2001.
[21] V. Mokshin, A. Kirpichnikov, A. Soiko, “Simulation and
[8] F. Parreo, R. Alvarez-Valds, J.F. Oliveira, J.M. Tamarit, “A hybrid optimization of the cargo terminal in the AnyLogic environment,”
GRAPS/VND algorithm for two-and three-dimensional bin packing,” Journal of Physics: Conference Series, vol. 1368, no. 4, 2019.
Annal. Oper. Res., vol. 179, no. 1, pp. 203-220, 2010.
[22] I.M. Yakimov, A.P. Kirpichnikov, V.V. Mokshin, Z.T. Yahina, “The
[9] T.G. Crainic, G. Perboli and R. Tadei, “Extreme point-based Modelling and Optimization of Machine Management System with
heuristics for three-dimensional bin packing,” Journal on Computing, Computer Numerical Control,” Advances in Automation, pp. 724-
vol. 20, no. 3, pp. 368-384, 2008. 731, 2019. DOI: 10.1007/978-3-030-39225-3_79.
[10] D. Liu, K. Tan, S. Huang, C. Goh and W. Ho, “On solving [23] I.M. Kulikovsky, “Lower computational cost in deep learning with
multiobjective bin packing problems using evolutionary particle nearly perfect linear separability of the training set,” Computer
swarm optimization,”European Journal of Operational Research, vol. Optics, vol. 44, no. 2, pp. 282-289, 2020. DOI: 10.18287/2412-6179-
190, pp. 357-382, 2008. CO-645
[11] A.V. Mokshin, V.V. Mokshin and L.M. Sharnin, “Adaptive genetic [24] Ye.V. Goshin and A.P. Kotov, “Parallel implementation of the multi-
algorithms used to analyze behavior of complex system,” view image segmentation algorithm using the Hough transform,”
Communications in Nonlinear Science and Numerical Simulation, Computer Optics, vol. 41, no. 4, pp. 588-591, 2017. DOI: 10.18287/
vol. 71, pp. 174-186, 2019. DOI: 10.1016/j.cnsns.2018.11.014. 2412-6179-2017-41-4-588-591.

VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 97