Hybrid Heuristic Algorithm For 2D Strip Packing Problem

Packing problem is a classical combinatorial optimization problem,which is widely used in manufacturing,logistics,computer and other industries.Its goal is to improve the utilization rate of resources and reduce the cost.The theoretical research of packing problem has very important practical significance for the development of the above industries.In this paper,we mainly study the 2D packing problem(2DSPP).The content of2 DSPP is to give a group of rectangular objects and rectangular plates with fixed width and infinite height.The purpose of 2DSPP is to minimize the height of the rectangular plates used by them.The main contents of this paper are as follows:(1)The scoring rule of skyline algorithm is improved,and the scoring rule Scorer? is proposed.Scorer? can select more suitable rectangular objects to place,which can effectively reduce the waste of space and improve the utilization rate of space.(2)A new skyline evaluation function Scorer? is constructed by using dqn algorithm.Scorer? refines the selection rules of rectangular objects and achieves the purpose of reducing space waste.At the same time,scorer I and Scorer? are used as the scoring rules of skyline,that is,when two or more rectangular objects are equal when using Scorer?,the algorithm can obtain better results.(3)The simple random algorithm(SRA)is improved.The greedy search(GS)phase is added to the SRA local search.The greedy search pair uses Scorer? Compared with other initial solutions based on perimeter,area,width and height,the optimal initial sequence is selected as the initial rectangular permutation sequence of heuristic algorithm.Compared with the single rectangular sequence sorted according to fixed rules,Scorer? can get better solutions,and its heuristic algorithm can get excellent solutions in different size problems,which improves the heuristic algorithm The universality of law.Combining Scorer? and SRA algorithm based on reinforcement learning,RSRA algorithm is proposed.(4)The RSRA algorithm is tested and analyzed on eight public datasets,and the experimental results show that the rsra algorithm is effective on the eight public datasets ave.Gap% 86%,45.16%,30.89% and 20.56% respectively.At the same time,compared with the latest algorithms Iam and spsal in 2020 on four sets of data sets,the experiments show that the best results are obtained on the four sets of data sets.(5)Based on the theory of 2DSPP,the algorithm design and software development are carried out for the specific problem of the installation position of the equipment under the rail vehicle.The algorithm is designed to meet the requirements of the installation of the equipment at the bottom of the rail vehicle,including the center of gravity balance,maintenance space,wiring space,equipment installation direction,fixed equipment and priority equipment.The gradient descent algorithm and cycle algorithm are used to implement the Y and X direction equipment installation algorithm,and the components are completed The development of management module,placement calculation module and data dictionary module.