Iterated dynamic thresholding search for packing equal circles into a circular container

Xiangjing Lai, Jin-Kao Hao, Dong Yue, Zhipeng Lü and Zhang-Hua Fu

European Journal of Operational Research, 2022, vol. 299, issue 1, 137-153

Abstract: Packing equal circles in a circle is a classic global optimization problem that has a rich research history and a number of relevant applications. The problem is computationally challenging due to the fact that the number of possible packing configurations grows exponentially with the number of circles. In this work, we propose a highly effective iterated dynamic thresholding search algorithm for solving this difficult problem. The algorithm integrates several features including a two-phase local optimization method, a dynamic thresholding search and a container adjustment procedure. Computational experiments on popular benchmark instances with up to N=320 circles show that the algorithm outperforms significantly the state-of-the-art algorithms. In particular, it improves the best-known results for 136 instances, while matching the best-known results for other 175 instances.

Keywords: Packing; Thresholding search; Global optimization; Heuristics (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721007360
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:299:y:2022:i:1:p:137-153

DOI: 10.1016/j.ejor.2021.08.044

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().