Open AccessHexagonal and Ring Packing Method for Solving Circle Packing Problem using Modified Heuristics
Author(s) -
Apoorva Shastri,
Sanjeev Sharma,
Aniket Nargundkar
Publication year - 2019
Publication title -
international journal of engineering and advanced technology
Language(s) - English
Resource type - Journals
ISSN - 2249-8958
DOI - 10.35940/ijeat.a9346.109119
Subject(s) - heuristics , packing problems , circle packing , heuristic , mathematical optimization , container (type theory) , set packing , computer science , bin packing problem , algorithm , hexagonal crystal system , ring (chemistry) , mathematics , geometry , engineering , set (abstract data type) , mechanical engineering , chemistry , bin , crystallography , programming language , organic chemistry
A heuristic technique is a perspective used for problem solving, which employs a problem specific domain knowledge which might not be optimal, but sufficient for the immediate goals. The most common heuristic is trial and error, employed everywhere and anywhere. One such application is Circle Packing Problem (CPP), which is difficult to solve as it is a NP problem which is of high theoretical and practical value. In this paper we consider uniform packing of unit circles (diameter 2) in an enclosing circle. To make this study possible a class of heuristic global optimization algorithm, the Energy Paving Algorithm and a generated Monte Carlo method were studied. The heuristics applied in this study are – ring and hexagonal. The computational effectiveness of our study has been validated against these sets of algorithms. One of the applied heuristics, Hexagon packing, being a ‘natural’ geometry showed better packing efficiency than existing literature. Our second heuristic shows, higher efficiency in terms of CPU run time but underutilized available outer area. In this study, the circles are packed in 2D which is a simplified version of the various problems existing in nature as container loading, sensor network layout which has been studied by mathematicians, computer scientists and operation researchers.