The Research And Implement Of Multi-Constraints 3D Bin-Packing

Three dimension packing problem with multi-constraints is a NP-hard combinatorial optimization problem, which makes some goods be in a set of containers, and satisfies definite multi-constraints (such as orientation, weight, priority, packing-place and average-packing etc), and aims at maximum volume packing to improve the using rate of containers.Genetic Algorithm is applied to three dimension packing problems for its better global search performance and robust performance. GA to solve constrained optimization problem is searching the feasibility answers satisfied the constraint condition in the global genetic type space. The chromosome unsatisfied constraint condition is called lethal chromosome.With the population of Genetic Algorithm evolving, due to complex multi-constraints of three dimension packing problems, lethal chromosomes occur in a high rate. Because of the packing problems with rigorous constraints, the number of lethal chromosomes become so large in population, The more the number of lethal chromosomes are in population, the worse the searching performance is. The algorithm will stop on some occasions.So Penalty function with GA is utilized to solve the packing problem. Penalty function changes the multi-constraints into the single-constraint. This method is simple and direct, but all constraints can not be penalized and feasible region is narrowed. Actually, feasibility answers could be found at the boundary of feasible region. However, the inflexible constraints may eliminate many better packing plans, even the best packing plan.Aiming at the shortcoming of conventional penalty function, the constraints are fuzzed by fuzzy theory, which is called fuzzy penalty function. This method not only can indicate whether a point is in feasible region, but also can fuzz the point which isn't in feasible region according to the distance from feasible region. There isn't clear boundary between feasible region and unfeasible region, incomplete feasibility answers are evaluated by the extent of violating constraints, if this extent is light, incomplete feasibility answers can be known as feasibility answers. This method enlarge the searching extent, utilize the some lethal chromosomes within excellent genes, prevent effective genes from losing, reserve some incomplete feasibility answers, and reduce the number of lethal chromosomes, extend feasible region, and attain objective of global searching for the superior bin-packing combination. The example shows that there is a better performance in 3D bin-packing.