Research And Software Implementation Of A New Algorithm For Container Loading

The target of "cutting and packing" is seeking an effective cutting and packing method, maximizing raw material or spatial utilization. Because the optimization of the layout can save raw material, use space abundantly, the profits of enterprise can be increased by the high utilization. The field that the problem applied is very wide, the most concrete application is the using of raw material area and space, such as the cutting of steel plate, glass and timber, the loading of the pallet and container.Container loading is the three-dimensional problem in "cutting and packing" problems. It is combined optimization with complex constraint condition. It belongs to NP complete problem in theory, so it's hard to solve in practical problems. This kind of problem has a few study reports in domestic and overseas, most of them base on heuristics approximation algorithms.On the research of the loading algorithm in this paper, the main idea is heightened the utilization of the container space. Firstly the method of Fan's was digested and revised. A descriptive and intersected method of remainder space was inherited from Fan's. Secondly, a new method was redesigned that based on Fan's original heuristic method. The heuristic method, that the spatial utilization was decreased by the simpler strategy which the items were chose from the bigger to the smaller, is improved. A new heuristic way is proposed, which decomposes the container into a number of layers and combines and backtracks different items in the layer. In order to avoid the combination of all items, the method that combined method integrating with the heuristic method is used. Under the control of time, a constrained combination method is used to enhance the spatial utilization. This is the key of the research. Thirdly, because the theory of the division of remainder space and layer in the container is cutting, the remainder space is interrelated in fact. So, a combination algorithm of remainder space is implemented to enhance the spatial utilization of container loading in procedure of the container loading.The software base on the algorithm of this paper is successfiil running. It can solve concrete container loading problem.