Algorithms For Solving The Circle Packing With Equilibrium Constraints Problem

It is known that the NP-hard problem is difficult to solve in computer science. At thesame time, they are widely used in everyday life and have attracted many researchers tostudy and put forward a number of related efficient solution algorithms. The circlepacking with equilibrium constraints problem (CPECP), as a two-dimensional packingproblem with the background of satellite module layout design, is an NP hard layoutoptimization problem. It is a complex global optimization problem with continuoussolution space, is an important extension of the circle packing problem (CPP) byintroducing the static equilibrium.Based on the characteristics of the CPECP, two new quasi-physical models areintroduced. One is to mimic the elastic movement driven by repelling forces fromextruded disks, the other is to simulate a whole translation movement of the disks drivenby a pulling force from an imaginative elastic rope connecting the centroid of the disksand the center of the container. We combine these two models and form a quasi-physicalmodel with single objective function. In the local search process, inspired by thecoarse-to-fine control strategy in the manufacturing industry, coarse tuning algorithm andfine tuning algorithm are proposed. In this way, the calculation neither spends too muchsearching time at local minimum traps nor easily misses promising areas that may lead toa global optimum. A basin hopping with taboo strategy is adopted when the calculationfalls into a local minimum trap, and this strategy can lead calculation jumps out of thecurrent basin, at the same time can avoid repeated search for the same area, therebyimproving the search efficiency. Furthermore, in order to keep the diversification of thesearching process, we introduce the idea of the Genetic Algorithm, and then combine thecoarse-to-fine quasi-physical method and basin hopping with taboo strategy proposedQuasi-Physical algorithm based on Coarse-to-Fine Adjustment (QPCFA). Not only canQPCFA keep the diversity of the searching space to facilitate the global search, but also ithas faster local search speed.Experiments were on two sets of11representative test instances. Computational results show that QPCFA achieved new and better results on six instances, at the sametime it matched the current best records on the other five. Also, the solutions obtained byQPCFA have smaller equilibrium deviations than others published in the literature.Furthermore, a method of naturally generating new instances by utilizing the circlepacking problem (CPP) instances taken from the literature is proposed, and gavecomputing results on these34new instances.