Packing algorithm inspired by gravitational and electromagnetic effects
- PDF / 4,725,815 Bytes
- 14 Pages / 595.276 x 790.866 pts Page_size
- 56 Downloads / 199 Views
(0123456789().,-volV)(0123456789(). ,- volV)
Packing algorithm inspired by gravitational and electromagnetic effects Felix Martinez-Rios1 • Alfonso Murillo-Suarez1
Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract This paper introduces a faster and more efficient algorithm for solving a two-dimension packing problem. This common optimization problem takes a set of geometrical objects and tries to find the best form of packing them in a space with specific characteristics, called container. The visualization of nanoscale electromagnetic fields was the inspiration for this new algorithm, using the electromagnetic field between the previously placed objects, this paper explains how to determine the best positions for to place the remaining ones. Two gravitational phenomena are also simulated to achieve better results: shaken and gravity. They help to compact the objects to reduce the occupied space. This paper shows the executions of the packing algorithm for four types of containers: rectangles, squares, triangles, and circles. Keywords Optimization Packing problem Electromagnetic fields Nature-inspired algorithm Gravitational algorithms
1 Introduction Packing problem takes a set of geometrical objects and searches for the best configuration to pack them into a specific space, which is known as the container. Regular figures such as squares, triangles, and polygons are frequently used as containers in these problems, specifically in a two-dimensional configuration [21]. Using this last configuration, a common problem is to suit a set of equal-size circles in a squared container, trying to optimize the distance between its centers. This problem has applications in different areas, such as placement of cell phone antennas to ensure coverage of a geographical area, the problem of storing cylindrical containers in an open area, packaging containers such as bottles and cans in a box, the problem of how to plant trees to achieve the maximum density of forested areas, designs of automotive panels in the automotive industry, etc. [3, 6, 10].
& Felix Martinez-Rios [email protected] Alfonso Murillo-Suarez [email protected] 1
Packing circles of known and equal size in a region that presents some physical limitations leads to a problem of continuous global optimization [1]. This has inspired some authors to use this problem to find the extreme values of objective functions [2]. For solving the packaging problem a non-convex and non-linear optimization model is proposed so that the variables are conformed by the coordinates of the points for placing the objects. When the problem changes because the circles have different sizes, the complexity increases and it is almost impossible to find the optimal solution with a traditional method, so heuristic algorithms are used to try to solve the problem, a large amount of local optima that packing problem presents make NLP optimizers fail in search of global optima, so this is where the heuristic methods capacity of exploring
Data Loading...
