Please use this identifier to cite or link to this item: http://hdl.handle.net/10125/7011

Three dimensional container packing using constrained resource planning

File Description SizeFormat 
uhm_ms_3808_uh.pdfVersion for UH users44.4 MBAdobe PDFView/Open
uhm_ms_3808_r.pdfVersion for non-UH users. Copying/Printing is not permitted44.4 MBAdobe PDFView/Open

Item Summary

Title: Three dimensional container packing using constrained resource planning
Authors: Shnidman, Daniel
Advisor: Yun, David Y Y
Issue Date: Aug 2003
Publisher: University of Hawaii at Manoa
Abstract: In this thesis, the Constrained Resource Planning (CRP) model is employed to solve Three-Dimensional (3D) packing problems. An efficient packing program 3dPack has been implemented which could be used to assist human packing in the parcel industries. Viewing 3D packing as a constraint satisfaction problem, 3dPack uses resource management and multiple domain-independent heuristics to navigate the immense search space and reach an optimum container fill percentage in near-linear time. Three specific problems have been investigated and tackled by using the 3dPack program. The three problems are Bin Packing, Loading dock Packing, and Perfect Packing. The Bin Packing problem is to pack a finite number of given package into as few bins as possible. The Loading dock Packing problem is to keep a high container-fill percentage as the packages are supplied, packed into the containers, and sent out at different points of time. The Perfect Packing problem, as the most difficult one, has only one container and multiple rectangular packages. The sum of package volumes equals the volume of the container. The objective of Perfect Packing is to pack all packages into the container leaving no empty space. These three problems were selected to test 3dPack on different aspects of packing including packing solution performance, optimality, scalability and completeness. In Experimental results on Bin packing problems, 3dPack outperforms the leading Guided Local Search and Tabu Search methods by an average of 14.3% and 22.6% fewer bins respectively. For the Loading dock problem, a packing efficiency of 98.8% is achieved with a standard deviation of 0.21%. For the Perfect Packing problem, all the 3D examples (over 50 packages) were consistently solved in near-linear time. The combined results from the three problems show the 3dPack algorithm to be versatile, scalable, and consistent. Taken together, results from all three problems support the overall performance excellence in terms of (1) high container fill percentage, (2) near-linear run-time, (3) scalability, and (4) consistency.
Description: vii, 121 leaves
URI/DOI: http://hdl.handle.net/10125/7011
Rights: All UHM dissertations and theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission from the copyright owner.
Appears in Collections:M.S. - Electrical Engineering



Items in ScholarSpace are protected by copyright, with all rights reserved, unless otherwise indicated.