Packing in two and three dimensions
Loading...
Authors
Martins, Gustavo H. A.
Subjects
Advisors
Dell, Robert F.
Date of Issue
2003-06
Date
June 2003
Publisher
Language
Abstract
This dissertation investigates Multidimensional Packing Problems (MD-PPs): the Pallet Loading Problem (PLP), the Multidimensional Knapsack Problem (MD-KP), and the Multidimensional Bin Packing Problem (MD-BPP). In these problems, there is a set of items, with rectangular dimensions, and a set of large containers, or bins, also with rectangular dimensions. Items cannot overlap (share the same region in space), and, when packed, must be completely located within the bin. We develop new theory for PLP, and apply it to the construction of new bounds, heuristics, and an exact algorithm. The bounds verify that the heuristics optimally solve 99.999% of PLP instances with up to 100 items; in the instances that the heuristics fail to solve optimally, their best solution differs from the optimum by only one item. Using our new PLP theory, we implement algorithms to solve orthogonal non-guillotine MD-KP instances and are the first to obtain exact solutions for some instances from the literature. Using these MD-KP algorithms, we develop the first exact algorithm for the orthogonal nonguillotine MD-BPP and are the first to obtain exact solutions to several instances from the literature.
Type
Thesis
Description
Series/Report No
Department
Operations Research
Organization
Identifiers
NPS Report Number
Sponsors
Funding
Format
xvi, 158 p. : ill. ; 28 cm.
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.