The Study On The Parallel Heuristic Ant Colony Algorithm For Polyhedra Packing Problem

The container loading problem(CLP)has widely applied to various areas,such as logistics,multi-processor scheduling,resource allocation,cutting and packing,and so on.This paper focuses on the problem of loading polyhedron in a box container(CPLP).The problem might be described as follows: Packing several different-sized and different-shaped polyhedra into a given box container with fixed rectangle base,the objective is to minimize the height of the box container.CPLP is no doubt an NP-Hard problem,which cannot be solved within a polynomial time by a natural serial computer.Compared with other packing problems,it is more difficult to solve for CPLP,because of its high dimensional real solution space and a large amount of non-intersected calculation.So far,heuristic algorithm and evolution algorithm are feasible to solve CPLP,but literatures published are few and have respective restricted conditions(for example,only fitting to regular-shaped polyhedron,no rotating the polyhedron,computing the no-fit polyhedron).Scholars have been focused on how to improve the space utilization and calculation efficiency.This paper discusses the parallel heuristic ant colony algorithm for CPLP and the work is supported by Natural Hunan Province Science Foundation(Project: Study on the global cooperative optimization mechanism and approach for the 3D multi-shape Packing problem with static and dynamic mass balance,No.:2017JJ2250).Major content and innovations are as follow:1.An improved HAPE3 D algorithm is proposed for CPLP.(1)Besides gravitational potential energy,another two attractive force potential energy from two different directions are introduced to define the potential energy of the system;(2)“Plane Separation Theorem” is proposed to detect whether there is overlap area between two polyhedra.Concurrent GPU threads are used to calculate the optimal packing attitude of a polyhedron in parallel so that it takes less time to calculate the optimal packing pattern.Experiment results show that both the space utilization and calculation efficiency of the proposed IHAPE3 D are higher than those of existing algorithms.2.A parallel heuristic ant colony algorithm(IHAPE3D + ACA)is proposed for CPLP.A dynamic pheromone update strategy is designed by which it can avoid to strap into the local optimum for the iteration of IHAPE3 D + ACA;(2)the searching ability can be improved for a large scale CPLP problem and the computationalefficiency is improved by GPU multi-threading computation.Experimental results show that both the computational efficiency and space utilization of the proposed IHAPE3 D + ACA are higher than those of existing algorithms.By taking the CLP as the research background,this paper discusses on the three-dimension multi-shape polyhedron packing problem in depth.Based on the principle of minimum potential energy,IHAPE3 D is proposed to obtain a packing scheme.Then,by combining it with an improved ant colony algorithm,the optimal packing order is searched and the optimal solution can be obtained.Hopefully this study can be regarded as a periodical achievement in three-dimension packing problem and provide inspiration and approach for others in the future.