Heuristic Algorithms for Solving Two Dimensional Loading Problems

摘要

The loading problem involves the allocation of 'n' boxes, each having a specific length, width and height, to a pallet of specific dimensions. Much work has been done on solving the many special cases of this problem where all boxes are of the same rectangular size and/or with the restriction that the edge of the rectangles follow a 'Guillotine cut' from one edge of the pallet to the other; the two dimensional cuttings stock problem. However, the generalized problem of different sized boxes becomes very difficult to solve. A common problem for the U.S. Air Force is the transportation of equipment in a large number of boxes, each of different sizes. These boxes would be loaded onto pallets for subsequent placement on transport aircraft. Generating the methods and instructions for loading the pallets is routinely accomplished manually and relys heavily on the experience of the transportation personnel to determine loading patterns that will produce good pallet usage. Therefore, utilizing a computer to generate the loading procedure would be of considerable practical benefit in reducing loading time. This report presents several heuristric algorithms for solving large two dimensional loading problems. The objective of the algorithms is to maximize the ratio of area used to the total pallet area. The procedures employ dynamic programming and a stacking procedure for positioning boxes on the pallet.