کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10346198 698774 2013 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Packing unequal circles using formulation space search
ترجمه فارسی عنوان
بسته های محافل نابرابر با استفاده از فرمول جستجوی فضایی
کلمات کلیدی
بسته بندی دایره، فرم جستجوی فضای جستجو
ترجمه چکیده
در این مقاله، یک الگوریتم اکتشافی برای مشکل بسته شدن محافل نابرابر در یک ظرف اندازه ثابت مانند دایره واحد، مربع واحد یا مستطیل ارائه می کنیم. ما مشکل را به عنوان یکی از پوسته پوسته شدن حلقه های نابرابر در نظر می گیریم به طوری که همه آنها می توانند در ظرف قرار بگیرند. الگوریتم ما از یک مرحله بهینه سازی و فاز بهبودی تشکیل شده است. فاز بهینه سازی براساس روش جستجوی فضای فرمول است، در حالیکه فاز بهبود باعث اختلال در راه حل فعلی با تغییر دو حلقه می شود. نمونه هایی که در این کار مورد بررسی قرار می گیرند می توانند به دو دسته تقسیم شوند: نمونه هایی با تغییرات زیاد در شعاع و نمونه هایی با تغییرات کوچک در شعاع. ما شش ظروف مختلف را در نظر می گیریم: دایره، مربع، مستطیل، مثلث راست تقسیم شده، نیمه گرد و ربع دایره ای. نتایج محاسباتی نشان دهنده پیشرفت در مقایسه با کار قبلی در ادبیات است.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش مقاله
بسته های محافل نابرابر با استفاده از فرمول جستجوی فضایی
چکیده انگلیسی
In this paper we present a heuristic algorithm for the problem of packing unequal circles in a fixed size container such as the unit circle, the unit square or a rectangle. We view the problem as being one of scaling the radii of the unequal circles so that they can all be packed into the container. Our algorithm is composed of an optimisation phase and an improvement phase. The optimisation phase is based on the formulation space search method whilst the improvement phase creates a perturbation of the current solution by swapping two circles. The instances considered in this work can be categorised into two: instances with large variations in radii and instances with small variations in radii. We consider six different containers: circle, square, rectangle, right-angled isosceles triangle, semicircle and circular quadrant. Computational results show improvements over previous work in the literature.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 40, Issue 5, May 2013, Pages 1276-1288
نویسندگان
, ,