Research On Three-dimensional Offline Packing Problem Based On Hybrid Genetic Algorithm

The packing problem can be summarized as placing a specified number of goods with different physical characteristics(such as weight,volume,etc.)into a specified box.As a combination optimization problem,the packing problem exists widely in production and life,and is the most common in the logistics transportation industry.With the development of economy and the increase of trade,China’s freight volume continues to grow,and the domestic demand for logistics is gradually increasing.But China’s logistics industry still remains at the stage of manual loading and disordered transportation,resulting in high logistics costs,bringing about the waste of resources and the problem of insufficient competitiveness of enterprises.Among them,the packing problem has become a key issue to reduce logistics transportation costs and reduce waste of logistics resources.However,at present,the research of scholars focuses on solving the problem of loading a single box,and does not conduct research on the problem that a batch of goods needs multiple boxes to be loaded in actual production.Therefore,this paper studies the three-dimensional offline packing problem that requires multiple boxes to complete loading in actual production,and designs a hybrid genetic algorithm to solve this problem.Firstly,on the basis of introducing the basic theory of the packing problem and the type of problem,this paper establishes a mathematical model of the three-dimensional offline packing problem with the goal of maximizing space utilization.Unlike the common single-box packing problem that maximizes the space utilization of a single box,in order to better fit the actual packing problem,the goods studied in this article need to be all packed into a batch of boxes of the same type and unlimited number.At the same time,in addition to the common constraints,special constraints such as rotation constraints and stability constraints are also introduced.Then,for the three-dimensional offline packing problem,a hybrid genetic algorithm combining genetic algorithm,tabu search algorithm and heuristic algorithm is designed.In order to make the algorithm solution contain the information of the packing order and the rotation state of the box in the packing scheme,a two-stage random number encoding method and decoding method based on random keys are designed,and correspondingly designed a cross-operation method based on partial random keys and uniform crossover;in order to convert the solution found by the optimization algorithm to the actual boxing scheme and improve the utilization of box space,this paper has designed a heuristic loading algorithm with the positioning rule using the lower left corner,minimum space selection rules,remaining space division and merge rules;after analyzing common selection operations,choose to use the roulette method in the early stage to strengthen the global search ability,and later use the optimal preservation strategy to speed up the convergence;In order to make up for the shortcomings of the genetic algorithm’s weak local search ability and slow convergence speed,the tabu search algorithm is used as a mutation operation in the genetic algorithm,and the solution in the offspring is used as the initial solution of the tabu search algorithm.Finally,this paper tests the proposed algorithm on 6 sets of weak heterogeneous and strong heterogeneous data in the BR data set,and compares it with genetic algorithm,genetic simulated annealing algorithm,and layered heuristic algorithm.The test results prove that this paper The proposed algorithm can reduce the use of boxes and improve the space utilization rate;at the same time,using two sets of logistics transportation company data for further testing,the test results show that the space utilization rate of the car has reached more than 80%,verifying the model and algorithm proposed in this article For effectiveness.