محمد حسين دوش ( مدرس )
كلية التربية للبنات - علوم الحاسوب ( مسؤول شعبة )
[email protected]
Packing Unequal Circles into a Square Container based on the Narrow Action Spaces
بحث النوع:
علوم التخصص العام:
He Kun اسم الناشر:
DOSH MOHAMMED Jin Yan اسماء المساعدين:
SCIENCE CHINA Information Sciences journal الجهة الناشرة:
The journal under the Springer Publisher home with impact factor 1.628 class B  
2017 سنة النشر:


We propose a Partitioned Action Space and Partitioned Circle Items (PAS-PCI) approach for the problem of packing unequal circle items in a single two-dimensional square container such that the size of the container is minimized. The PAS is used to partition the narrow action space on the long side to find two equal action spaces to fully utilize the unoccupied spaces. The PCI are used to partition the circle items into four groups based on item sizes for the basin-hopping strategy. Starting from several random patterns, PAS-PCI runs the following potential descent method and basin-hopping strategy iteratively. It finds patterns with the local minimum potential energy by the limited-memory BFGS (LBFGS) algorithm, then it selects the circular items having the most deformations and moves them to some large vacant space or randomly chosen vacant space. By adapting the action space defined for the rectangular packing problem, we approximate each circular item as a rectangular item, thus making it much easier to find comparatively larger vacant spaces for any given pattern. The tabu strategy is adopted to prevent cycling and enhance diversity during the search procedure. Several other strategies, such as randomly swapping pair-wise similar circle items in each set, are combined to increase the diversity of the patterns. Experimental results show that the PAS-PCI algorithm is effective for the addressed problem.