Beam search-based algorithms for the circular packing problem

Hakim Akeb and Mhand Hifi
Additional contact information
Hakim Akeb: Institut Sup rieur du Commerce et LaRIA
Mhand Hifi: LaRIA et Centre d'Economie de la Sorbonne

Documents de travail du Centre d'Economie de la Sorbonne from Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne

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 (search for similar items in EconPapers)
JEL-codes: C44 C61 C63 (search for similar items in EconPapers)
Pages: 19 pages
Date: 2007-11
New Economics Papers: this item is included in nep-cmp
References: Add references at CitEc
Citations:

Downloads: (external link)
https://shs.hal.science/halshs-00188779 (application/pdf)

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:mse:cesdoc:b07070

Access Statistics for this paper

More papers in Documents de travail du Centre d'Economie de la Sorbonne from Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne Contact information at EDIRC.
Bibliographic data for series maintained by Lucie Label ().