Research On Solving 3D Packing Problem Based On Hybrid Heuristic Algorithm

With the development of economic globalization,the logistics industry has experienced rapid growth in recent years.Simultaneously,the logistics optimization which mainly focus on reducing costs and improving benefits has also received widespread attention from the industry and academia.The packing problem is a classic problem in logistics optimization and has great research value in improving the distribution efficiency,promoting the utilization rate of loading space,hoisting the efficiency of logistics transportation,less the transportation cost and enhancing the peer competitiveness in logistics enterprises.Due to the extensibility,the three-dimensional packing problem is no longer limited to the field of logistics.It has been widely used in vehicle routing research,applied on economics research,architecture research,civil engineering research and many other subject areas.Because of the great application fields of container problem,analysing researches on different sub-problems show that the application of heuristic algorithm is most applied since 2000.There are five optimization model algorithm,tabu search algorithm,nonlinear algorithm and chemical reaction optimization algorithm to solve the two-dimensional packing problem.Traditional heuristic algorithms(such as genetic algorithm,simulated annealing algorithm)are used to solve three-dimensional packing problems.However,the traditional heuristic algorithm has some disadvantages,such as large computation and high computational complexity.As a new heuristic algorithm,the Chemical Reaction Optimization(CRO)has advantages of both genetic algorithm and simulated annealing algorithm: fast convergence and effectiveness.However,this algorithm is only applied to two-dimensional packing problem at present.Based on the limitation and advantage of chemical reaction optimization algorithm,this thesis proposes a hybrid heuristic algorithm for solving three-dimensional packing problem,which mainly includes hybrid chemical reaction optimization algorithm and hybrid recursive algorithm.The main contributions of this thesis are as follows:First,Minimizing the number of packing problems,this thesis put forward the hybrid chemical reaction optimization algorithm.It realizes the overall framework of Chemical Reaction Optimization algorithm(CRO)and adapt parameters to thethree-dimensional packing problem on potential energy,population number,data set number ratio,synthesis rate and decomposition rate.Based on the publicly provided random algorithm to generate the actual test data(320 instances of 8 classes),we abstract all possible results on test data into an unknown potential energy surfaces,and find that the lowest potential energy point after running the algorithm which is the best combination of adaptability.The validity of the algorithm is proved by the comparison with the data of existing papers.Second,in view of the same size packing problem,this thesis puts forward hybrid recursive algorithm.On the one hand,the thesis build blocks through natural composition and splicing,on the other hand,the space is effectively cut and recursion is used to solve the problem.In order to verify the effectiveness of the algorithm,a comparison experiment was conducted based on the data of the existing papers.It was found that the algorithm could further improve the filling rate of unit packing and solve the problem of weak local search ability in CRO to some extent.To sum up,this thesis proposes a hybrid reaction optimization algorithm and a hybrid recursive algorithm for the specific problems of three-dimensional packing.The hybrid chemical reaction optimization algorithm further optimizes and minimizes the number of packing problem.Based on the public data set(the proposed 8-class320 instance data),the simulation experiment shows that the algorithm in this thesis is superior to the existing similar algorithm.Secondly,inspired by the idea of combining blocks and space cutting,the hybrid recursive algorithm is implemented,and experiments are carried out on the existing data set I and data set II.Through the result analysis,it can be seen that the hybrid recursive algorithm has a great competitive advantage in the same size packing problem.