کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
481815 1446186 2007 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A dynamic adaptive local search algorithm for the circular packing problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
A dynamic adaptive local search algorithm for the circular packing problem
چکیده انگلیسی

This paper studies the circular packing problem (CPP) which consists of packing n non-identical circles Ci of known radius ri, i ∈ N = {1, … , n}, into the smallest containing circle C. The objective is to determine the coordinates (xi, yi) of the center of Ci, i ∈ N, as well as the radius r and center (x, y) of C. This problem, which is a variant of the two-dimensional open dimension problem, is solved using a two-step, dynamic, adaptive, local search algorithm. At each iteration, the algorithm identifies the set of potential “best local positions” of a circle Ci, i ∈ N, given the positions of the previously packed circles, and determines for each of these positions the coordinates and radius of the smallest containing circle. The “best local position” minimizes the radius of the current containing circle. That is, every time an additional circle is packed, both the center and the radius of the containing circle are dynamically updated, and the smallest containing circle is known. The experimental results reflect the good performance of the algorithm.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 183, Issue 3, 16 December 2007, Pages 1280–1294
نویسندگان
, ,