Solving the Three-Dimensional Palet-Paking Problem Using Mixed 0 - 1 Model

Adel Mohammed Al-Shayea

.

DOI: 10.4236/jssm.2011.44059                

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.

Keywords

Pallet, Packing Problem, Optimization, Mixed 0 - 1 Models, 3-D Pallet Loading

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	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
[2]	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.
[3]	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
[4]	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
[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
[6]	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
[7]	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
[8]	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.
[9]	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
[10]	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
[11]	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
[12]	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
[13]	W. Kocjan and K. Holmstr?m, “Computing Stable Loads for Pallets,” European Journal of Operational Research, Vol. 207, No. 2, 2010, pp. 980-985. doi:10.1016/j.ejor.2010.05.005
[14]	L. Junqueira, R. Morabito and D. S. Yamashita, “Three- Dimensional Container Loading Models with Cargo Stability and Load Bearing Constraints,” Computers & Operations Research, Vol. 39, No. 3, 2012, pp. 74-85. doi:10.1016/j.ejor.2010.05.005
[15]	J. Terno, G. Scheithauer, U. Sommerwei? and J. Riehme, “An Efficient Approach for the Multi-Pallet Loading Problem,” Institute for Numerical Ma-thematics, Technical University Dresden Mommsenstr, Dresden, Vol. 13, 1997.
[16]	E. E. Bischoff and M. S. W. Ratcliff, “Is-sues in the Development of Approaches to Container Loading,” Omega Institute, Vol. 23, No. 4, 1995, pp. 377-390. doi:10.1016/0305-0483(95)00015-G
[17]	P. B. Ballew, “The Distributor’s Three-Dimensional Pallet-Packing Problem: A Mathematical Formulation and Heuristic Solution Approach,” MS Thesis, Graduate School of Engineering, Air Force Institute of Technology (AU), Wright Patterson AFB OH, 2000.
[18]	C. S. Chen, S. M. Lee and Q. S. Shen, “An Analytical Model for Container Loading Problem,” European Journal of Operational Research, Vol. 80, No. 1, 1995, pp. 68-76. doi:10.1016/0377-2217(94)00002-T
[19]	R. G. Askin, and R. S. Charles, “Modeling and Analysis of Manufacturing Systems,” John Wiley and Sons Inc., New York, 1993, pp. 320-321.