Hybrid Genetic Algorithm For Multiple Constraints Colored Three-dimensional Packing Problem

As a typical NP-complete problem, three-dimensional packing problem has a long research history. And with a significant influence on national economy, it exists almost everywhere in life and production, especially in modern logistics industry. For logistics companies, both optimizing loading problem and improving utilization of cabinet volume or truck could reduce costs, thereby enhancing competitiveness of enterprises. Therefore, it is an important to study the issue of three-dimensional packing problem in modern logistics.From the angle of loading target, three-dimensional packing problem could be divided into bin loading problem, container loading problem and knapsack loading problem. As a vital study field, bin loading problem is generally researched to load all required specifications of the loaded cargo at the minimum containers. In this paper, we chose.bin loading problems as the main research object, and combined with the practical application, we put forward a multi-constraints colored three-dimensional packing problem. Multi-constraints colored three-dimensional packing problem is constrained by multi-constraints three-dimensional packing problem and colored three-dimensional packing problem. And there are a number of researches on the former problem to study goods packing, loading and unloading sequence, while the latter problem mainly centers on goods with mutually exclusive types or colors. Thus, Multi-constraint colored problem is an integration for the above two problems. From the background and significance of multi-constraint colored three-dimensional packing problem, in the paper, we deeply analyzed the problem and proposed a set of solutions from model development to hybrid genetic algorithm. Specifically, the solution included an abstraction of multi-constraint colored problem model, a design on the positioning boxing rules and an approximate optimal solution by using the overall optimizing ability of genetic algorithms. Thus, on the issue of subspace decomposition, we proposed a decomposition method based on the space optimization method. Namely, cabinet subspace was divided based on the utilization of objects coming into undivided space to the space. Furthermore, we further proposed a new data structure of improved ternary tree to represent such a divided space. In the data structure, the best consolidation strategy was used in subspace to merge.And it is proved a high quality of the solution method. Additionally, when designing genetic algorithms, we divided chromosomes into head and tail, representing boxes load order and display mode respectively. And genes of head and tail have different ways of crossover and mutation. Lastly, with the proposed algorithm, a set of boxing assistive software was developed. Moreover, test data was applied to test the merits of the algorithm, which proved to be effective to solve problem of multi-constraint colored three-dimensional packing.