Solution-hashing search based on layout-graph transformation for unequal circle packing

Jianrong Zhou, Jiyao He and Kun He

European Journal of Operational Research, 2025, vol. 327, issue 1, 58-83

Abstract: The problem of packing unequal circles into a circular container is a classic and challenging optimization problem in the field of computational geometry. This study introduces a suite of innovative and efficient methods to tackle this problem. Firstly, we present a novel layout-graph transformation method that represents configurations as graphs, together with an inexact hash method facilitating fast comparison of configurations on isomorphism or similarity. Leveraging these advancements, we propose an iterative solution-hashing search algorithm adept at circumventing redundant exploration through efficient configuration recording. Additionally, we introduce several enhancements to refine the optimization and search processes, including an adaptive adjacency maintenance method, an efficient vacancy detection technique, and a Voronoi-based locating method. Our algorithm demonstrates excellent performance over existing state-of-the-art methods through comprehensive computational experiments across various benchmark instances, showcasing quality applicability and versatility. Notably, our algorithm improves the best-known results for 116 out of 239 benchmark instances while achieving parity with the remaining instances.

Keywords: Circle packing; Heuristics; Continuous optimization; Graph isomorphism; Solution hashing (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725003595
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:327:y:2025:i:1:p:58-83

DOI: 10.1016/j.ejor.2025.05.003

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 ().