Евристичний алгоритм для розрідженого пакування кругів

Abstract

Sparse packing refers to the placement of objects within a container maximizing the minimum Euclidean distance between them, as well as between the objects and the container boundary. This formulation is motivated by modern environmentally friendly and energy-efficient technologies, such as ultrasonic hardening and processing with detonating gas mixtures, used for cleaning complex shaped parts, obtained by 3D printing, from particles of non-sintered powder. The paper studies the problem of sparse packing of circles in a circular container. A heuristic algorithm employing nonlinear optimization and simulated annealing is proposed. Numerical experiments are provided to demonstrate the effectiveness of the approach.