Maximum Caving Degree Algorithm For Solving Cuboids Packing Problem

Packing Problem appears high frequency in the fields of machine making, feather fashion, shipbuilding, traffic conveyance, aviation and space flight, LSI design, and so on. Solving Packing Problem has significant sense in both scientific researches and manufacturing products. A typical Cuboids Packing Problem is the Container Loading Problem which is very common in ocean conveyance and railway freight, this problem has NP hard. Solving NP hard problem is a bottleneck for the computer science and technology nowadays .In recent years, investigations shows that for NP hard problems , there may not exist any algorithm that is both complete and rigorous and not too slow. So its solution methods are usually heuristic.Professor Huang Wenqi propose a quasi-human algorithm called Maximum Caving Degree Algorithm to solve the Cuboids Packing Problem. Maximum Caving Degree Algorithm has already been used to solve the Rectangles Packing Problem, and its effective in solving the Rectangles Packing Problem has been testified. Professor Huang generalize the Maximum Caving Degree Algorithm from planar to three dimensional. The author amply describe the inwardly origin of the algorithm, key definitions(includes caving degree, corner aero, corner occupying action),the steps of the algorithm to carry out, and actualize the algorithm in C language. Then the author propose some ameliorations with Professor Huang, the ameliorations include: (1)amelioration to the definition of caving degree; (2)bring in backtrack;(3) predigest the definition of corner aero. Experimental results demonstrate that the algorithm is quite effective in solving the problem.