A Recursion Heuristic Algorithm For Cylinder Objects Loading Problem

The loading problem is about how to fill a number of small objects into a large space and maximize the space utilization in the most optimized way. Originally it is the combination of the three-dimensional packing problem and the knapsack problem. The loading problem is a complicated combinatorial optimization problem, and refers to knowledge across different subjects and domains. In practice the problem widely exists in train load, truck load, ship load, container load and etc. Improving the quality and reliability of container load and transportation is very important to the solution of this problem. The modern research and design about container load system is focusing on computer-aid methods.The three-dimensional C&P problem can be classified into categories of Bin Packing Problem, Container Loading Problem and Pallet loading problem. Practical concerns are about direction, endurance and stability. Since the 3-D box layout is a NP-complete problem, while the sizes and amount of boxes increase and the solution space explodes, the computation becomes highly inefficient. Most of the related literatures are about how to put small boxes into a big box, but few associate the dimension design of small boxes to large box load.In pallet load, the shapes of objects are always rectangle and the edges are always parallel to the edges of the pallet; no overlap between any objects; and no object can exceed the height limit. The goal is to get the maximized space utilization. For manufacturer tray loading, most of the literatures are assuming that all the objects are placed along the same direction, so that they can be put by layers, and the design of each layer is equivalent to a 2D-layout algorithm. In fact the problem is converted to a 2D rectangular packing problem. Assuming that all the objects are of the same size and the constraints are relatively simple so a high degree of optimization can be achieved. If a wholesaler loads objects are of different sizes, the problem is much more difficult to deal with. Based on the requirements of current container loading problem and the complete understanding of all types of loading problems, this paper describes an approach to the loading problem of cylindrical objects. Firstly we put the identical cylindrical objects into small rectangular box. Then add the small boxes into the pallet stratified. This paper presents an efficient recursive heuristic algorithm which is simple and easy loading.The first step is about packing cylindrical objects. There are many approaches to pack the same sized circular objects. Usually the recursive shear-cut algorithm suits for punching problem. Since the loading problem is different from the shear cutting problem in industrial production, the traditional method of shear-cut, which is good at handling some particular cases, does not apply naturally for the loading problem. Based on the above analysis we use circular heuristic regular arrangements in which the angle between neighboring rows is constant. The reason for this is that regular arrangements are easy to produce using either manual or automated methods. For each possible box size, the approach uses regular arrangements to determine the layout of the cylinder objects in the box, such that the objects number is as large as possible.The second step is to load small cubic boxes onto the pallet. After the first step we should consider that how to maximum the loading utilization when packing these identical cubic boxes into a large container stratified. This problem is similar to optimal packing of identical rectangle. That is putting a number of identical rectangle blanks into the sheet. The identical rectangle packing problem usually uses multi-stage cutting pattern which can be recognized as putting a strip horizontal or vertical along one border of the area which was already packed. In this paper we use dynamic programming algorithm to achieve the identical rectangle packing problem and control the cost by setting the parameters. By this way we find the optimal multi-stage cutting pattern and meanwhile it's a more simple and easy loading process. Then we develop a practical cylindrical objects containing loading system. Design the basic functional modules after completion of the algorithm. Then we develop the optimization layout system based on heuristic recursive algorithm. Through a large number of tests, we prove the feasibility of the algorithm by the utilization of loading layout and consuming time. By comparing the maximum stage number with the minimum, we conclude that the algorithm can simplify the process of loading and reduce the cost in practical application. The computational results show that using this algorithm can get a better result with considering utilization and loading complexity.Finally we conclud the research of cylindrical loading and put forward the orientation of the future work.