Beam search-based algorithms for the circular packing problem

Hakim Akeb and Mhand Hifi ()
Additional contact information
Hakim Akeb: UPJV - Université de Picardie Jules Verne, ISC Paris - Institut Supérieur du Commerce de Paris
Mhand Hifi: UPJV - Université de Picardie Jules Verne, CES - Centre d'économie de la Sorbonne - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique

Post-Print from HAL

Abstract: In this paper, we propose to solve the circular packing problem (CPP) whose objective is to pack n different circles C(i) of known radius r(i) , i = 1, ..., n into the smallest containing circle C. The objective is to determine the radius r of C as well as the coordinates (x(i) , y(i) ) of the center of the circles C(i), i = 1, ..., n. This problem is solved by applying an adaptive algorithm that combines the beam search, the local position distance and the dichotomous search strategy. Decisions at each node of the developed tree are based on the well-known maximum hole degree that uses the local minimum distance. The computational results, on a set of instances taken from the literature, show the effectiveness of the proposed algorithms.

Keywords: Circular packing; dichotomous search; beam search; maximum hole degree; Placement circulaire; recherche dichotomique; recherche par faisceaux; distance minimum (search for similar items in EconPapers)
Date: 2007-11
References: Add references at CitEc
Citations:

Published in 2007

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:hal:journl:halshs-00188779

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().