Font Size: a A A

A Self-adaptive Hybrid Genetic Algorithm For3D Bin Packing Problem

Posted on:2014-04-01Degree:MasterType:Thesis
Country:ChinaCandidate:S R YinFull Text:PDF
GTID:2268330401958921Subject:Computational Mathematics
Abstract/Summary:PDF Full Text Request
Three-dimensional bin packing problem (3DBPP) is a typical NP problem and plays animportant role in the logistics industry. With the increasing of the sale of the problems, itwould generate the time dimension disaster and could not be ideal to optimize the loading ofthe large scale packing problem if we applied the traditional optimization algorithm to solvethis kind of problems. In order to find an approximate optimal solution within a reasonabletime, some scholars began to study a variety of methods that is a combination of heuristicalgorithms and genetic algorithms, and achieved good results.Firstly, the historical background and the significance of the packing problem is describ-ed, and then the heuristic algorithms and genetic algorithms is also described in detail in thispaper. Secondly, on the basis of previous studies, a new hybrid genetic algorithm combinedheuristic algorithm with genetic algorithm is proposed to solve the problem. The self-adaptivegenetic algorithm is used to optimize the packing sequence and direction of the constraint seq-uence, and the heuristic algorithm is mainly used to reasonably arrange the packing locationof the box on the basis of known boxing sequence and direction constraint sequence. In theheuristic algorithm, the packing sequence is a permutation of the types of boxes; select onlyone type of box used to form a simple block, if no suitable simple block could be put into thecurrent layout space, the simple block selected each time must not only to be packed into thecurrent residual space, but also to be the most appropriate one. Last, A large number of experi-ments over the LN computational example have been done in order to verify the effectivenessof the algorithm, the experimental results show that the algorithm is an effective method tosolve the three-dimensional packing problem in terms of the space utilization.
Keywords/Search Tags:3D Bin Packing Problem, Heuristic Algorithm, Self-adaptive, Genetic Algorithm
PDF Full Text Request
Related items