Solving the Three-Dimensional Palet-Paking Problem Using Mixed 0 - 1 Model
- 1
Abstract
The distribution of Pallet Packing Problem is to load a set of distinct boxes with given dimensions on pallets or in con- tainers to maximize volume utilization. This problem is still in its early stages of research, but there is a high level of interest in developing effective models to solve this NP-hard problem to reduce the time, energy and other resources spent in packing pallets. In this paper, the three-dimensional pallet loading with mixed box sizes model has been developed. This loading model allows many boxes of various sizes to be placed onto the same pallet. The model also considers the number or proportion of each box size that can be loaded on a pallet. No restrictions are placed on the dimensions of the boxes, the pallets, or the number of different box sizes that can be considered. Therefore, the objective of this work is to determine how to most efficiently load a given pallet by maximizing the volume occupied by its load of boxes. Tests on several problems were implemented using OR library in order to show the validation of the proposed model. The results showed that the formulated mixed 0 - 1 models provide exact solutions for the pallet-packing problem. The computational time requirements of the developed model prevent its use in real-time palletizing applications. As microcomputer chip technology continues to evolve the lengthy computation time may prove to be less of a problem in real time applications.
- E. G. Jr. Coffman and P. W. Shor, “Average-Case Analysis of Cutting and Packing in Two-Dimensions,” European Journal of Operational Research, Vol. 44, No. 2, 1990, pp. 134-145. doi:10.1016/0377-2217(90)90349-G
- J. Verstichel, W. Vancroonenburg, W. Souffriau and G. V. Berghe, “A Mixed Integer Programming Approach to the Aircraft Weight and Balance Problem,” Procedia Social and Behavioral Sciences, No. 20, 2011, pp. 1051-1059.
- W. Q. Huang and K. He, “An Efficient Algorithm for Solving the Container Loading Problem,” 2007. http://mscmga.ms.ic.ac.uk/jeb/orlib/thpackinfo.html
- J. A. George and D. F. Robinson, “A Heuristic for Packing Boxes into a Container,” Computers and Operational Research, Vol. 7, 1980, pp. 147-156. doi:10.1016/0305-0548(80)90001-5
- C. H. Che, W. Huang, A. Lim and W. Zhu, “The Multiple Container Loading Cost Minimization Problem,” European Journal of Operational Re-search, Vol. 214, 2011, pp. 501-511. doi:10.1016/j.ejor.2011.04.017
- S. Martello, D. Pisinger and D. Vigo, “The Three-Dimensional Bin Packing Problem,” Operations Research, Informs, Vol. 48, No. 2, 2000, pp. 256-267. doi:10.1287/opre.48.2.256.12386
- T. Dereli and G. S. Das, “A Hybrid ‘Bee(s) Algorithm’ for Solving Container Loading Problems,” Applied Soft Computing, No. 11, 2011, pp. 2854-2862. doi:10.1016/j.asoc.2010.11.017
- J. Liu, Y. Yue, Z. Dong, C. Maple and M. Keech, “A Novel Hybrid Tabu Search Approach to Container Loading,” Computers & Operations Research, No. 38, 2011, pp. 797-807.
- H. Gehring, K. Menschner and M. Meyer, “A ComPuter-Based Heuristic for Packing Pooled Shipment Containers,” European Journal of Operational Research, Vol. 44, No. 2, 1990, pp. 277-289. doi:10.1016/0377-2217(90)90363-G
- C. P. Han, K. Knott and P. J. Egbelu, “A Heuristic Approach to the Three-Dimensional Cargo-Loading Problem,” International Journal of Production Research, Vol. 27, No. 5, 1989, pp. 757-774. doi:10.1080/00207548908942585
- H. J. Steudel, “Gene-rating Pallet Loading Patterns: A Special Case of the Two-Dimensional Cutting Stock Problem,” Management Science, Vol. 25, No. 10, 1979, pp. 997-1004. doi:10.1287/mnsc.25.10.997
- B. B. Mohanty, K. Mathur and N. J. Ivancic, “Value Considerations in Three-Dimensional Packing—A Heuristic Procedure Using the Fractional Knapsack Problem,” European Journal of Operational Research, Vol. 74, No. 1, 1994, pp. 143-151. doi:10.1016/0377-2217(94)90212-7