The Research Of Two Stage Optimization Algorithm On Multi-Shaped Objects Packing Problem With Static Imbalance Constraints

The packing problem of a satellite cabin, ie, placing the given instruments and payloads on bearing plates of the satellite module in the best way to reduce the space in the most degree and gain a feasible and compact layout solution in condition of performance constraints. When solving the problem by existed algorithms, objects are always simplified to cuboids and cylinders, and transform the packing problem on each bearing board surfaces to rectangles, circles, and the mixture of rectangles and circles packing problem. While the simplification might reduce the quality of solution.So in favor of National Natural Science Foundation, this paper studies the packing problem of multi-shaped objects with static imbalance constraints. The main idea is that: based on the knowledge of Geometry, Mathematics, Computer Graphics,Operational Research and so on, instruments and equipment are simplified to the cylinder, half-cylinder, cuboid, triangular prism, trapezoid column, and the mixture of the cuboid and half-cylinder; and transform the packing problem on the bearing boards surface to multi-shaped objects packing problem of circle, half-circle,rectangle, triangle, trapezoid, and the mixture of rectangle and half-circle. Then,research the feasible and efficient solution. Main work and innovation are as follow:1. Propose a rough packing method for multi-shaped packing problem based on the proposed improved dynamic adjustment strategy. Transform multi-shaped objects to rectangles to pack. It is combined with the quasi-physical and quasi-human algorithm to get the best solution. Experiments show that convergence speed of the proposed method in iteration is fast, especially for large scale problem.2. Propose an accurate adjustment method for multi-shaped packing with static imbalance constraints based on the moving strategy. For the initial layout solution,move objects using the method of judging and calculating the overlapping proposed by this paper, to obtain a compact solution. Experiences show that the computational efficiency is better and layout solution of multiple shaped objects is more compact.This paper studies the multi-shaped objects packing problem, proposes the rough packing and accurate adjustment method, and uses cases to verify effect. Experiments show that the results are better than existed algorithms. Hope it could act as a staged achievement of 3D multi-shaped packing problem, and a reference for 2D ones.