Binary monkey algorithm for approximate packing non-congruent circles in a rectangular container

  • PDF / 1,310,626 Bytes
  • 10 Pages / 595.276 x 790.866 pts Page_size
  • 72 Downloads / 216 Views

DOWNLOAD

REPORT


(0123456789().,-volV)(0123456789().,-volV)

Binary monkey algorithm for approximate packing non-congruent circles in a rectangular container Rafael Torres-Escobar1



Jose´ Antonio Marmolejo-Saucedo2 • Igor Litvinchev3

Published online: 13 November 2018 Ó Springer Science+Business Media, LLC, part of Springer Nature 2018

Abstract A Packing problem consists in the best arrangement of several objects inside a bounded area named as the container. This arrangement must fulfill with technological constraints, for example, objects should not be overlapping. Some packing models for circular objects are typically formulated as non-convex optimization problems; where the continuous variables are the coordinates of the objects, so they are limited to not finding optimal solutions. Due to the combinatorial nature in the arrangement of such objects, heuristic methods are being used extensively which combine methods of global search and methods of local exhaustive search of local minima or their approximations. In this paper, we will address the packing problem for non-congruent (different size) circles with the binary version of the monkey algorithm which incorporates a cooperation process and a greedy strategy. We use a rectangular grid for covering the container. Every node in the grid represent potential positions for a circle. In this sense, binary monkey algorithm for the knapsack problem, can be used to solve de 0–1 approximate packing problem for non-congruet circles. The binary monkey problem uses two additional processes of the original monkey algorithm, these two processes are a greedy process and a cooperation processes. Keywords Circle packing  Optimization  Monkey algorithm  Heuristic  Evolutionary strategies

1 Introduction Packing problems can be important components in other studies such as cutting patterns, area coverage, the design of facilities, loading of vehicles, assignment, sequencing of equipment and chain management of supply [3, 5, 15, 22]. A Packing problem consists in the best arrangement of

& Rafael Torres-Escobar [email protected] Jose´ Antonio Marmolejo-Saucedo [email protected] Igor Litvinchev [email protected] 1

Universidad Anahuac Me´xico. Facultad de Ingenieria, Av. Universidad Ana´huac 46, Lomas Ana´huac, Huixquilucan, Estado de Me´xico 52786, Mexico

2

Facultad de Ingenierı´a, Universidad Panamericana, Augusto Rodin 498, Ciudad de Me´xico 03920, Mexico

3

Faculty of Mechanical and Electrical Engineering, Nuevo Leon State University, 66450 Monterrey, NL, Mexico

several objects inside a bounded area named as the container. This arrangement must fulfill with technological constraints, for example, objects should not be overlapping. The shape of the container may vary from a circle, a square, a rectangle, etc. An extension of the packing problem can be incorporated into the following problems [4, 6, 12]. This paper focuses on problems dealing with circular objects in two dimensions. Circular packing problems are difficult problems, owing to the combinatorial nature in the arra