The Research On Heuristic Ant Colony Optimization For The Circle And Rectangle Packing Problem With Equilibrium Constraints And Its Application

Satellite module layout design is a combinatorial optimization problem whichmeans to find the optimal solution to palce all payloads of the satellite module in aspecified space. It is also the research hotspot of combination mathematics andoperational research. It concerns the knowledge of multi-subject and multi-domainsuch as logical reasoning, computer graphics, computational geometry, operationalresearch and so on. Satellite module layout design belongs to the NP-hard problembecause it can not find the exact solution in finite time. By simplifying theinstruments and equipments into cylinders and cuboids placed vertical on bearingsurfaces, satellite module layout design problem mainly contains the following threekinds of layout problems with performance constraints:(1) the circle packing problemwith the performance constraints;(2) the rectangle packing problem with theperformance constraints;(3) the circle and rectangle packing problem with theperformance constraints. It is more difficult to solve the latter than the first twoproblems and the existing methods mainly contain evolutionary algorithm,collaborative design and interactive evolutionary algorithm. Time-consuming of theinterference quantity calculation already becomes a bottleneck problem of furtherimproving the solution accuracy and computational efficiency. This work is supportedby a grant from the National Natural Science Foundation (61272294), Natural ScienceFoundation of Hunan Province (11JJ6050) and Research Foundation of EducationBureau of Hunan Province (11A120). Taking the layout design of the satellite modelas research background, this paper studies the two-dimensional circle and rectanglepacking problem with inertia constraints and proposes a heuristic ant colonyoptimization for this problem and a divide-conquer co-evolutionary algorithm forlayout design of simplified international commercial communications satellite module.Numerical exprements show that the proposed algorithm is feasible and effective. Theconcreate work and innovations are as follows:1. Aiming at the circle and rectangle packing problem, this paper proposes aheuristic method based on the knowledge obtained from its known information. It canquickly construct the feasible layout scheme.2. Aiming at the circle and rectangle packing problem with inertia constraints,this paper proposes a heuristic ant colony optimization which is the combination ofthe proposed heuristic algorithm and the ant colony optimization.We use the proposedalgorithm to optimize the envelope radius and rotary inertia of the layout schemes of four layout sub-problems on bearing surfaces of the satellite model. Experimentsshow that the performances of the proposed heuristic ant colony optimizationapproach are better than those of the existing algorithms for the circle and rectanglepacking problem with the rotary inertia constraints.3. Aiming at the satellite module layout design, this paper proposes a divide-conquer co-evolutionary algorithm. Firstly qusi-physical method based on thepotential energy function is used to further optimize the layout schemes of the layoutsub-problems on four bearing surfaces of the satellite model. Afterward, through theproposed particle swarm optimization method, errors of both the inertia angles andmass center of the whole layout scheme of the satellite model are optimized as smallas possible and its the envelope radius and rotary inertia keep unchanged. Further, thewhole layout scheme can be obtained.Aiming at layout design problem of the simplified international commercialcommunication satellite module, this paper researches the circle and rectanglepacking problem with the performance constraints, and proposes a divide-conquerco-evolutionary algorithm. The solution accuracy and computational efficiency of theproposed algorithm is better than those of other existing algorithms for the layoutoptimization design of the satellite module. Authors hope that the paper will be usefuland helpful for the solution of other similar layout problems.