Skip to main navigation Skip to search Skip to main content

Packing circles in the smallest circle: An adaptive hybrid algorithm

  • Université de Picardie Jules Verne

Research output: Contribution to journal › Article › peer-review

27 Scopus citations

Abstract

The circular packing problem (CPP) consists of packing n circles C i of known radii ri, iε=N={1,.., n}, into the smallest containing circle. The objective is to determine the coordinates (xi, yi) of the centre of Ci, iεN, as well as the radius r and centre (x, y) of. CPP, which is a variant of the two-dimensional open-dimension problem, is NP hard. This paper presents an adaptive algorithm that incorporates nested partitioning within a tabu search and applies some diversification strategies to obtain a (near) global optimum. The tabu search is to identify the n circles ordering, whereas the nested partitioning is to determine the n circles positions that yield the smallest r. The computational results show the efficiency of the proposed algorithm.

Original languageEnglish
Pages (from-to)1917-1930
Number of pages14
JournalJournal of the Operational Research Society
Volume62
Issue number11
DOIs
StatePublished - Nov 2011

Keywords

  • circular packing
  • heuristics
  • nested partitioning
  • non-linear programming
  • tabu search

Fingerprint

Dive into the research topics of 'Packing circles in the smallest circle: An adaptive hybrid algorithm'. Together they form a unique fingerprint.

Cite this