SCIENCE CHINA Information Sciences, Volume 61 , Issue 4 : 048104(2018) https://doi.org/10.1007/s11432-017-9223-3

Packing unequal circles into a square container based on the narrow action spaces

More info
  • ReceivedMar 22, 2017
  • AcceptedAug 16, 2017
  • PublishedMar 16, 2018


There is no abstract available for this article.


This work was supported by National Natural Science Foundation of China (Grant Nos. 61472147, 61370183, 61602196, 61772219), and Shenzhen Science and Technology Planning Project (Grant No. JCYJ20170307154749425).


[1] Hifi M, M'Hallah R. A Literature Review on Circle and Sphere Packing Problems: Models and Methodologies. Adv Operations Res, 2009, 2009: 1-22 CrossRef Google Scholar

[2] Szabó P G, Markót M C, Csendes T, et al. New Approaches to Circle Packing in a Square: With Program Codes. Berlin: Springer, 2007. Google Scholar

[3] Liu J, Zhang K, Yao Y. A heuristic quasi-physical algorithm with coarse and fine adjustment for multi-objective weighted circles packing problem. Comput Industrial Eng, 2016, 101: 416-426 CrossRef Google Scholar

[4] He K, Mo D, Ye T. A coarse-to-fine quasi-physical optimization method for solving the circle packing problem with equilibrium constraints. Comput Industrial Eng, 2013, 66: 1049-1060 CrossRef Google Scholar

[5] He K, Huang W, Jin Y. An efficient deterministic heuristic for two-dimensional rectangular packing. Comput Operations Res, 2012, 39: 1355-1363 CrossRef Google Scholar

[6] He K, Huang M, Yang C. An action-space-based global optimization algorithm for packing circles into a square container. Comput Operations Res, 2015, 58: 67-74 CrossRef Google Scholar

[7] Liu D C, Nocedal J. On the limited memory BFGS method for large scale optimization. Math Programming, 1989, 45: 503-528 CrossRef Google Scholar

[8] Fu Z, Huang W, Lü Z. Iterated tabu search for the circular open dimension problem. Eur J Operational Res, 2013, 225: 236-243 CrossRef Google Scholar

  • Figure 1

    (Color online) An example of the narrow action spaces.


    Algorithm 1 The proposed PAS-PCI algorithm


    reach the limitation of time; return NULL.

    Require:Container size $L_0$, item sizes $r_1,~\dots,~r_n$, number of patterns G, selection number m;

    Output:Feasible pattern ($X,~L$) or Null;


    Randomly generate G patterns, store in array A;

    for each pattern Ai

    Ai $\gets$ LBFGS (Ai);

    if $U_e$(Ai) $~<~10^{-20}$ then

    (Ai,L)$\gets$post-processing algorithm (Ai,L);

    return (Ai,L);

    end if

    end for



    for $k_p~=~1$ TO $20$

    Select m patterns with the lowest $U_e$;

    Generate 39 new patterns using the basin-hopping algorithm for each selected pattern;

    for each of the new $39~\times~m$ patterns

    $(X&apos;,L)\gets$ LBFGS$(X,L)$;

    if $U_e(X&apos;)~~<~10^{-20}$ then

    $(X&apos;,L)\gets~$ post-processing$(X&apos;,L)$;

    return $(X&apos;,L)$;

    end if

    end for

    end for

    Select m patterns with the lowest $U_e$, do perturbation operator, $k_b\gets~k_{b+1}$;