Beam search-based algorithms for the circular packing problem.

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.

MoreLess

Year of publication:	2007-11
Authors:	Akeb, Hakim ; Hifi, Mhand
Institutions:	Centre d'Économie de la Sorbonne, Université Paris 1 (Panthéon-Sorbonne)
Subject:	Circular packing \| dichotomous search \| beam search \| maximum hole degree

More details

Extent:	application/pdf
Series:	Documents de travail du Centre d'Economie de la Sorbonne. - ISSN 1955-611X.
Type of publication:	Book / Working Paper
Language:	French
Notes:	19 pages
Classification:	C44 - Statistical Decision Theory; Operations Research ; C61 - Optimization Techniques; Programming Models; Dynamic Analysis ; C63 - Computational Techniques
Source:	RePEc - Research Papers in Economics

Persistent link: https://ebvufind01.dmz1.zbw.eu/10005510602