Three dimensional container packing using constrained resource planning
Date
2003-08
Authors
Contributor
Advisor
Department
Instructor
Depositor
Speaker
Researcher
Consultant
Interviewer
Narrator
Transcriber
Annotator
Journal Title
Journal ISSN
Volume Title
Publisher
University of Hawaii at Manoa
Volume
Number/Issue
Starting Page
Ending Page
Alternative Title
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
Keywords
Citation
Extent
vii, 121 pages
Format
Geographic Location
Time Period
Related To
Theses for the degree of Master of Science (University of Hawaii at Manoa). Electrical Engineering; no. 3808
Related To (URI)
Table of Contents
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.
Rights Holder
Local Contexts
Collections
Email libraryada-l@lists.hawaii.edu if you need this content in ADA-compliant format.