Hybrid Immune Genetic Algorithm For Semi-online Three-Dimensional Packing Problems

The three-dimensional packing problem belongs to the class of combinatorial optimization problems with various practical applications,especially in logistics.In the process of logistics,packing is a key step.A reasonable packing plan can greatly improve the utilization of space,and efficiency,thus improve the level of automation.It can greatly reduce the cost and improve the competitiveness for an enterprise.As for emergency logistics,it can optimize the loading and distribution of emergency materials,and save life at utmost.Therefore,it is of great significance to study the three-dimensional packing problems.A lot of research has been carried out on the problem of 3D packing.However,the majority of studies in this area have focused on offline three-dimensional packing problems,and sequencing constraints have not been considered while many packing problems in reality must be packed in a certain order.Therefore,on the basis of previous researches,a hybrid immune genetic algorithm for semi-online packing problem was proposed to solve the problems in real life.The research status at home and abroad for three-dimensional packing problem is introduced firstly,and the packing problem is classified later.It also shows the general methods to solve the combinatorial optimization problem.Then the paper provides a new heuristic algorithm for semi-online packing problem,and the mathematical model is established.The simulation results show that a single heuristic algorithm is fast in calculation,but adaptability needs to be improved.Motivated by this,the hybrid immune genetic algorithm is proposed.First,spatial distribution of boxes is generated by immune genetic algorithm,and final solution can be obtained by heuristic algorithm.At last,adaptation,convergence and rapidity are tested by computer simulation and with a set of data.In the immune genetic algorithm,a reasonable and effective matrix coding form is used,and an effective genetic operator is designed to ensure the fast convergence of the algorithm.In the heuristic algorithm,contact rate is proposed to indicate the stability.The objective function takes both space utilization and stability into consideration,which improves the feasibility of the algorithm.In the end,adaptation and rapidity are tested again by a series of random data.Results show the semi-online packing problem can be solved well by the algorithm.With several trying for semi-online packing problem,the heuristic algorithm still exist some imperfection,but it provide a new method which is instructive to solve the three-dimensional packing problem.