Adaptive Large Neighborhood Search for Circle Bin Packing Problem

2020·Arxiv

1. Introduction

1. Introduction

Packing problems form an important class of combinatorial optimization problems that have been well studied under numerous variants [1, 2, 3, 4]. It is a classic type of NP-hard problems, for which there is no deterministic algorithm to find exact solutions in polynomial time unless . Also, there are numerous applications in the industry, such as shipping industry [5, 6], manufacturing materials [7, 8], advertisement placement [9, 10], loading problems [11, 12], and more exotic applications like origami folding [13, 14]. Packing problems are well studied since 1832 Farkas et al.[15, 3] investigated the occupying rate (density) of packing circle items in a bounded equilateral triangle bin, and since then tremendous improvements have been made [16, 17]. In the past three decades, most researches focus on the single container packing. The container is either in square, circle, rectangle, or polygon shape [18], while the items can be rectangles, circles, triangles, or polygons.

As one of the most classic packing problem, the circle packing problem (CPP) is mainly concerned with packing circular items in a container. Researchers have proposed various methods for finding feasible near-optimal packing solutions [19, 20, 21, 22], which fall into two types: constructive optimization approach and global optimization approach.

The construction approach places the circle items one by one appropriately in the container based on a heuristic that defines the building rules to form a feasible solution. Most researches of this category either fix the position of the container’s dimension and pack the items sequentially satisfying the constraints [23], or adjust the size of the container using a constructive approach [22]. Representative approaches include the Maximum Hole Degree (MHD) based algorithms [24, 25, 26], among which Huang et al. [24] came up with two greedy algorithms: "B.10" places the circle items based

on MHD, while "B.15" strengthens the solution with a self-look-ahead search strategy. Another approach called Pruned Enriched Rosenbluth Method (PERM) [27, 28, 29] is a population control algorithm incorporating the MHD strategy. There are also other heuristics such as the Best Local Position (BLP) based approaches [30, 19, 31, 32], which selects the best feasible positions to place the items among other positions that minimizes the size of the container.

On the other hand, the global optimization technique [33] tries to solve the packing problem by improving the solution iteratively based on an initial solution, which is subdivided into two types. The first type is called the quasi-physical quasi-human algorithm [34, 35, 36], which is mostly motivated by some physical phenomenon, or some wisdom observed in human activities [37, 38]. The second type is called the meta-heuristic optimization, mainly built by defining an evaluation function that employs a trade-off of randomisation and local search that directs and re-models the basic heuristic to generate feasible solutions. The meta-heuristic searches an estimation in the solution space closing to the global optimum. Representative algorithms include the hybrid algorithm [39] that combines the simulated annealing and Tabu search [40, 41]. Recently another hybrid algorithm was proposed by combining Tabu search and Variable Neighborhood Descent, and yield state-of-the-art results [42].

In this work, we address a new variant of packing problem called the two-dimensional circle bin packing problem (CBPP) [21]. Given a collection of circles specified by their radii, we are asked to pack all items into a minimum number of identical square bins. A packing is called feasible if no circles overlap with each other or no circle be out of the bin boundary. The CBPP is a new type of geometric bin packing problem, and it is related to the well-studied 2D bin packing problem [43, 44], which consists in packing a set of rectangular items into a minimum number of identical rectangular bins.

This manuscript is an extended version with significant

improvement on the algorithm of our previous conference publication [21], among which we first introduce this problem and propose a Greedy Algorithm with Corner Occupying Action (GACOA) to construct a feasible dense layout [21]. In this paper, we further strengthen the packing quality and propose an Adaptive Large Neighborhood Search (ALNS) algorithm. ALNS first calls GACOA to construct an initial solution, then iteratively perturbs the current solution by randomly selecting any two used bins and unassigning circles that intersect a random picked region in each of the selected bin. Then we use GACOA to pack the outside circles back into the bin in order to form a complete solution. The complete solution is accepted if the update layout increases the objective function or the decrease on the objective function is probabilistically allowed under the current annealing temperature. Note that the objective function is not the number of bins used but is defined to assist in weighing the performance to reach the global optimum of the new candidate solution. Computational numerical results show that ALNS always outperforms GACOA in improving the objective function, and sometimes ALNS even outputs packing patterns with less number of bins. In this work, we make three main contributions: 1) we design a new form of objective function, embed-

ding the number of containers used and the maximum dif-

ference between the containers with the highest density and the box with the lowest density. The new objective function can help identify the quality of the assignment, especially in the general case with the same number of bins. 2) we propose a method for local search on the complete

assignment solution. We select two bins randomly and gen-

erate a rectangular area for each bin with equal area. All the circles that intersect the rectangular area were unassigned and the remaining circles form the new partial solution. 3) we modify the conditions for receiving the new partial

solution. The previous local neighborhood search algorithm

only accepts new partial solutions with larger objective functions. However, it is not conductive to the global optimum to some extent. We apply the idea of simulated annealing to this new algorithm so that partial solutions with lower objective function values can also be accepted with a variable possibility. The remaining of this paper is organised as follows. Sec-

tion 2 introduces the mathematical constraints for the given

problem, Section 3 presents the two frameworks used for the development of our algorithm. Section 4 further describes the objective function as well as the experimental setup. All the algorithms are computationally experimented and the results presented in Section 5. Finally, Section 6 concludes with recommendations for future work.

2. Problem Formulation

Given a set of circles where item is in radius and identical square bins with side length (w.l.g. for any circle ), the CBPP problem is to locate the center coordinates of each such that any item is totally inside a container and there is no overlapping between any two items.

The goal is to minimize the number of used bins, denoted as .

A feasible solution to the CBPP is a partition of the items into sets for the bins, and the packing constraints are satisfied in each bin. An optimal solution is the one in which , the number of bins used, cannot be made any smaller. A summary of the necessary parameters is given in Table 1.

Table 1 Parameter regulation

Assume that the bottom left corner of each bin is placed at (0, 0) in it’s own coordinate system. we formulate the CBPP as a constraint optimization problem.

where

which implies that each circle is packed exactly once. Further, if a bin is used, then

And, finally, for circles that are in the same bin, 1, and , no overlap is allowed, implying that

Specifically, let the circles be ordered by their radii so that . To ensure that no item passes across the boundary of the bin, we ask that

Conditions (1)–(4) along with (5) are the constraints for CBPP. The overall goal of CBPP is to use as few bins as possible to pack the circles, which is

3. General Search Framework

In this section, we introduce two general optimization search frameworks for constraint optimization problem that we will use for the development of our CBPP algorithm. The two frameworks are Large Neighborhood Search (LNS), and a variation of the well-studied simulated annealing process [45], Adaptive Large Neighborhood Search (ALNS) [46]. A particular advantage of ALNS is the capacity to move the iterated solution out of the local optimum.

3.1. Large neighborhood search

Large neighborhood search (LNS) is a technique to iteratively solve constraint optimization problems [46, 47]. At each iteration, the goal is to find a more promising candidate solution to the problem, and traverse a better search path through the solution space.

Definition 1. (Constraint optimization problem, COP). A constraint optimization problem is de-fined by an array of variables that can take values from a given domain , subject to a set of constraints is the objective function to measure the performance of assignment. An assignment is an array of values . A constraint is a predicate that decides whether an assignment is locally valid. A solution to is an assignment that is locally valid for all constraints in , i.e. is true for all . The optimal solution of is a solution that maximizes the objective function .

At each iteration, LNS relaxes and repairs the solution by randomly generating and then completing a partial solution (Alg. 1). If the new assignment has higher objective function value, the previous assignment will be replaced.

2 initial temperature;

3 휃 Θ;

4 for to do 5 generate_partial_solution (); 6 complete_partial_solution(); 7 if acceptMove() then 8 ;

9 end

11 end

4. ALNS for CBPP

4.1. Domain and objective function

For the CBPP as a constraint optimization problem (COP), we define its domain as follows. For each circle , its assignment variables include . We simplify the notation to if . The corresponding domain defines all possible assignments of a circle in the bin–coordinate space. Since each circle is constrained by an indicator function to be put only in a single bin, we abuse the notation slightly, simply use to denote , and place an emphasis on the circles rather than the containers, and each of the components where is a 3-tuple denoted as . Thus, when referring to a solution to , we write , and corresponds to the domain for the tuple variables. So denotes a possible packing.

Let be the area of a bin, the density of of a packing is defined as

where is the set of items assigned to . Let be the number of used bins for a solution , so

Here denotes the density of the sparsest bin and the density of the densest bin. We define a useful objective function, which will form part of our algorithm as

The larger the value of is, the better the packing is, since an increase in corresponds to a denser packing as circles move out of lower density bins. In order to clarify the process for taking a complete candidate solution for to a partial solution, the following formal definitions are required.

Note that , this term is used for regularization. It implies that using fewer bins is preferable, that a difference in the number of bins is enough to compare two candidate solutions. With the same number of used bins in different solutions, we focus on the fullest bin and the emptiest bin on each candidate solution. The more dense the fullest bin is, the less wasted space is. The more sparse the emptiest bin is, the more concentrated the remaining stillreserved space is, which means it would be easier for assigning subsequent circles. So, the difference in density between the fullest bin and the emptiest bin determines the quality of each candidate solution.

4.2. Construct initial solution

An initial solution can be quickly constructed by our greedy algorithm GACOA (Alg. 3).

For each circle, GACOA computes a set of candidate positions by greedily moving on to the next bin if a circle cannot be packed in any of the previous bins. In particular, each circle is packed according to the following criteria.

Definition 5. (Candidate packing position). A candidatepacking position of a circle in a bin is any position that places the circle tangent to a) any two packed items, or b) a packed item and the border of the bin, or c) two perpendicular sides of the bin (i.e. the corner).

Definition 6. (Feasible packing position). A packing position of a circle in a bin is feasible if it does not violate any constraints: circles do not overlap and be fully contained in a bin. (See Eq. (1)–(5) for detailed constraints).

Definition 7. (Quality of packing position). The distance between the feasible packing position and the border of the bin is given by

where (resp. ) is a distance between the center of the circle and the closer side of the bin in the horizontal (resp. vertical) direction. For a circle in the current target bin, all

feasible positions in the bin are sorted in dictionary order of . The smaller, the better.

We call an action that places a circle onto one of its candidate packing positions a Corner Occupying Action (COA). GACOA works by packing circles one by one in the decreasing order of their radii. Each circle considers the target bin in the increasing order of the bin index . For bin , a feasible candidate packing position with the highest quality is selected, i.e. a feasible assignment that maximizes will be executed. Thus, the best feasible COA is selected that favours positions closer to the border of the bin. If there is no feasible assignment in bin , we will try to pack in the next bin . The pseudo code is given in Alg. 3.

Partial solutions are generated from a complete solution by selecting two bins at random and do perturbations. We randomly select a rectangular area of equal size in each bin, all circles that intersect the two rectangular areas will be taken out and added to the remain2assign set, and the complete solution becomes a partial solution. The unassigned circles will be reassigned based on the partial solution. This is equivalent to perturbing a complete solution that has reached a local optimum. Let function random_intsreturns distinct integers randomly selected from set . Let function random_real returns a random real number .

Alg. 5 randomly selects a circle in the non-empty bin, and then randomly generates a rectangular area with the circle center be the center of the area. This guarantees that at

least one circle will intersect the generated rectangular area (Here we simply use the envelope rectangle of the circle to check its intersection with the area). In most cases, more than one circle items intersect the rectangular area and will be unassigned at each iteration. We choose to select two bins and generate one rectangular area for each bin. Only one bin can be sampled at a time, but when the partial solution and unassigned circle set are continued to be placed in the future, in the worst case, it will be put back as it is to obtain the same complete solution as before. The worst instance is that the previous partial solution did not leave enough free space to allocate the unassigned circles except for the generated area. If there is only one bin and one rectangular area, the unassigned circles are very likely to be put back into the previous generated rectangular area during the iteration, which means that this iteration process has no effect and does not help jump out of the local optimum. Thus, two bins are selected for each iteration so that the unassigned circles have more free space to be allocated. Even in the worst case, the algorithm will try to exchange the circles in the two rectangular areas, which ensures that there will be some disturbance per iteration. Of course, an alternative way is to sample only one bin and generate two rectangular areas for the bin, but two rectangular areas in different bins can increase the randomness.

4.3. Complete a partial solution

Completing a partial solution is performed efficiently by the GACOA algorithm (Alg. 3) restricted to the bins from which circles were unassigned in the previous step.

is the partial solution generated by generate_partial_solution(). GACOA is used to complete the partial solution.

4.4. Acceptance metric

A solution is accepted if it increases the objective function or if the decrease in the objective function is probabilistically allowed given the current annealing temperature

. This is the well-known simulated annealing move acceptance criteria [45],

4.5. ALNS for CBPP

The complete algorithm for solving CBPP requires various steps from the above. The ALNS procedure is started using the initial solution along with the temperature and the number of iterations . The initial solution is then broken using Alg. 4 and re-completed using the new solution filled by GACOA. This procedure outputs a new candidate solution, which is then either accepted or rejected based on the acceptance metric with simulated annealing. At which point,

Table 2 Experimental results on the fixed benchmarks with square bins when . The average improvement is 0.19.

if the iteration limit has not reached, the process restarts using the new solution as an input

An illustration of the entire parameter setup flow of ALNS algorithm is shown in Figure 1.

5. Computational Experiments

To evaluate the competency of the proposed approach, we implemented the ALNS for CBPP using the Visual C++ programming language. All results were generated by setting (Alg. 2) and obtained in a computer with Intel Core i7-8550U CPU @ 1.80GHz.

We generated benchmarks based on two groups of instances downloaded from www.packomonia.com for Single Circle Packing Problem (SCCP): for wide variation instances and for smaller variation instances. On the packomania website, we use the range seed (number of circles for SCCP) from 8 to 20, and generate sets of benchmarks as follows: For each square bin, the best solution found in [48] for the SCPP was used to fix the bin size as the best known record and we generate two sets of benchmarks called “fixed" and “random".Let be the set of circles packed in the current best solution for SCPP . The fixed set of CBPP benchmarks contains exactly 5 copies of each circle packing for SCPP. The rand set of CBPP benchmarks contains a random number ()

of copies of each circle (i.e., the number of copies of each circle varies across the same benchmark) packed for SCPP.

In the following tables we get generated instances from the two groups of instances, we compare the number of bins and the objective value for the best solution obtained by our search algorithm ALNS with the solution obtained from our constructive algorithm GACOA. They contain, for each original number of circles () and actual number of replicated circles in the CBPP benchmark (), two rows showing the bin densities for ALNS (A) and GACOA (G) algorithm. The last two columns contain the final value of the objective function obtained in each algorithm and the relative improvement of ALNS over GACOA. Figure 2 shows in depth the typical behavior in comparison of ALNS and GACOA on the two benchmark instances. The objective function () in the y-axis under the number of circles in the x-axis. We can observe the packing occupying rate of ALNS is higher than that of GACOA. An in-depth analysis is explained in Section 5.1 and Section 5.2.

5.1. Comparison on 푟 = 푖

We run ALNS and GACOA on the benchmark instances of . The number of unequal circle items ranges from 8 to 20 seeds for both fixed and random square settings. Table 2 shows the computational results of the fixed copies of 5 for each . Table 3 displays the random number of copies of the circle items ranging from of the corresponding

Figure 1: The parameter setup flow of ALNS.

Figure 2: ALNS vs. GACOA.

Figure 3: Solution for the fixed benchmark when

seed. From Table 2 we can observe that when or 60 on the fixed benchmark, ALNS utilises 5 bins, while GACOA uses 6 bins to pack the circle items. Figure 3 illustrates the packing layout for . On the other hand, for the random instances in Table 3 when or 72, ALNS also minimizes the number of bins by packing circles in 4 bins while GACOA packs in 5 bins. Figure 4 illustrates the packing layout for . In summary, from the results of all the instances, ALNS returns feasible results, and has an overall average improvement of 19% for the fixed benchmarks and 12% for the random benchmarks when compared to GACOA.

5.2. Comparison on 푟푖 =√푖

Similarly we also run ALNS and GACOA on the benchmark instances of , which contains a smaller variation of radii. Table 4 contains fixed instances while Table 5 contains random instances. The instances also range from 8 to 20 seeds. As an illustration, we select and from Table 4 and illustrate the layout in Figure 5. The occupying rate for the first three bins is higher for ALNS when compared to that of GACOA, showing that most circle items have maximally occupied each bin’s area. The fourth last bin’s density of the packed items for ALNS is lower than that of GACOA, indicating that ALNS contains fewer packed circle items in the last bin. On the random benchmarks in Table 5 for at instance 8, 12, 13, 14 and

Table 3 Experimental results on the random benchmarks for . The average improvement is 0.12.

15, we also observe that ALNS uses one lesser bin in total when compared to GACOA. The average improvement of ALNS over GACOA is 22% for the fixed instances and 23% for the random instances, respectively.

5.3. Further discussion

The run-times for ALNS at each benchmark are shown in Table 6 (column of in seconds). We see that ALNS computes the instances efficiently in less than 300 seconds for 100 items. By comparison, as a greedy algorithm, GACOA

Table 4 Experimental results on the fixed benchmarks when . The average improvement of 0.22. .

8 7

7 7

Figure 5: Solution for the fixed benchmark when

completes the calculation in microseconds on any of these benchmarks. Such property facilitates the high efficiency of the ALNS algorithm.

In summary, for all the generated instances, we compare the number of bins and the objective value for the best solution obtained by ALNS algorithm with solutions obtained by GACOA. The results clearly show that ALNS consis-

tently improves the objective function value as compared to GACOA over all sets of benchmarks, and it was even able to reduce the number of bins used in some benchmarks.

Table 5 Experimental results on the random benchmarks for . The average improvement is 0.23.

The results show that our objective function does guide the ALNS algorithm to search for dense packing and promote reducing the number of bins used.

6. Conclusions

We address a new type of packing problem, two dimensional circle bin packing problem (2D-CBPP), and propose an adaptive local search algorithm for solving this NP-Hard problem. The algorithm adopts a simulated annealing search on our greedy constructive algorithm. The initial solution is

Table 6 Runtimes for ALNS execution in all benchmarks.

built by the greedy algorithm. Then during the search, we generate a partial solution by randomly selecting rectangular areas in two bins and remove the circle items that intersect the areas. And we implement our greedy algorithm for completing partial solutions during the search. To facilitate the search, we design a new form of objective function, embedding the number of containers used and the maximum gap of the densities of different containers. A new solution is conditionally accepted by simulated annealing, completing one iteration of the search.

Despite to all the improvements in this work, it is highly noted that the proposed problem is indeed challenging for combinatorial optimization heuristics and future researches are needed to get better solutions and generate high quality benchmarks. Implementing an adaptive local neighborhood search seems to be an attractive meta-heuristic to adopt. we would like to explore the idea to other circle bin packing problems, and extend our approach in addressing three dimensional circle bin packing problem which is more challenging with many applications that deserves proper attention.

Acknowledgement

This work was supported by the National Natural Science Foundation of China (Grant No. U1836204, U1936108) and the Fundamental Research Funds for the Central Universities (2019kfyXKJC021).

References

[1] E. Specht, A precise algorithm to detect voids in polydisperse circle packings, Proceedings of the Royal Society of London Series A 471 (2015) 19.

[2] M. M. Akbar, M. S. Rahman, M. Kaykobad, E. Manning, G. Shoja, Solving the multidimensional multiple-choice knapsack problem by constructing convex hulls, Computers & Operations Research 33 (2006).

[3] S. P. G., M. C. Markot, T. Csendes, E. Specht, L. G. Casado, I. Gar- cia a, New Approaches to Circle Packing in a Square: With Program

Codes (Springer Optimization and Its Applications), Springer-Verlag, 2007.

[4] S. G, Greco.O, Conca.P, Cutello.V, P. M, N. G, Packing equal disks in a unit square: an immunological optimization approach, in: International Workshop on Artificial Immune Systems (AIS), 2015, pp. 1–5.

[5] P. Thapatsuwan, P. Pongcharoen, C. Hicks, W. Chainate, Develop- ment of a stochastic optimisation tool for solving the multiple container packing problems, International Journal of Production Economics 140 (2012) 737 – 748.

[6] T. A. Toffolo, E. Esprit, T. Wauters, G. V. Berghe, A two-dimensional heuristic decomposition approach to a three-dimensional multiple container loading problem, European Journal of Operational Research 257 (2017) 526 – 538.

[7] G. WÃďscher, H. HauÃ§ner, H. Schumann, An improved typology of cutting and packing problems, European Journal of Operational Research 183 (2007) 1109 – 1130.

[8] M. A, Colla.V, Nastasi.G, S. M., I. V, A bin packing algorithm for steel production, 2016, pp. 19–24.

[9] A. Freund, J. S. Naor, Approximating the advertisement placement problem, Journal of Scheduling 7 (2004) 365–374.

[10] M. Dawande, S. Kumar, C. Sriskandarajah, A note on the minspace problem, Journal of Scheduling 8 (2005) 97–106.

[11] B. E. G, M. J.M.z, R. D.Pn, Optimizing the packing of cylinders into a rectangular container: A nonlinear approach, European Journal of Operational Research 160 (2005) 19 – 33.

[12] L. Junqueira, R. Morabito, D. S. Yamashita, Three-dimensional con- tainer loading models with cargo stability and load bearing constraints, Computers & Operations Research 39 (2012) 74 – 85.

[13] M. L. Demaine, S. P. Fekete, R. J. Lang, Circle packing for origami design is hard, ArXiv abs/1008.1224 (2010).

[14] B. An, S. Miyashita, A. Ong, M. T. Tolley, M. L. Demaine, E. D. Demaine, R. J. Wood, D. Rus, An end-to-end approach to self-folding origami structures, IEEE Transactions on Robotics 34 (2018) 1409– 1424.

[15] F. Bolyai, Wolfgangi bolyai de bolya: Tentamen iuventutem stu- diosam in elementa math-eseos purae elementaris ac sublimioris methodo intuitiva evidentiaque huic propria introducendi,cum appendice triplici. in latin. marosvasarhelyini,second edition in 1904 2 (1832-33) 119–122.

[16] R. L. Graham, B. D. Lubachevsky, Dense packings of equal disks in an equilateral triangle: From 22 to 34 and beyond, J. of Combinatorics 2 (1995) pp. (electronic).

[17] R. L. G. B. D. Lubachevsky, Dense packings of equal disks in an equi- lateral triangle: From 22 to 34 and beyond, The Electronic Journal of

Combinatorics 2 (1995), A1 (2004) 39.

[18] C. LÃşpez, J. Beasley, A heuristic for the circle packing problem with a variety of containers, European Journal of Operational Research 214 (2011) 512 – 525.

[19] M. Hifi, R. MâĂŹHallah, A dynamic adaptive local search algorithm for the circular packing problem, European Journal of Operational Research 183 (2007) 1280 – 1294.

[20] K. He, W. Huang, An efficient placement heuristic for three- dimensional rectangular packing, Computers & Operations Research 38 (2011) 227 – 233.

[21] K. He, M. Dosh, A greedy heuristic based on corner occupying action for the 2d circular bin packing problem, Springer Singapore (2017) 75 – 85.

[22] Z. Zeng, X. Yu, K. He, W. Huang, Z. Fu, Iterated tabu search and variable neighborhood descent for packing unequal circles into a circular container, European Journal of Operational Research 250 (2016) 615–627.

[23] W. Dickinson, D. Guillot, A. Keaton, S. Xhumari, Optimal packings of up to five equal circles on a square flat torus, Contributions to Algebra and Geometry 52 (2011) 315–333.

[24] W. Huang, Y. Li, B. Jurkowiak, C. Li, R. Xu, A two-level search strat- egy for packing unequal circles into a circle container, in: Principles and Practice of Constraint Programming, Springer Berlin Heidelberg, 2003, pp. 868–872.

[25] W. Huang, Y. Li, C. Li, R. Xu, New heuristics for packing unequal circles into a circular container, Computers & Operations Research 33 (2006) 2125 – 2142.

[26] W. Huang, Y. Li, H. Akeb, C. Li, Greedy algorithms for packing un- equal circles into a rectangular container, Journal of the Operational Research Society 56 (2005) 539–548.

[27] Z. LÃĳ, W. Huang, Perm for solving circle packing problem, Com- puters & Operations Research 35 (2008) 1742 – 1755.

[28] H. P. Hsu, V. Mehra, W. Nadler, G. Peter, Growth based optimization algorithm for lattice heteropolymers, Phys. Rev. E 68 (2003) 021113.

[29] W. Huang, Z. P. Lu, H. Shi, Growth algorithm for finding low energy configurations of simple lattice proteins, Physics Review E 72 (2005) 016704.

[30] M. Hifi, R. MHallah, Approximate algorithms for constrained circular cutting problems, Computers & Operations Research 31 (2004) 675 – 694.

[31] M. Hifi, R. MâĂŹHallah, Adaptive and restarting techniques based algorithms for circular packing problems, Computational Optimization and Applications 39 (2008) 17–35.

[32] H. Akeb, M. Hifi, A hybrid beam search looking-ahead algorithm forÂătheÂăcircular packing problem, Journal of Combinatorial Optimization 20 (2010) 101–130.

[33] I. Castillo, F. J. Kampas, J. D. PintÃľr, Solving circle packing prob- lems by global optimization: Numerical results and industrial applications, European Journal of Operational Research 191 (2008) 786 – 802.

[34] D. Zhu, Quasi-human seniority-order algorithm for unequal circles packing, Chaos, Solitons & Fractals 89 (2016) 506 – 517.

[35] J. Liu, J. Li, Z. LÃĳ, Y. Xue, A quasi-human strategy-based improved basin filling algorithm for the orthogonal rectangular packing problem with mass balance constraint, Computers & Industrial Engineering 107 (2017) 196 – 210.

[36] K. He, H. Ye, Z. Wang, J. Liu, An efficient quasi-physical quasi- human algorithm for packing equal circles in a circular container, Computers & Operations Research 92 (2018) 26 – 36.

[37] K. He, M. Huang, C. Yang, An action-space-based global optimiza- tion algorithm for packing circles into a square container, Computers & Operations Research 58 (2015) 67 – 74.

[38] K. He, M. Dosh, S. Zou, Packing unequal circles into a square con- tainer by partitioning narrow action, spaces and circle items, CoRR abs/1701.00541 (2017).

[39] D. Zhang, A. Deng, An effective hybrid algorithm for the problem of packing circles into a larger containing circle, Computers & Operations Research 32 (2005) 1941 – 1951.

[40] F. Glover, Tabu searchâĂŤpart 1, ORSA Journal on computing 1 (1989) 190–206.

[41] F. Glover, Tabu searchâĂŤpart ii, ORSA Journal on computing 2 (1990) 4–32.

[42] Z. Zeng, X. Yu, K. He, Z. Fu, Adaptive tabu search and variable neigh- borhood descent for packing unequal circles into a square, Applied Soft Computing 65 (2018) 196 – 213.

[43] A. Lodi, S. Martello, D. Vigo, Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems, Journal on Computing 11 (1999) 345–357.

[44] N. Bansal, A. Lodi, M. Sviridenko, A tale of two dimensional bin packing, in: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS, 2005, pp. 657–666.

[45] S. Kirkpatrick, C. Gelatt, M. Vecchi, Optimization by simulated an- nealing, Science 220 (1983) 671–80.

[46] M. Gendreau, J.-Y. Potvin, et al., Handbook of metaheuristics, Vol. 272, Springer International Publishing, 2010.

[47] C. Larsson, Chapter 5 - optimization techniques, Academic Press, 2018, pp. 103 – 122.

[48] E. Specht, Packomania website 2018 www.packomania.com (2018).