An Action-space-based Global Optimization Algorithm For Packing Circles Into A Square Container

Packing problem is a well-known NP-hard problem, and it is concerned with how to pack a certain number of circles of given radius inside a container with no overlap. The shape of the container can be a circle, a rectangle, a square or a polygon, and the items can be circles, rectangles or irregular items. Packing problem has a wide range of applications in the areas of marine transportation, motor cycle industry, material cutting, fashion industry, wireless communication, food industries, etc. As an NP-hard problem, there exists no exact algorithm for solving it to optimality in polynomial time unless P = NP. Up to now, many heuristic methods are proposed for finding the results in the reasonable time.This paper proposes an action-space-based global optimization(ASGO) approach for the problem of packing unequal circles into a square container such that the size of the square is minimized. Starting from several random configurations, ASGO runs the following potential descent method and basin-hopping strategy iteratively. It finds configurations with the local minimum potential energy by the limited-memory BFGS(LBFGS) algorithm, then 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 configuration. The tabu strategy is adopted to prevent cycling and enhance the diversification during the search procedure. Several other strategies, such as swapping two similar circles or swapping two circles in different quadrants in the container, are combined to increase the diversity of the configurations.We compare the performance of ASGO on 68 benchmark instances at the Packomania website with the state-of-the-art results. ASGO obtains configurations with smaller square containers on 63 instances; at the same time it matches or approaches the current best results on the other five instances.