The Application Of Hybrid Genetic Algorithm In Rectangular Strip Packing Problem

Rectangular strip packing problem is a part of rectangular packing problem, which means discharging all rectangular parts to be ranked into a rectangular plate, which has a certain width and unlimited length. Make full use of raw materials, to achieve the highest possible panel utilization. RSPP has been proved to be NP-complete problem, unable to obtain global optimal solution in polynomial time. Analyzing the packing problem’s trends combined with its own characteristics and the research status at home and abroad. By improvements of the mathematical model of traditional RSPP, increased excess stock recovery cost under the premise of ensuring the utilization of raw materials. Minimize the cost of raw materials and excess stock recovery. Cutting process meets the straight cutting. Design a hybrid genetic algorithm with adaptive crossover and mutation operator. Heuristic rules to generate the initial population. Use adaptive crossover and mutation operator to adjust the population diversity. Decoding individuals generated, then integration operator to improve the results of packing. The population shift to the simulated annealing operation, avoidance algorithm full into the local optimal solution. Proved by experiment and simulation, the algorithm for solving large-scale RPSS is effective.