An Ant Colony Algorithm For The Rectangle Packing Problem

Computer Aided Nesting(CAN) is one of the widely used computer aided technique, which is used to instruct industries to deal with the cutting stock problem in order to achieve the objectives of saving raw material and reducing the cost of product.The cutting stock problem exists in many industries of the national economy, in which the two-dimension cutting stock problem is applied widely. The rectangle packing problem is the base of the two-dimension cutting stock problem, so doing the research on it is a significant issue to find out the optimal layout of rectangular blanks. We consider problems requiring to allocate a set of rectangular items to larger rectangular standardized units by minimizing the waste. In two-dimensional bin packing problems these units are finite rectangles, and the objective is to pack all the items into the minimum number of units, while in two-dimensional strip packing problems there is a single standardized unit of given width, and the objective is to pack all the items within the minimum height. Scholars in and abroad have done extensive research on this problem and proposed a variety of algorithms such as: linear programming algorithm, genetic algorithm, simulated annealing algorithm.In recently, since the ant colony algorithm's autocatalytic, positive feedback, parallel mechanism and the strong robustness, it has become a widely used meta-heuristic algorithm. In the work presented here, we used an ant colony algorithm to solve the strip packing problem which is NP-hard. In this paper, the research contained:(1)To solve the problem, a new layout scheme generation algorithm is presented which is based on the minimum length of waste criteria. This method can effectively improve the utilization of materials.(2)Establish the Ant Colony algorithm model of the strip packing problem, present the appropriate definition of the construction plans, pheromone and heuristic information, and path construction and pheromone update rules. Finally, design a suitable algorithm flow.(3)Analyzing the different parameters of ant colony algorithm, obtain the appropriate parameters to solve the problem.(4)After we get the ant colony algorithm for the rectangular strip packing problem, add some procedure to enable them to handle the rectangular bin packing problem.(5)Finally, designing and developing the rectangle packing system. The presented algorithm in this paper is tested by using a large number of experiments, and the results are compared with our team literatures as well as commercial software, the results show that the algorithm presented in this paper can lead to high material utilization. In a word, the rectangle packing algorithm presented in this paper is efficient.