Skip to main content

Full text of "DTIC ADA378300: The Distributor's Three-Dimensional Pallet-Packing Problem: A Mathematical Formulation and Heuristic Solution Approach"

See other formats


r 



THE DISTRIBUTOR’S THREE-DIMENSIONAL PALLET¬ 
PACKING PROBLEM: A MATHEMATICAL FORMULATION 
AND HEURISTIC SOLUTION APPROACH 


THESIS 


Brian P. Ballew, Second Lieutenant, USAF 
AFIT/GOR/EN S/00M-02 

DEPARTMENT OF THE AIR FORCE 
AIR UNIVERSITY 

AIR FORCE INSTITUTE QF TECHNOLOGY 


Wright-Patterson Air Force Base, Ohio 


APPROVED FOR PUBLIC RELEASE; DISTRIBUTION UNLIMITED. 


JDTIG QUALITY QJSPECTSSD 4 


20000613 087 



REPORT DOCUMENTATION PAGE 


Form Approved 
OMB No. 074-0188 


Public reporting burden for this collection of information is estimated to average 1 hour per response, including the time for reviewing 
instructions, searching existing data sources, gathering and maintaining the data needed, and completing and reviewing the collection of 
information. Send comments regarding this burden estimate or any other aspect of the collection of information, including suggestions for 
reducing this burden to Washington Headquarters Services, Directorate for Information Operations and Reports, 1215 Jefferson Davis Highway, 
Suite 1204, Arlington, VA 22202-4302, and to the Office of Management and Budget, Paperwork Reduction Project (0704-0188), 
Washington, DC 20503 


1. AGENCY USE ONLY (Leave blank) 2. REPORT DATE 3. REPORT TYPE AND DATES COVERED 

March 2000 Master’s Thesis 


4. TITLE AND SUBTITLE 

THE DISTRIBUTOR’S THREE-DIMENSIONAL PALLET-PACKING 
PROBLEM: A MATHEMATICAL FORMULATION AND HEURISTIC 
SOLUTION APPROACH 


6. AUTHOR(S) 


FUNDING NUMBERS 


Brian P. Ballew, Second Lieutenant, USAF 


7. PERFORMING ORGANIZATION NAMES(S) AND ADDRESS(S) 

Air Force Institute of Technology 

Graduate School of Engineering and Management (AFIT/EN) 
2950 P Street, Building 640 
WPAFB OH 45433-7765 


9. SPONSORING / MONITORING AGENCY NAME(S) AND ADDRESS(ES) 

Dayton Area Graduate Studies Institute 
Attn: Dr. Frank Moore 
3155 Research Blvd, Suite 205 
_Kettering, OH 45420 (937)781-4000 


11. SUPPLEMENTARY NOTES 


8. PERFORMING ORGANIZATION 
REPORT NUMBER 

AFIT/GOR/EN S/00M-02 


10. SPONSORING / MONITORING 
AGENCY REPORT NUMBER 


JAMES T. MOORE, Lt Col, USAF (RET). AFIT/ENS e-mail: james.moore@afit.af.mil Phone: (937) 255-6565x4337 


12a. DISTRIBUTION / AVAILABILITY STATEMENT 12b. DISTRIBUTION CODE 

APPROVED FOR PUBLIC RELEASE; DISTRIBUTION UNLIMITED. 


ABSTRACT (Maximum 200 Words) 

It is through practice and experience Air Force loadmasters are able to pack the Air Force standard HCU-6/E (463L) pallets 
efficiently. Although the loadmasters perform their jobs exceptionally well, the Air Force is in search of a model that will more 
efficiently pack the pallets. 

We have developed a mathematical formulation of the three-dimensional pallet-packing problem which min i m izes the 
amount of unused space on a pallet. The formulation ensures each box is packed with the correct volume and dimensions, and 
ensures the volume of all the boxes packed is less than the available pallet volume. Additionally, the formulation ensures that each 
box has a foundation on which to be placed and allows, at most, one box to be placed in each location on the pallet. 

The three-dimensional pallet-packing problem is a NP-hard problem. Thus, for large problems, the optimal solution can not 
be found in a reasonable amount of time. Therefore a heuristic solution approach is required to solve these large problems. This 
research observes the performance of a genetic algorithm on the three-dimensional pallet-packing problem using single-point 


crossover. 


14. SUBJECT TERMS 

Three-dimensional pallet-packing, packing problems, pallet-loading problems, 
distributor’s pallet-packing problem, heuristics, genetic algorithms 


15. NUMBER OF PAGES 
111 


16. PRICE CODE 


17. SECURITY CLASSIFICATION 18. SECURITY CLASSIFICATION 19. SECURITY CLASSIFICATION 20. LIMITATION OF ABSTRACT 
OF REPORT OF THIS PAGE OF ABSTRACT 

UNCLASSIFIED UNCLASSIFIED UNCLASSIFIED UNC _ 


NSN 7540-01-280-5500 Standard Form 298 (Rev. 2-89) 

Prescribed by ANSI Std. Z39-18 
298-102 




















The views expressed in this thesis are those of the author and do not reflect the official 
policy or position of the United States Air Force, Department of Defense, or the U. S. 
Government. 


AFIT/GOR/EN S/00M-02 


THE DISTRIBUTOR’S THREE-DIMENSIONAL PALLET-PACKING PROBLEM: A 
MATHEMATICAL FORMULATION AND HEURISTIC SOLUTION APPROACH 

THESIS 


Presented to the Faculty 
Department of Operational Sciences 
Graduate School of Engineering and Management 
Air Force Institute of Technology 
Air University 

Air Education and Training Command 
In Partial Fulfillment of the Requirements for the 
Degree of Master of Science 


Brian P. Ballew, B.S. 
Second Lieutenant, USAF 

March 2000 


APPROVED FOR PUBLIC RELEASE; DISTRIBUTION UNLIMITED. 


AFIT/GOR/ENS/00M-02 


THESIS APPROVAL 


Student : Brian P. Ballew, Second Lieutenant, USAF Class : GOR-OOM 

Title : The Distributor’s Three-Dimensional Pallet-Packing Problem: A Mathematical 
Formulation and Heuristic Solution Approach 

Defense Date: 02 March 2000 


Committee: 

Name/Title/Department 

Signature 

Advisor 

James Moore, Ph. D. 

Associate Professor 

Department of Operational Sciences 


Reader 

Raymond Hill, Major, USAF 

Assistant Professor 

Department of Operational Sciences 


Reader 

Gregory McIntyre, Lt. Colonel, USAF 
Assistant Professor 

Department of Operational Sciences 



Acknowledgements 


First, I would like to thank my thesis advisor, Dr. Moore, for his support and 
guidance throughout this thesis effort. I would also like to thank one of my readers, 
Major Hill, for his insight on the problem and his help with the establishment of a 
sponsor. I would also like to thank Lt Col McIntyre for his help with GENESIS and 
genetic algorithms. 

My family and my girlfriend, Betsy, deserve a lot of thanks for putting up with 
me during these trying months and supporting me throughout the thesis effort. My 
parents deserve extra thanks for teaching me the commitment and discipline needed to 
complete this program. 

Lastly, I would like to thank my classmates for all of their help throughout the 
program and the good times. 


11 


Table of Contents 


Page 


Acknowledgements.ii 

Table of Contents.iii 

List of Figures.vi 

List of Tables.vii 

Abstract.viii 

Chapter 1 - Introduction.1-1 

1.1 Background.1-1 

1.2 Three-Dimensional Pallet-Packing.1-4 

1.3 Statement of the Problem.1-6 

1.4 Restrictions and Assumptions.1-6 

1.5 Overview.1-8 

Chapter 2 - Literature Review.2-1 

2.1 Introduction.2-1 

2.2 Three-Dimensional Pallet-Packing Problem.2-2 

2.3 Previously Contracted Efforts.2-8 

2.4 Commercial Packing Software.2-10 

2.5 Heuristics.2-12 

2.5.1 Greedy Heuristic.2-12 

2.5.2 Simulated Annealing.2-13 

2.5.3 Genetic Algorithms.2-14 

2.6 GENESIS.2-19 


ill 
























2.7 Summary.2-20 

Chapter 3 - Results.3-1 

3.1 Mathematical F cumulation.3-1 

3.2 Results from LINGO.3-7 

3.3 Results from GENESIS.3-9 

3.4 Summary.3-14 

Chapter 4 - Conclusions and Recommendations.4-1 

4.1 Introduction.4-1 

4.2 Research Results.4-1 

4.3 Recommendations for Future Research.4-3 

4.4 Final Thoughts.4-4 

Appendix A - Annotated Bibliography.A-l 

Appendix B - LINGO Formulation.B-l 

B.l LINGO Formulation...B-l 

B.2 Model Initialization and Objective Function.B-2 

B.3 First and Second Constraints.B-3 

B.4 Third and Fourth Constraints.B-4 

B.5 Constraint Five.B-5 

B.6 End of Program.B-6 

B.7 Results when Boxes One and Three are Packed.B-7 

B. 8 Results when Boxes Two and Three are Packed.B-8 

Appendix C - Genetic Algorithm Evaluation Function.C-l 

C. l Description of Evaluation Function and Variables used in Program.C-l 

iv 



























C.2 Function Preventing Negative Penalties 
C.3 Initialization of Variables. 


C-3 


C-4 

C.4 Determine Whether Each Boxes Length, Width, and Height are the Same.C-5 


C.5 Convert Character String to Binary String.C-6 

C.6 First Feasibility Check.C-6 

C.7 Second Feasibility Check.C-7 

C.8 Third Feasibility Check.C-7 

C.9 Fourth Feasibility Check.C-8 

C.10 Fifth Feasibility Check.C-9 

C. 11 Sixth Feasibility Check.C-10 

C. 12 Objective Function Value.C-20 

Appendix D - Results of Genetic Algorithm on Test Problems.D-l 

D. l Introduction.D-l 

D.2 Results of Test Problem One.D-l 

D.3 Results of Test Problem Two.D-2 

D.4 Results of Test Problem Three.D-3 

Bibliography.BIB-1 

Vita.V-l 


v 



















List of Figures 


Figure Page 

2-1 Single-point Crossover.2-16 

2-2 Generalized Crossover.2-17 

2- 3 Graphical Depiction of how GENESIS Operates.2-20 

3- 1 Box with Length, Width, and Height = 2.3-5 

3-2 Ensuring Correct Box Dimensions.3-6 

3-3 Packing of the Six Box Test Case.3-12 


vi 









List of Tables 


Table Page 

3-1 Box Characteristics for the Three Box Test Case.3-8 

3-2 Penalties for Constraint Violations.3-10 

3-3 Parameter Settings for the Three Box Test Case.3-10 

3-4 Box Characteristics for the Six Box Test Case.3-11 

3-5 Parameter Settings for the Six Box Test Case.3-11 

3-6 Box Characteristics for the Eleven Box Test Case.3-12 

3-7 Parameter Settings for the Eleven Box Test Case.3-13 


vii 









AFIT/GOR/ENS/00M-02 


Abstract 

It is through practice and experience Air Force loadmasters are able to pack the 
Air Force standard HCU-6/E (463 L) pallets efficiently. Although the loadmasters 
perform their jobs exceptionally well, the Air Force is in search of a model that will more 
efficiently pack the pallets. 

We have developed a mathematical formulation of the three-dimensional pallet¬ 
packing problem which minimizes the amount of unused space on a pallet. The 
formulation ensures each box is packed with the correct volume and dimensions, and 
ensures the volume of all the boxes packed is less than the available pallet volume. 
Additionally, the formulation ensures that each box has a foundation on which to be 
placed and allows, at most, one box to be placed in each location on the pallet. 

The three-dimensional pallet-packing problem is a NP-hard problem. Thus, for 
large problems, the optimal solution can not be found in a reasonable amount of time. 
Therefore a heuristic solution approach is required to solve these large problems. This 
research observes the performance of a genetic algorithm on the three-dimensional pallet¬ 
packing problem using single-point crossover. 


VUl 



Chapter 1 - Introduction 


1.1 Background 

The mission of AMC is “The Air Mobility Team ... Responsive Global Reach for 
America ... Every Day.” An important aspect of this responsiveness is providing the 
troops in forward locations with the goods they need using the fewest number of planes. 
Therefore, in hope of optimizing the use of our aircraft while simultaneously minimizing 
transportation costs, loadmasters attempt to maximize the amount of cargo on a given 
aircraft. Another aspect of cargo loading that could help cut costs and increase airlift 
efficiency is the packing of cargo on the pallets. 

Pallets are packed by Air Force loadmasters. Loadmasters attend a training 
course on the basic principles of pallet packing, yet it is through practice and experience 
that they are able to pack the pallets as efficiently as they do. Experienced loadmasters 
eyeball the items to be loaded and determine the best way to load them. The pallets are 
Air Force standard HCU-6/E (463 L) pallets. The length and width of the pallets are 88 
inches (7 feet 4 inches) and 108 inches (9 feet), respectively. However, only 84 inches of 
the length and 104 inches of the width are available to be packed. Loadmasters are 
required to leave the outside two inches of the pallet unpacked so that the cargo net is 
able to securely fit around the packed boxes. The maximum height of a pallet is 96 
inches (8 feet) for pallets loaded in the main compartment and 76 inches (6 feet 4 inches) 
for pallets loaded on the ramp (Taylor, 1994). 

Although loadmasters perform their jobs exceptionally well, the Air Force is in 
search of a model that will help efficiently pack the pallets and provide loadmasters with 


1-1 



a report stating where the boxes should be placed on the pallet to minimize unused space. 
This will save time and resources. If the pallets are more efficiently packed, the number 
of sorties flown may decrease and aircraft may be freed to carry other items in large-scale 
mobilizations. 

The Air Force has sponsored research in this area on multiple occasions in search 
of finding a better way to pack the pallets and load the aircraft. These include an early 
effort by Taylor (1994), an airlift-loading model by Chocolaad (1998), and a three- 
dimensional packing problem approach by Manship and Tilley (1998). 

Taylor developed three different models in an attempt to solve the hybrid two- 
dimensional packing problem. The goal of the hybrid packing technique is to pack the 
boxes in layers as in the two-dimensional case. An additional goal is to minimize the 
deviation in height between the boxes in each layer. This helps make the height of each 
layer as uniform as possible (Taylor, 1994). 

Taylor’s first model minimized the deviation in height between the boxes in a 
layer while maximizing the area covered. In his second model, the objective was to 
minimize the deviation in volume wasted based on whether or not a given box was 
loaded. The amount of wasted volume depended on whether or not any unused surface 
area of the pallet remained due to choosing a specific box. By minimizing the largest of 
these values over the set of boxes, the most volume efficient packing solution could be 
found (Taylor, 1994). Taylor’s third model was an extension of the second model, and 
the objective was to minimize the wasted volume of all packed boxes. 

Taylor was able to come up with optimal solutions for his model, but due to 
limited computer resources and capabilities, he was only able to solve three very small 


1-2 




problems (Taylor, 1994). The first problem was loading four boxes onto a three by three 
pallet. The second problem was loading seven boxes onto a four by four pallet in which 
one box was manually placed. The last problem was loading eight boxes onto a five by 
five pallet in which two boxes were manually placed. Since his test problems were only 
concerned with packing two layers on a pallet, the pallets did not have a height 
dimension. 

Chocolaad’s (1998) research pertains to the airlift-loading problem. In his 
research, he developed a packing heuristic which uses simple tabu thresholding to 
determine the packing. This is a simple search method which avoids becoming trapped at 
a local optimum by allowing non-improving moves (Chocolaad, 1998). However, 
Chocolaad’s research addresses the airlift loading problem and not the pallet-packing 
problem. Thus, he is trying to maximize utilization of the aircraft as opposed to the 
utilization of a pallet. In the two-dimensional case, the airlift-loading problem is similar 
to the pallet-packing problem in that the goal is to maximize the number of different size 
items (boxes/cargo) to fit into an airplane or pack onto a pallet subject to some 
constraining factors. 

Manship and Tilley (1998) approached the three-dimensional packing problem 
using a nonlinear programming approach. Unfortunately, their pallet-packing model only 
provides sub-optimal solutions. However, it does provide feasible solutions that include 
most of the required constraints (Manship and Tilley, 1998). 

Efforts in the past to improve on current pallet-packing procedures have at best 
only produced marginally better pallet loads, yet due to the complexity of the problem, 
very little if any time is saved due to computational times (Taylor, 1994). Therefore, 


1-3 



there is much room for improvement in the area of pallet packing. A model that can 
efficiently pack pallets not only will cut costs but will free time and resources to be used 
elsewhere. 

1.2 Three-Dimensional Pallet-Packing 

Of all the research devoted to optimization problems, only a very small 
percentage of that research focuses on packing problems, and even a smaller percentage 
of that research concentrates on three-dimensional pallet-packing problems. The main 
reason for this is that if the three-dimensional pallet-packing problem is formulated as an 
integer program, it becomes an extremely complex and difficult to solve problem. As the 
pallet dimensions increase and the number of boxes to be packed increase, the number of 
variables required to model the problem explodes; thus, the problem does not admit a 
solution-time based on a polynomial function of the problem size. 

Although the focus of this research is in three-dimensional pallet packing, it is 
important to describe how the three-dimensional pallet-packing problem differs from the 
other types of packing problems. First, there are two general types of packing problems; 
there are the ‘manufacturer’s pallet packing problem’ and the ‘distributor’s pallet packing 
problem’. The ‘manufacturer’s pallet packing problem’, also referred to as the pallet 
loading problem, is the problem of finding the optimal layout for identical rectangular 
boxes on a rectangular pallet (K. Dowsland, 1987). Generally, the pallet is packed in 
layers where the second layer is packed the same as the first layer and so on until the 
height constraint of the pallet is reached. Thus, the formulation for this problem is 


1-4 




reduced to the two-dimensional case and the objective is to maximize the number of 
boxes packed on the pallet. 

For the ‘distributor’s pallet packing problem,’ the objective is to load boxes of 
varying dimensions onto as few pallets as possible (Askin and Standridge, 1993). This is 
a more difficult problem. For the case in which only one pallet is to be loaded, the 
objective is to maximize volume utilization (minimize the amount of unused space). 

Most work done with the three-dimensional case of this problem has attempted to group 
boxes with the same or similar height to form layers. Then using these layers, the 
algorithm packs the layers until the height constraint is reached. 

Other packing problems very similar to the three-dimensional pallet-packing 
problem are the three-dimensional container-loading problem and the bin-packing 
problem. For all three of these problem types, the objective is to maximize volume 
utilization. However, the container-loading problem and the bin-packing problem have 
one less constraint than the three-dimensional pallet-packing problem. Since both bins 
and containers have vertical walls providing load stability, neither of these two problem 
types includes a load stability constraint. Load stability means the boxes do not have the 
tendency to tip over once packed. The three-dimensional pallet-packing problem on the 
other hand must include the stability constraint to ensure the packing of the boxes is 
stable. 

The distributor’s three-dimensional pallet-packing problem is the most difficult of 
the packing problems. Unfortunately, expanding two-dimensional formulations to 
incorporate the third dimension becomes intractable for realistic problems. In addition, it 


1-5 



is very difficult to modify these formulations to meet the additional required constraints 
of the three-dimensional pallet-packing problem, particularly the stability constraint. 

1.3 Statement of the Problem 

The purpose of this research is to develop a three-dimensional pallet-packing 
algorithm that can be adopted by the Air Force to improve the current packing procedure. 
Few models have been developed to attack the three-dimensional palletization problem 
with non-uniform box sizes, and as mentioned in the previous section, not many of these 
models took a strict three-dimensional approach. Most algorithms attack the third 
dimension using some pseudo three-dimensional approach, such as the layered approach. 
This research employs a strict three-dimensional procedure for non-uniform box sizes 
that more efficiently packs pallets. 

1.4 Restrictions and Assumptions 

Due to the complexity of the three-dimensional palletization problem as well as 
the lack of previous work that has been accomplished in this area, many simplifying 
assumptions are employed in the formulation. The goal is to start simple and add 
complexity until we can pack Air Force 463L pallets. 

The first two restrictions are quite obvious. The first restriction is that only one 
box can occupy each pallet location. The second restriction is that the boxes are not 
permitted to extend beyond the dimensions of the pallet. Thus, the volume of all packed 
boxes must be less than the available pallet volume. Before a pallet is loaded onto a 
plane, the loadmaster secures the pallet by tying down cargo nets around the load. 


1-6 



Protruding boxes prevent the loadmaster from adequately securing the load. Therefore, 
to help the formulation “pack the boxes” so that they fit within the boundaries of the 
pallet, each box can be packed in any of its six orientations. 

Additionally, we assume in the formulation that no overhang is allowed when the 
boxes are packed. For a box to be packed, its entire base must be on top of either the 
pallet or other boxes. A further restriction is that all boxes are rectangular in nature. 

Both of these restrictions are commonly found in three-dimensional formulations. The 
first prevents the packed boxes from tipping, which adds to the stability of the load, 
whereas the second restriction simplifies the problem so spherical and cylindrical objects 
do not have to be accounted for in the formulation. 

Generally, Air Force 463L pallets are “cubed out” before they are “grossed out” 
(Taylor, 1994). This means the total available volume of the pallet is generally filled 
before the allowable weight limit is reached. For this reason, the weight of the boxes is 
initially omitted from the formulation. Therefore, all constraints dealing with weight are 
omitted. 

The first weight constraint omitted is the constraint ensuring the weight of all 
packed boxes does not exceed the available weight of the pallet. The second weight 
constraint omitted ensures heavier boxes are placed below lighter boxes. The third 
weight constraint omitted is the center of gravity constraint. For safety reasons, the Air 
Force requires that the center of gravity of a load is within four inches of the center of the 
pallet. 

Another constraint not included in this formulation is the load stability constraint. 
This constraint is omitted since each box is required to have a complete foundation under 


1-7 




it. Additionally, we are omitting the constraint which ensures the top of the load is as 
close to level as possible. This is required so that when the cargo net is thrown over the 
load, boxes do not shift or fall. Lastly, we are only concerned with packing boxes onto 
one pallet. These assumptions aid in the development of a formulation strictly concerned 
with the placement of boxes; yet allows for future modifications increasing the realistic 
nature of the formulation. 

1.5 Overview 

Chapter Two presents a detailed review of past work accomplished in this field of 
study and describes some of the solution techniques used by others. In addition, it 
touches upon a couple of commercial three-dimensional pallet-packing software 
packages available for purchase. Chapter Three describes in detail the development of 
the formulation and the constraints in the formulation. Since for larger, more realistic 
problems the number of variables increases exponentially, we also discuss in Chapter 
Three the heuristic applied to solve the problem’s formulation. Lastly, Chapter Four 
provides a formal conclusion and recommendations for follow-on research. 


1-8 




Chapter 2 - Literature Review 


2.1 Introduction 

Much of the previous work on packing problems pertains to the two-dimensional 
packing problem. Yet in recent years with the advancements in computer technology and 
the advent of new solution techniques, there has been an influx of research and published 
papers in the realm of the three-dimensional pallet-packing problem. Unfortunately, the 
three-dimensional pallet-packing problem is a NP-hard problem; thus, for relatively large 
problems, the optimal solution can not be found in a reasonable amount of time. For this 
reason, much of the research on the three-dimensional palletization problem includes the 
implementation of a heuristic to find a good solution. 

“A heuristic is a technique which seeks good (i.e., near optimal) solutions at a 
reasonable computational cost without being able to guarantee either feasibility, or 
optimality, or even in many cases to state how close to optimality a particular feasible 
solution is” (Reeves, 1995). Instead of having to search the entire solution space and 
enumerate all possible solutions to find the optimal solution, a heuristic provides a means 
for smartly searching the solution space, examining only those areas where the optimal 
solution most likely resides. The heuristic will not necessarily converge on the optimal 
solution; yet, they generally provide solutions close to optimal in a reasonable amount of 
time. 

The remainder of this chapter reviews past research pertaining to the three- 
dimensional pallet-packing problem. Additionally, it reviews a couple of the commercial 
pallet-packing software packages available for purchase. Lastly, it reviews the 


2-1 


application of heuristics to the three-dimensional pallet-packing problem, specifically the 
application of the genetic algorithm to solving the three-dimensional palletization 
problem. 

2.2 Three-Dimensional Pallet-Packing Problem 

For nearly twenty years both Kathryn A. Dowsland and William B. Dowsland 
have been researching packing problems. Most of their earlier work focuses on the two- 
dimensional pallet-packing problem, yet they do address the three-dimensional packing 
problem. In a combined packing overview, one paper suggests that, on average, a three- 
dimensional algorithm will better load boxes on a pallet. However, they state this will 
come at an expensive computational cost and there will always be situations when a 
manual packing will more efficiently pack a pallet (Dowsland and Dowsland, 1992). 

William Dowsland (1991) states that since this is such a new field, much of the 
published work regarding the three-dimensional palletization problem declares successful 
implementation, but fails to provide the reader with any clear measure of scientific 
success. Since this is such a new area of study and many different methods are being 
attempted, any work illustrating a successful implementation of an algorithm is 
published. Scientific results stating how well a particular method performed on the three- 
dimensional pallet-packing problem are generally not provided, yet this is the information 
most useful to those performing follow-on research as it dictates what methods to avoid, 
or what methods to pursue further. 

Dowsland addresses many of the methods used by researchers to pack pallets in 
the third dimension. Unfortunately, he states many of these methods will become 


2-2 



intractable when extended to larger, more realistic problems (Dowsland 1991). Two 
methods discussed are the layered approach and the ‘L’ packing approach. The idea 
behind the layered approach is grouping boxes of the same height together and packing 
that group along the bottom of the pallet. Boxes of the same height are continually 
grouped and then packed as the next layer on the pallet. This continues until the height 
constraint is reached. If there are not enough boxes of the same height to fill a layer, then 
the algorithm searches for boxes closest in height and packs them as a layer. 

The problem with using the layered approach when packing in three dimensions is 
accounting for the stability of the load and the weight of the boxes. Moreover, if there 
are many boxes with different heights, the packing efficiency drops. It is generally good 
practice to first pack the larger, heavier boxes on the pallet to provide a foundation for the 
other boxes. However, a layered approach will pack the boxes with the same height first 
no matter their weight or volume. Thus, when using the layered approach in three 
dimensions, there are numerous additional checks the algorithm must perform to ensure 
the packing satisfies these additional constraints. 

The ‘L’ approach is also known as the wall building approach. As in the layered 
approach, we first want to group boxes with the same height and pack them as a layer 
along the floor of the pallet. Then, boxes with similar dimensions are grouped together 
and stacked vertically along one of the walls until the height constraint is reached. The 
algorithm continues alternating between packing the boxes in a horizontal layer and a 
vertical column until there are no more boxes that can be packed or there are no more 
boxes to pack. Han, Knott, and Egbelu (1989) applied this approach to the manufacturers 
pallet-packing problem and were able to achieve good results. 


2-3 


When packing different sized boxes, the main concern with this type of packing is 
how to ensure packing stability since this type of packing technique can produce gaps 
between the vertical columns of packed boxes (Dowsland, 1991). Additionally, when 
there are not enough boxes to completely fill the pallet, the algorithm produces 
unbalanced loads. Lastly, it is preferred to pack pallets upward from the base of the 
pallet. For these reasons, the ‘L’ approach has been known to produce loads that do not 
satisfy the stability constraint nor the center of gravity constraint, and thus this approach 
has not been used except for cases where the boxes to be packed are of uniform size. 

Abdou and Yang (1994) developed a multi-objective algorithm for the 
palletization problem. They attempt to maximize both pallet utilization and stability. 
Stability is needed to prevent the boxes from toppling when packed. To prevent this, 
larger, heavier boxes should be packed below the smaller, lighter boxes. This provides a 
solid foundation for the next layer of boxes. In their approach, Abdou and Yang attempt 
to simplify the problem by grouping boxes with the same height. 

In addition, the authors develop blocks that are subsets of the actual pallet. They 
try to maximize the space filled within each block, by either filling it with a large box or 
with several smaller boxes. As expected, when new blocks are generated, the criteria is 
to use boxes that have not been previously selected, use the bigger boxes first, and lastly 
use as few boxes as possible. This makes it easier to pack the next layer. By packing the 
larger boxes first, either the volume of the block will be filled, or the larger boxes provide 
a good foundation for the boxes placed above them. 

Abdou and Yang’s algorithm has many features required by the Air Force. 
However, to increase the capability of this model, boxes with similar heights but different 


2-4 



base dimensions should not be grouped together. Abdou and Yang’s current model uses 
a layered approach to attack the third dimension. Although the boxes are not the same 
size, they are grouped by height so that the packing can be performed in layers. By 
disallowing this requirement, the complexity of the problem increases, however the 
opportunity for a better solution increases as well. 

Abdou and Arghavani (1997) developed a three-dimensional algorithm that 
arrives at its solutions through two separate objective functions. The first objective 
function attempts to maximize the packed base area of the pallet. Additionally, sub-areas 
are defined within this objective function. The second objective function seeks to 
maximize the stacking column for each sub-area. 

Abdou and Arghavani (1997) discuss some constraints for their three-dimensional 
pallet-packing problem. One constraint ensures all boxes are packed within the confines 
of the pallet. Another ensures the stacking heights are less than or equal to the maximum 
pallet height. A third constraint limits the number of each type of box available while a 
fourth constraint allows the boxes to be packed in only one of two orientations. This is 
also known as the ‘face up’ constraint where the boxes can only rotate 90° around the 
vertical axis. 

Ivancic, Mathur, and Mohanty (1989) attack the three-dimensional packing 
problem to minimize the number of pallets required to hold all the boxes. This is 
basically the same as maximizing pallet efficiency. The authors formulate the problem as 
a multidimensional knapsack problem and use a greedy heuristic to pack the boxes. 
Instead of packing boxes by using the “biggest bang for the buck” philosophy, their 
algorithm favors packing the box type having the most boxes left unpacked or those with 


2-5 





smaller volumes. The algorithm avoids packing boxes that trap unpacked space. This 
algorithm does allow the boxes to be packed in any of the six orientations, yet a major 
drawback of this heuristic is that it requires knowledge of all the packing patterns, which 
for large problems is computationally prohibitive (Ivancic, Mathur, and Mohanty, 1989). 

Bischoff, Janetz, and Ratcliff (1995) developed a three-dimensional heuristic 
approach to packing multiple-sized boxes onto a pallet, also known as the “Distributor’s 
Pallet Packing Problem.” Their objective function maximizes pallet utilization while 
ensuring the load is stable. The algorithm developed by the authors packs the boxes in 
layers allowing up to two different box types per layer; however, it gives preference to 
those layers which can be filled by a single box type. 

The authors found the layering approach provided better stability than those 
algorithms which pack boxes in vertical columns. Additionally, the algorithm prefers 
larger gaps between boxes to smaller ones. The larger the gap, the better the chance a 
box will be able to fill the vacancy. The algorithm did produce stable loads, but as the 
number of various sized boxes increased, the packing efficiency declined. 

Bischoff and Ratcliff (1995) published a follow-on to the article described above. 
They packed pallets in layers allowing at most two different box sizes per layer. The 
focus of this research was to determine whether it is better to load multiple pallets 
simultaneously or pack them sequentially. Simultaneous packing means that all the 
pallets are loaded at the same time, whereas sequential packing means that one pallet is 
fully loaded before any boxes are placed on the next pallet. The authors found packing 
the pallets sequentially to be the better packing method. 


2-6 


Fuh-Hwa and Hsiao (1997) address the three-dimensional “manufacturer’s pallet 
loading problem.” Since all the boxes are the same size, the authors use a layered 
approach to pack the boxes. The boxes are packed with any orientation; however, they 
must be packed so that the height of each layer is constant. While a primary objective is 
to maximize the number of boxes on each pallet, stability is also important. They check 
to ensure no packed vertical columns are removed from the rest of the packing. They 
also ensure each box has a solid base underneath it. Lastly, for problems where the boxes 
are not all the same size, they pack the heavier, larger boxes on the bottom of the pallet 
providing a solid foundation for the remaining boxes. 

Fuh-Hwa and Hsiao have developed a three-dimensional heuristic to maximize 
the pallet load. They model this problem with boxes of four different sizes arriving 
randomly at a loading dock. Once at the loading dock, the critical path method is used to 
determine the placement and sequence of the boxes. For example, for a box to be 
packed, there must be a solid, uniform foundation for that box. Although the technique 
may be transferable to the Air Force’s pallet-packing problem, the scenario is different. 
The authors developed this model to pack boxes arriving on a conveyor belt as opposed 
to packing boxes already at the loading site. 

Tsai, Malstrom, and Kuo (1993) developed an exact model for the three- 
dimensional pallet-packing problem. Unfortunately, as the number of boxes increases, 
the computation time required to find the optimal solution increases and limits the 
practical use of this model. However, the authors do provide the constraints required to 
ensure no two boxes overlap and that all boxes, if packed, are packed within the confines 
of the pallet. 


2-7 



The authors’ model did not include the constraints that address the issue of load 
stability. The model was designed for the single pallet case and thus the objective of the 
model was to maximize the packing volume. They did not consider the case when there 
are multiple pallets to be packed. Lastly, the authors did allow the boxes to be packed in 
one of two orientations; the boxes were allowed to rotate 90° around the vertical axis. 

Tsai, Malstrom, and Kuo introduced a heuristic to solve the three-dimensional 
pallet-packing problem. This paper focuses on packing boxes arriving via a conveyor 
belt. Additionally, this problem is concerned with packing multiple pallets 
simultaneously. The arrival of different sized boxes on a conveyor belt does reflect how 
boxes arrive in distribution centers, however it is quite different from this research’s 
problem. 

2.3 Previously Contracted Efforts 

The Air Force has been examining this problem for many years in an attempt to 
minimize the costs associated with shipping cargo. In addition to the past research efforts 
at the Air Force Institute of Technology (AFIT), the Air Force has contracted this 
problem to companies outside the DoD. Both the Computer Science Corporation (1997) 
and TASC, Inc. (1998) performed research on this topic. 

The Computer Sciences Corporation’s research states that although a strict 
mathematical model which produces optimal loads may not be available, heuristic 
techniques are available which could enhance load efficiency as well as reduce the time it 
takes to produce a load (Computer Sciences Corporation, 1997). Thus, they do feel a 
software package can be developed which takes into account the necessary packing 


2-8 



constraints and is able to find a close to optimal packing. Additionally, they state it is 
crucial for the software package to provide instructions describing exactly how to achieve 
the packing found by the software. 

The research provided a review of current systems employed by the Air Force 
and a review of existing literature on the pallet-packing problem. Unfortunately, none of 
the existing systems used by the Air Force specifically address packing pallets. 

Therefore, the research reviewed existing literature on the packing problems and 
commentated on how the current research pertained to the Air Force’s requirements. 

TASC, Inc. researched the three-dimensional pallet-packing problem. The initial 
focus of their research was the feasibility of finding optimal solutions. However, as they 
became more familiar with the problem and its inherent complexity, the focus of the 
research changed to the feasibility of finding reasonably good solutions (TASC, 1998). 
Before they looked at solving the problem, they performed a literature search on past 
pallet-packing efforts. They found a lot of research has been performed on this problem, 
yet none of the research was complete in the sense that it encompassed all the 
requirements of the Air Force. 

The TASC research provided a list of all the packing rules and constraints used by 
the Air Force. While some of the constraints are required, other constraints are either 
recommended or optional. 

Before introducing the pallet-packing software they developed, TASC described a 
few of the existing pallet-packing software packages. The software package they 
developed was LoadPal (short for load pallet) (TASC, 1998). This program was written 


2-9 


in C++ and contained most of the major constraints. Unfortunately due to time 
constraints, the program did not include a Graphical User Interface (GUI). 

After testing their software package, they found that their approach was comparable 
to other existing software packages. However, they stated that their package could be 
expanded to include the other required constraints and employ a better solution technique 
which would provide statistically better solutions than those found from existing software 
packages. They suggest the cost of developing this product would be $150,000 and it 
would require six months of effort. 

2.4 Commercial Packing Software 

The Remarkable Software Company located in New Zealand is selling a three- 
dimensional pallet-packing software package (PowerPak™) that may possibly be of use 
to the Air Force. They have developed PowerPak™ to allow boxes with different sizes 
and attributes be loaded into the program. There is also no limitation on the size of the 
pallet or the size of the boxes as long as each uses the same units. Additionally, there is 
no limit on the number of boxes that can be input into the system. However, the program 
only allows the user to pack one pallet at a time. 

PowerPak™ also allows the user to input the maximum allowable weight for the 
pallet as well as the weight of each box. Using these values, the program determines the 
packing of boxes onto the pallet to minimize empty space. Once a solution is found, the 
software allows the user to rotate the pallet to see where each box was placed, but more 
importantly it provides an Optimized Packing Sequence Report. This report allows the 
user to achieve the computed packing through a step by step process. 


2-10 



Unfortunately, there is little insight into which technique(s) PowerPak™ uses to 
pack boxes on a pallet. The product does take weight into account, making sure the 
weight of all packed boxes does not exceed the allowable pallet weight, but it is unclear 
whether or not the model ensures heavier boxes are packed towards the bottom. 

Another commercial software product pertaining to pallet loading is Capesystems. 
Capesystems allows the user to pack up to three pallets simultaneously. Moreover, this 
product does not limit the shapes of the items to be packed. It packs cases, cylinders, 
ovals, and trapezoidal items. Three different modules are available to deal with the range 
of pallet-packing problems. 

The first module is Single Product and is used for the loading of identically sized 
boxes. For a large problem, this module’s computation time is around 15 seconds. The 
next module, Display Pallet, allows the user to load products of up to 40 different sizes. 
However, this module has a limit on pallet dimensions. Each dimension must be less 
than 100 inches. Therefore, since the length of the 463L pallet is 108 inches wide, this 
module would not meet Air Force requirements. Depending on the number of different 
sized boxes to be packed, the solution time for this module is around one minute. For 
both of these products, the program uses a series of logistical algorithms to pack the 
boxes in layers or in columns. 

The last module is concerned with packing products with different dimensions 
perpendicular to the pallet. This term means that the items packed must be packed 
upright. Since this research is not concerned with non-rectangular shapes, little 
information was gathered on this module. 


2-11 




However, they do have another product, Truckfill, which handles the larger sized 
pallets such as the 463 L pallet. This product was designed more for logistics than it was 
for optimization, thus the packing is not as efficient as one would get using either of the 
other two modules. Since this module allows for such a diverse range in problem size, 
Capesystems provided no estimate regarding the average solution time using Truckfill. 

2.5 Heuristics 

Heuristics are commonly applied to packing problems so that realistically large 
problems can be solved in a reasonable amount of time. Although the solutions are not 
guaranteed to be optimal or even close to optimal, heuristics generally provide good 
solutions. A variety of heuristics have been applied to the three-dimensional pallet¬ 
packing problem, but the three most common heuristics used are the greedy heuristic, 
simulated annealing and genetic algorithms. 

2.5.1 Greedy Heuristic 

A greedy heuristic is a simple approach to the packing of the boxes on a pallet. 
The algorithm packs the largest boxes first and continues down the list of boxes until no 
more boxes can fit on the pallet. Unfortunately, the greedy heuristic does not necessarily 
provide efficient loads and thus is not used except to provide starting solutions for other 
heuristic techniques. 


2-12 



2.5.2 Simulated Annealing 

Simulated annealing is another heuristic that has been utilized in packing 
problems. K. Dowsland (1993) used simulated annealing techniques on the two- 
dimensional packing problem. Simulated annealing is a probabilistic search technique in 
that moves are selected with some associated probability. 

For the packing problem, simulated annealing begins with some initial solution. 
This solution can be found through the use of a greedy heuristic or it can be as simple as 
starting with an empty pallet. The algorithm then proceeds through the list of boxes and 
picks a box at random to enter the packing. Entering that box into the packing is 
considered a “move.” If that box increases pallet utilization while maintaining a feasible 
solution, then the move is accepted. However, if the move is infeasible, then a box is 
picked at random to be removed from the solution. All moves that increase pallet 
utilization are accepted as long as feasibility is maintained. However, if a move 
decreases pallet utilization, the move is only accepted according to some probability 
function designed by the user. 

In the initial stages of the algorithm, it is generally good practice to have the 
algorithm accept both improving and non-improving moves. This prevents the search 
from converging on a local optimum. Then as the search proceeds, the algorithm should 
select fewer unimproving moves to encourage the algorithm to converge on the global 
optimum. This is referred to as the cooling schedule. It is defined by the user and is 
generally different for each problem. Defining a cooling schedule is a very difficult and 
timely process. “It is said that while simulated annealing is easy to get working it is 
difficult to get working well.” (Dowsland, 1993) 


2-13 


2.5.3 Genetic Algorithms 

A third heuristic technique most commonly applied to pallet-packing problems is 
genetic algorithms. Genetic algorithms exploit historical information to speculate on new 
search points with expected improved performance. Genetic algorithms are based on the 
ideas of natural selection and the goal is to start with a group of initial solutions, called a 
population, and use these initial solutions to guide the search to the optimal solution. The 
initial population can be randomly generated or it can be initialized using solutions from 
quick, greedy heuristic techniques. The initial population is referred to as the first 
generation. After each iteration, a new population is produced. The user must determine 
the number of iterations to perform or the number of generations to generate before 
terminating the search. 

Additionally, the user must determine the size of the population. This is a 
difficult parameter to assess since it varies for each problem type and problem size. If a 
population size is too small then there is an insufficient number of different solutions, the 
population is not diversified enough, and the genetic algorithms may converge on sub- 
optimal regions. On the other hand, an extremely large population provides too much 
diversification and genetic algorithms may fail to converge to even local optimal 
solutions. Additionally, with extremely large populations, the solution time increases 
drastically. Therefore, the goal is to find a population size which provides enough 
diversification with reasonable solution times to obtain good solutions. 

Once a population is established, members from that population are combined 
(mated) to produce new solutions (a new generation). Four genetic algorithm parameters 
determine which members of a population should mate, how they should mate, and which 


2-14 



candidate solutions should become the members of the next generation. These 
parameters are the selection strategy, crossover rate, mutation rate, and generation gap. 

The selection strategy determines which members of a population mate. 
Proportional selection, the elitist strategy, and rank-based selection are three of the more 
popular selection strategies. In each method, members are randomly selected, however 
the random selection differs for each strategy. Proportional selection is the most common 
of all selection strategies. This strategy proportionally assigns probabilities to candidate 
solutions based on their objective function value. Those solutions with better objective 
function values have a higher probability of being selected for mating. The elitist 
strategy is a variation of proportional selection that ensures the best candidate solution 
survives into the next generation (Grefenstette, 1990). The elitist strategy generally 
converges on solutions quicker than a completely random selection; however, it 
sometimes converges prematurely on sub-optimal locations. The ranking strategy ranks 
the candidate solutions and assigns probabilities based on their rank within the 
population. Thus, higher-ranking solutions have a greater probability of being selected 
for mating. 

Two basic operations are responsible for how the actual mating occurs. They are 
crossover and mutation. The idea behind crossover is that of exploitation. The goal of 
exploitation is to mate two parents associated with good solutions to produce offspring 
which have an improved solution. This continues until the genetic algorithm converges 
on a good solution or is kicked out of that region. Crossover combines selected portions 
of one parent with selected portions of the second parent to produce an offspring. 


2-15 



Generally, each solution is represented by a bit stream. Figure 2-1 provides an example 
of single-point crossover. 

Parent 1: 001001 || 1101 Child 1: 001001 || 1001 

Parent 2: 010101 j| 1001 Child 2: 010101 || 1101 

Figure 2-1: Single-point Crossover 

There are numerous types of crossover operations that can be applied in a genetic 
algorithm. The most primitive type of crossover operation is the single-point crossover. 
The algorithm randomly chooses a place along the bit stream where the crossover should 
occur. In Figure 2-1, the vertical lines after the sixth bit signify the crossover point. 

Once this crossover point has been established, the algorithm takes the first group of bits 
from the first parent and combines them with the second group of bits from the other 
parent to produce a new offspring or child. Thus for Child 1, the first six bits come from 
the first six bits of Parent 1, while the remaining four bits come from the last four bits of 
Parent 2. For Child 2, the first six bits come from the first six bits of Parent 2, while the 
remaining four bits come from the last four bits of Parent 1. 

Although single-point crossover is the simplest type of crossover, it is not 
necessarily the best type of crossover. In fact, single-point crossover limits the amount of 
information which is exchanged between the parents (Reeves, 1995). To combat this, 
multi-point crossover can be applied to improve the performance of a genetic algorithm. 

Another type of crossover that can be applied is ‘string-of-change’ crossover. 
(Reeves, 1995) This is a special type of single-point crossover that should be applied 
only when the bit stream of both parents to be mated is similar through the first few bits. 
This is because if both bit streams are similar through the first few bits and the single- 


2-16 




point crossover occurs in this location, then the crossover will fail to produce a new 
string. Thus, ‘string-of-change’ crossover checks the bit streams to ensure the crossover 
point produces offspring with different bit streams than the parents. 

A third type of crossover is referred to as the generalized crossover, also called 
uniform crossover (Reeves, 1995). For this type of crossover, after the parent bit streams 
have been chosen, a third bit stream of equal length to the other bit streams is randomly 
generated. Figure 2-2 below provides an example of generalized crossover. 

Parent 1: 0010011101 Child 1: 0111011101 

Parent 2: 0101011001 Child 2: 0000011001 

Random Bit Stream: 1010010110 

Figure 2-2: Generalized Crossover 

For Child 1, wherever there is a ‘ 1’ in the random bit stream, the corresponding 
bit is taken from Parent 1, and wherever there is a ‘O’ in the random bit stream, the 
corresponding bit is taken from Parent 2. Thus, the random bit stream provided in Figure 
2-2 implies that for Child 1, the 1 st , 3 rd , 6 th , 8 th , and 9 th elements are taken from Parent 1, 
while the 2 nd , 4 th , 5 th , 7 th , and 10 th elements are taken from Parent 2. It is the opposite for 
Child 2. Wherever there is a ‘ 1’, the element is taken from Parent 2, and wherever there 
is a ‘O’, the element is taken from Parent 1. These three types of crossover are the most 
common types and have been successfully implemented in past research. 

Mutation attempts to jump the solution out of the current solution space by adding 
exploration to the search. The purpose of mutation is to prevent the genetic algorithm 
from quickly converging on a sub-optimal solution and is applied after the crossover has 
taken place. Mutation occurs when the value of a single bit in a solution is flipped. For 


2-17 



example, if a bit chosen for mutation has a value of 1, after mutation its value is changed 
to 0. The user defines how much mutation to include in the problem, but generally the 
mutation rate is less than five percent. Each bit in the bit stream has an equal probability 
of being mutated. Therefore, based on the probability introduced by the user, the 
algorithm determines which bit(s) to mutate. 

The generation gap determines the percentage of offspring to include in the next 
generation. There are two methods used to determine this; the generational genetic 
algorithm and the incremental genetic algorithm. In the generational genetic algorithm, 
all offspring are included in the next generation, completely replacing the previous 
generation. In the incremental genetic algorithm, only selected offspring are included in 
the next generation. Generally, they replace those members from the previous generation 
associated with the worst solutions. 

It is generally good practice to replace a majority of the parent generation, yet it is 
also important to allow some of the parent generation to survive from one generation to 
the next. When only a small portion of the parent generation is replaced, the algorithm 
frequently fails to converge on a feasible solution. On the other hand if we replace the 
entire parent generation, then it is possible that we are removing good candidate solutions 
from our solution space. However, most genetic algorithms maintain a list of the best 
solutions found to date. Therefore, even if an entire population is replaced, the genetic 
algorithm will remember the best solutions found. 

The algorithm continues these operations until the technique has converged on the 
best solution at which time each solution in the population will have basically the same 
bit make-up. 


2-18 



A weakness of genetic algorithms is its handling of constraints. Constraint 
violations are penalized in an objective function. The appropriate form of these 
constraint penalty functions can be difficult to determine; this is particularly true in this 
research. 

2.6 GENESIS 

Genetic Search Implementation System, GENESIS, is a program written in C- 
code that performs all the genetic algorithm operations (Grefenstette, 1990). All that is 
required is for the user to write his own evaluation function which determines a candidate 
solution’s objective function value. 

The user determines how many generations the algorithm should generate as well 
as the size of the initial population. The user also determines how to generate the initial 
solutions. It can be done randomly, or the initial population can be ‘seeded’ with 
solutions found by a greedy heuristic. The user also determines which selection strategy 
to use, the crossover rate, and the mutation rate. 

After this has been established, GENESIS sends the individual member of the 
current population to a user-defined program. The solution is sent in a bit stream to the 
evaluation function. When all the decision variables are binary variables, the length of 
the bit stream is equivalent to the number of variables. The user-defined evaluation 
function checks the feasibility of the solution and assigns penalties for constraint 
violations. After the program determines the objective function value (including 
penalties), the value is sent back to GENESIS. After all the members of the population 
have been evaluated, GENESIS performs all the operations necessary to produce a new 


2-19 


generation. Once a new generation is produced, these solutions are again sent to the user- 
defined program. This procedure repeats itself until the program reaches the number of 
generations specified by the user. Figure 2-3 provides an illustration of what we have 
just described. 



Figure 2-3: Graphical Depiction of how GENESIS Operates 


2.7 Summary 

There has not been a large amount of research performed on the three-dimensional 
pallet-packing problem. However, the problem has gathered interest in the operations 
research community. Appendix A presents an annotated bibliography of papers pertinent 
to packing problems. 


2-20 







In the next chapter we describe in detail the development of the three-dimensional 
pallet-packing formulation, the constraints included in the formulation, and the heuristic 
used to test and expand the formulation to handle larger problems. 


2-21 




Chapter 3 - Results 


3.1 Mathematical Formulation 

The initial focus of this research was on the development of a strict three- 
dimensional mathematical formulation for the distributor’s pallet-packing problem. We 
chose a 0-1, nonlinear model. The objective of the formulation is to minimize unused 
packing space. To determine the amount of unused space, we broke the available 
packing space on the pallet into cubic units. Since the dimensions for both the pallet and 
boxes are given in inches, the cubic units of the pallet are (inches) 3 . Therefore, the 
number of cubic units available for packing equals the volume of the pallet. 

We want the formulation to mimic actual packing procedures, so constraints force 
the algorithm to generate solutions in the same manner as a loadmaster. Therefore, the 
formulation allows the boxes to be packed in any of their six orientations. 

The constraints included in the model ensure boxes are packed with the correct 
volume and dimensions, the available packing volume is not exceeded, each box has a 
complete foundation on which to be packed, and at most only one box occupies each 
cubic unit on the pallet. Following is a descriptions of the variables used in the 
formulation. 


E 

L 

W 

H 

N 

PV 


The amount of unoccupied space on the pallet 

The length of the pallet 

The width of the pallet 

The height of the pallet 

The number of boxes to be packed 

The pallet volume available for packing 


3-1 




L x = The length of box x; where x goes from 1 to N 

W x = The width of box x; where x goes from 1 to N 

H x = The height of box x; where x goes from 1 to N 

V x = The volume of box x; where x goes from 1 to N 


A x = The number of adjacent faces for each box x; where x goes 
from 1 to N (we explain this concept in detail following the 
presentation of the formulation) 


B x 


B,jkx 


PL^ 


PW :v 


PHxy 


Binary variable used to represent whether box x is packed or not; 
where x goes from 1 to N 
0 = Box x is not packed 

1 = Box x is packed 

Binary variable used to represent whether part of box x is packed 
in pallet location i, j, k; where x goes from 1 to N, where i goes 
from 1 to L, where j goes from 1 to W, where k goes from 1 to H 
0 = Box x is not packed in pallet location i, j, k 

1 = Box x is packed in pallet location i, j, k 

Binary variable which counts the number of times when summing 
across the length of the pallet the summed value for box x equals 
the length of that box; where x goes from 1 to N, where y goes 
from 1 to (W*H) 

0 = Length of box x along length y does not equal Lx 

1 = Length of box x along length y does equal L x 

Binary variable which counts the number of times when summing 
across the width of the pallet the summed value for box x equals 
the width of that box; where x goes from 1 to N, where y goes 
from 1 to (L*H) 

0 = Width of box x along width y does not equal W x 

1 = Width of box x along width y does equal W x 

Binary variable which counts the number of times when summing 
across the height of the pallet the summed value for box x equals 
the height of that box; where x goes from 1 to N, where y goes 
from 1 to (L*W) 

0 = Height of box x along height y does not equal H x 

1 = Height of box x along height y does equal H x 


The formulation is the following: 
Minimize E 


3-2 



Subject to the following constraint sets: 


( N 


\ 


^Bx*Vx 

\x=l J 


+ E = PV 


( 1 ) 


N 

2] Bykx <1 Vi from 1 to L, j from 1 to W, k from 1 to H 


( 2 ) 


x=\ 


N 

X Bijkx - Bij(k+\)x >0 Vi from 1 to L, j from 1 to W, k from 1 to (H-l) (3) 


x=l 


L W H 


XXX 

V '=1 M k= 1 J 


-Bx*Vx = 0 V x from 1 to N 


( 4 ) 


r H W L- 1 \ f H L W- 1 '\ 

X X X ^' jhC * B{‘ + ‘W + XXX B'i 11 * ^ Bi{j+l)kx 
V *=1 M i=l J \k=l i=l j=l 


V x from 1 to N 


+ 


W L H-l 


XXX 5 * fa *^ ( * +i) * 

V y=i /=! k=\ 


( 5 ) 


■Ax*Bx = 0 


L 

^Bijkx = Lx*PLxy V j from 1 to W, k from 1 to H, x from 1 to N, y from 1 to 
i=l 

(W*H) (6a) 

W*H 

^ PLxy = Wx* Hx V x from 1 to N (6b) 

y =i 


w 

X Bijkx = Wx* PWxy Vi from 1 to L, k from 1 to H, x from 1 to N, y from 1 to 
7=1 

(L*H) (6c) 

L*H 

Y J PWxy = Lx*Hx V x from 1 to N (6d) 

y =1 


H 

^Bijkx - Hx*PHxy V i from 1 to L, j from 1 to W, x from 1 to N, y from 1 to 
k =1 

(L*W) (6e) 


3-3 




(6f) 


L*W 

J^PHxy = Lx*Wx V X from 1 to N 

Bijkx, B x , PLxy, PWxy, and PH xy = 0 or 1 

The objective of this formulation minimizes the amount of unused packing space 
on the pallet. Constraint (1) ensures the volume of the packed boxes is less than the 
available volume that can be packed. Constraint (2) is a set of constraints ensuring no 
more than one box is placed in each cubic location on the pallet. Therefore, the number 
of constraints in this set is equal to L*W*H. 

Constraint (3) ensures each box has a foundation on which to be placed. This 
helps ensure load stability. The number of constraints in this set is equal to L*W*(H-1). 
Constraint (4) ensures each packed box is packed with the correct volume. The number 
of constraints in this set is equal to the number of boxes. 

Constraint (5) is the first of two constraints ensuring each box is packed with the 
correct dimensions. We broke down each box into cubic units, where the number of 
cubic units for a box is equal to the volume of the box. Then to ensure each box was 
packed with the correct dimensions, we developed a formula to determine how many 
adjacent faces exist for a box with a given length, width and height. Figure 3-1 illustrates 
what we define as adjacent faces. 


3-4 


Top Layer 


i 

k— 

— i 

lr 

i 

V — 

-i 



Bottom Layer 

Figure 3-1: Box with Length, Width, and Height = 2 

Figure 3-1 illustrates all eight cubic units of a box with length, width, and height 
dimensions of two. The lines intersecting the faces define the number of adjacent faces 
with regards to the length and the width of the box. For this box there are eight adjacent 
faces with regards to length and width. The stars represent the number of adjacent faces 
with regards to the height of the box, which in this case equals four. Therefore, there are 
12 adjacent faces for a box with these dimensions. 

Counting the adjacent faces of each box size is a tedious assignment, especially as 
box dimensions increase. Therefore, we developed an equation to determine the number 
of adjacent faces for a box with given dimensions. This equation is shown below. 

L = Length of Box 

W = Width of Box 

H = Height of Box 

A = Number of adjacent Faces 

A = {L-\\W*H)+{W-\\L*H)+(H-\\L*W) (7) 

The first term of equation (7) finds all of the adjacent faces in the direction of the 
length. The number of adjacent faces along the length of a box is always equal to the 
length of the box minus one unit of length. This value is multiplied by the width and the 


3-5 





height of the box to determine the number of adjacent faces for the length dimension. 
The same method is applied to the width and the height of the box to determine the 
number of adjacent faces for each of those dimensions. The adjacent faces for each 
dimension are added together to determine the total number of adjacent faces for a box. 

Unfortunately, ensuring a box is packed with the correct volume and the correct 
number of adjacent faces does not ensure a box is packed with the correct dimensions. 
The figure below illustrates the phenomenon when the original five constraints do not 
ensure a box is packed with the correct dimensions. 


Box A Box B 



Figure 3-2: Ensuring Correct Box Dimensions 


Figure 3-2 provides a depiction of two possible ways to pack a box with a volume 
of four and three adjacent faces. Box A is packed correctly while Box B is not. However 
in both cases the volume of the packing and the number of adjacent box faces are correct. 
Therefore, a sixth constraint is required to ensure all boxes are packed with the correct 
dimensions. 

Constraint (6) is broken up into three different sections with two equations within 
each section. Each section represents a dimension. For example, equation (6a) illustrates 
that for each width and height pair, and for each box, the formulation sums over the 
length and counts how many units are occupied for each box. If the number of units 




equals the actual length of the box then the binary variable, PLxy, is set to one, otherwise 
it is zero. 

Equation (6b) ensures the correct length of each box occurs the correct number of 
times. The number of correct lengths for a box equals W X *H X . For a box with length, 
width, and height dimensions of two, there will be four times when the packed length of a 
box (for a given width and height) equals two. 

The other two sets of equations (6c and 6d, and 6e and 6f) ensure both the width 
and the height of each box is correct throughout the pallet. For each box, equations (6a, 
6c, and 6e) are performed W*H, L*H, and W*L times respectively, while equations (6b, 
6d, and 6f) are performed once for each box. The constraints in constraint sets (5) and 
(6) work together to ensure boxes are packed with the correct dimensions. 

As the size of the problem increases, the number of variables and constraints 
required to formulate the problem becomes very large. The equations below illustrate the 
number of variables and constraints for a problem with A boxes and pallet dimensions L, 
W, and H. 

Variables = N + (N*L*W*H) + (N*W*H) + (N*L*H) + (N*L*H) (8) 

Constraints = 1+5N+ (L * W*H)+(L * W*(H-1))+(W*H*N)+(L *H*N)+(L * W*N) (9) 


3.2 Results from LINGO 

For a small problem, we tested the formulation using HYPERLINGO, an 
optimization software package developed by LINDO Systems Inc. A small problem 
stays within the limits of the software, produces reasonable run times, and allows a 


3-7 


validation of the model results (e.g., we can check the packing). The test case developed 
had three separate boxes. Table 3-1 presents the characteristics of each box. 

Table 3-1: Box Characteristics for the Three Box Test Case 


Box 


Width 

Itferairi 



1 

3 

3 

2 

18 

33 

2 

3 

2 

3 

18 

33 

3 

3 

2 

1 

6 

7 


Additionally, the pallet the boxes were being packed on had a length, width, and 
height of three. Therefore, we knew the optimal solution was three, meaning that only 
three units of empty space should be left after the boxes were packed. Either box 1 or 2 
would be packed and then box 3 would also be packed. This simple test case would 
allow us to determine if the constraints were functioning properly and if the formulation 
in general was performing as expected. 

Without constraint (6), the boxes were packed with the correct dimensions. 
Therefore, to simplify the problem and to allow the boxes to be packed in any of their six 
orientations, we did not include constraint (6) in our HYPERLINGO formulation. 

As with any nonlinear code, HYPERLINGO can only find locally optimum 
solutions as opposed to the global optimal solution. Therefore, we forced the program to 
pack either boxes one and three or boxes two and three to ensure it would at least follow 
the packing rules defined by the constraint sets provided in the previous section. The 
coded formulation and the outputted results, which illustrate the boxes were packed 
feasibly, are both shown in Appendix B. 


3-8 





















3.3 Results from GENESIS 


As the pallet dimensions and the number of boxes increase, the three-dimensional 
packing problem gets large and complex and finding a solution requires an unreasonable 
amount of time. To expand the size of the problem we applied a heuristic solution 
technique. We applied a genetic algorithm, using the GENESIS (Genetic Search 
Implementation System) software product. 

Since the variables for this program are binary, the solution sent to the evaluation 
program by GENESIS has a length equal to the number of variables. For this problem, 
the number of variables is equal to the pallet volume times the number of boxes. For the 
simple three box test case, the number of variables sent from GENESIS to the evaluation 
function is equal to 81. 

In order to measure the performance of the genetic algorithm, we applied the 
same test case we used in HYPERLINGO. Penalties were assigned for each constraint 
violation to get the genetic algorithm to converge near the optimal solution. Therefore 
each time a constraint was violated, a penalty was assigned. Testing showed the 
assignment of penalties was critical. 

Appendix C shows the code for the evaluation function we developed. Table 3-2 
shows the final penalties used for each constraint. Table 3-3 shows the genetic algorithm 
parameters used with GENESIS. 


3-9 



Table 3-2: Penalties for Constraint Violations 


Constraint Violation 


Constraint 1 

500 

Constraint 2 

500 

Constraint 3 

500 

Constraint 4 

100 

Constraint 5 

100 

Constraint 6 

100 


Table 3-3: Parameter Setting for the Three Box Test Case 


Parameter 

Setting 


50 

Crossover rate 

0.85 

Mutation rate 

0.01 

Generation gap 

0.9 

Selection strategy 

Elitist 


Using the penalties from Table 3-2 and the parameter settings from Table 3-3, the 
genetic algorithm converged on the optimal solution in less than 200 generations. 
Therefore, a population size of 50 provided enough diversification to force the genetic 
algorithm to converge on the optimal solution. A crossover rate of 0.85 signifies that 
single-point crossover occurs on 85% of all pairs to be mated. A mutation rate of 0.01 
indicates there is a 1% chance a bit will be mutated. Replacing 90% of parent solutions 
with offspring worked best for the generation gap. Lastly, we applied the elitist strategy 
to ensure the best characteristics are maintained from generation to generation. The 
complete input file and solution are shown in Appendix D. 

The second test case, a 3 by 3 by 3 pallet with six different sized boxes, is shown 
in Table 3-4. 


3-10 































Table 3-4: Box Characteristics for the Six Box Test Case 


Box 

Length 

Width 

Height 

Volume 

Adj. Faces 

1 

2 

2 

2 

8 

12 

2 

3 

2 

1 

6 

7 

3 

1 

2 

2 

4 

4 

D 

2 

1 

1 

2 

1 

5 

1 

3 

1 

3 

2 

6 

1 

1 

1 

1 

0 


Since we doubled the number of boxes to be packed, the length of the bit stream 
sent to the evaluation function also doubled. The bit stream consisted of 162 bits. Since 
the volume of all the boxes is 24 and the available packing volume is 27, the optimal 
solution for this problem packs all six boxes and leaves three empty units on the pallet. 

We used the same penalties as those used in the three box problem, but modified 
the genetic algorithm parameters. Table 3-5 shows the parameter settings we used for 
this problem. 


Table 3-5: Parameter Settings for the Six Box Test Case 


Parameter 

Setting 

Population size 

100 

Crossover rate 

0.95 

Mutation rate 

0.01 

Generation gap 

0.9 

Selection strategy 

Elitist 


Since the solution space is larger for this problem, we increased the population 
size to 100. A crossover rate of 0.95 worked best for this problem. The other parameter 
settings remained the same as those used with the three box test problem. The entire input 
file and solution are presented in Appendix D. Using the penalties from Table 3-2 and 
the parameter settings in Table 3-5, the genetic algorithm converged on a solution 75% of 


3-11 











































optimal in 655 generations. The algorithm packed all boxes except for Box 2. Figure 3-3 
shows how the boxes were packed on the pallet. A number inside of a square represents 
that a part of the numbered box is located in that pallet location. 



Figure 3-3: Packing of the Six Box Test Case 


Our third test problem came from an article by Abdou and Arghavani (1996). 

The problem consists of a much larger pallet and eleven boxes. The length of the pallet is 
seven units while the width and height are four units. The characteristics of the eleven 
boxes are shown in Table 3-6. 


Table 3-6: Box Characteristics for the Eleven Box Test Case 


Box 

Length 

Width 

Height 

Volume 

Adj. Faces 

1 

2 

2 

1 

4 

4 

2 

2 

2 

1 

4 

4 

3 

2 

2 

2 

8 

12 

O 

3 

2 

1 

6 

7 

5 

3 

2 

2 

12 


6 

3 

2 

2 

12 


7 

3 

2 

3 

18 

33 

8 

4 

2 

1 

8 

10 

9 

4 

2 

1 

8 

10 

10 

4 

2 

2 

16 

28 

11 

4 

2 

2 

16 

28 ! 


3-12 





































































For this problem, Abdou and Arghavani (1996) were able to pack the pallet with 
100% utilization. The length of the bit stream for this problem was 1,232 bits. Again we 
used the same penalties, but modified the parameter settings. Table 3-7 shows the 
parameter settings used for this problem. 


Table 3-7: Parameter Settings for the Eleven Box Test Case 


Parameter 

Setting 

iBI jSBSBi m 

100 

Crossover rate 

0.85 

Mutation rate 

0.01 


0.9 1 

Selection strategy 

Elitist 


Unfortunately, GENESIS did not show any signs of convergence in a reasonable 
amount of time. The reason for this is that GENESIS only allows for single-point 
crossover, which is too simplistic for a problem with this many variables. Even after 
1,000 generations, which took approximately 45 minutes, the best solution did not even 
come close to resembling a feasible packing for any of the 11 boxes. Appendix D shows 
the complete input file as well as the results found after 1,000 generations. Although 
single-point crossover was effective for the smaller problem sizes, it was ineffective for a 
problem of this magnitude. 

Even for the smaller problem sizes, multi-point crossover is preferred because it 
means more information is exchanged between the parents which leads to quicker 
convergence. We speculate that one potential method for determining the number of 
crossover points is to base it on the number of boxes. 


3-13 














3.4 Summary 

We have developed a mathematical formulation for the three-dimensional pallet¬ 
packing problem and verified the formulation packs boxes correctly in three dimensions. 
Additionally, we successfully applied a genetic algorithm to our formulation. In Chapter 
Five we provide a formal conclusion for this research and recommendations for future 
work. 


3-14 




Chapter 4 - Conclusions and Recommendations 


4.1 Introduction 

We began this research with two objectives. The first objective was to develop a 
direct three-dimensional mathematical formulation for the pallet-packing problem. The 
second objective was to verify that the formulation correctly packed boxes onto a pallet. 
This verification included the development of a test problem to ensure the constraints 
caused the proper packing of the pallet. 

In addition to meeting these objectives, we expanded the research to include the 
application of a heuristic solution approach. We attempted to use a genetic algorithm to 
determine if it was an effective tool which could be used to produce close-to-optimal 
feasible solutions. 

In this chapter we discuss the results of the research and provide 
recommendations for future research in this area of study. We close this chapter with our 
final thoughts on this research topic. 

4.2 Research Results 

In our literature review of research accomplished on packing problems, we found 
only a minority of the research pertained to the three-dimensional pallet-packing 
problem. 

Although most articles contained some of the necessary constraints for the Air 
Force’s three-dimensional pallet-packing problem, none contained a formulation 


4-1 


including all the required constraints. The article by Abdou and Arghavani (1996) was 
the most helpful in our initial formulation. 

The objective of our formulation was to minimize the amount of unpacked space 
on the pallet. Three of the constraints included in the formulation ensure that each box is 
packed with the correct volume and the correct dimensions. The link boxes constraint as 
well as the box dimensions constraint work together to ensure each box is packed with 
the proper dimensions. To determine the number of adjacent faces for each box when it 
is broken down into cubic units, we developed a formula which calculates the number of 
adjacent faces among the unit cubes for each box based on that boxes length, width and 
height. 

Two of the other constraints included in the formulation ensure each box has a 
foundation on which to be placed and that at most only one box can occupy each location 
on the pallet. The last constraint ensures the volume of all the packed boxes does not 
exceed the available pallet volume. Although these are not all the constraints required for 
the Air Force pallet-packing problem, using an optimal solver, we were able to show 
these constraints correctly pack boxes in three dimensions on a pallet. 

Due to the complexity of the problem, we applied a genetic algorithm to our 
formulation. From the test cases, we concluded that genetic algorithms could be 
effectively used to find good feasible solutions to packing problems. Unfortunately, as 
the problem size increased, the solution quality decreased. We feel single-point 
crossover and the penalty functions are the two areas preventing the genetic algorithm 
from converging on better solutions for larger problems. 


4-2 



4.3 Recommendations for Future Research 


Since we successfully applied a genetic algorithm to small test problems, further 
research should examine genetic algorithm application to larger problems. A genetic 
algorithm program which allows for multi-point crossover should be examined on larger 
more realistic problems to ultimately determine whether a genetic algorithm can find 
close-to-optimal feasible solutions for large, realistically sized problems. 

If the genetic algorithm continues to provide poor results, either simulated annealing or 
tabu search should be investigated as possible heuristic solution techniques that could be 
applied to packing problems. 

In addition to further examining heuristic solution techniques, the formulation 
should be expanded to include more of the necessary constraints required to pack Air 
Force 463L pallets. The first characteristic that must be included is the weight of the 
boxes. One constraint associated with weight ensures the total weight of all the boxes 
packed is less than the maximum allowable weight for the pallet. Another constraint 
ensures the heavier boxes are packed below the lighter boxes. A third constraint ensures 
each box is not crushed. This constraint ensures the total weight of all the boxes packed 
on top of a box does not exceed the maximum allowable weight that can be packed on 
that box. For safety reasons, a fourth constraint ensuring the center of gravity of the 
packed boxes is within four inches of the middle of the pallet is required by the Air 
Force. Another constraint to add, not pertaining to weight, ensures the top of the packing 
is as smooth as possible. Therefore, when the cargo net is thrown over the load, it will 
securely hold the boxes in place. 


4-3 


4.4 Final Thoughts 

The Air Force has spent a lot of time and effort searching for a model which will 
more efficiently pack pallets. There is good reason for this as improved pallet utilization 
will cut costs and free additional time and resources. However, this is a very complex 
problem, and a heuristic solution approach is necessary to find a solution in a reasonable 
amount of time. Unfortunately, a major drawback of applying a heuristic is that it does 
not guarantee the optimal solution. However, it is the belief of the researcher that as 
more and more research is performed on heuristic solution approaches, a heuristic 
solution approach will be found for the three-dimensional pallet-packing problem that 
produces close-to-optimal, feasible solutions. 


4-4 



Appendix A-Annotated Bibliography 


Abdou, G., and M. Yang. “A systematic approach for the three-dimensional 
palletization problem,” International Journal of Production Research 32 ; 2381-2394 
(1994). 

The authors develop a multi-objective algorithm for the palletization problem. 
They attempt to maximize both pallet utilization and stability. Not many of the 
algorithms developed for this type of problem include stability as an objective. For the 
Air Force, stability is a necessity. The authors discuss the five factors that affect 
palletization: box size, box weight, box orientation, box density (stability), and box 
availability. They attempt to simplify the problem by assuming boxes with different base 
dimensions are grouped by the same height. 

The authors develop blocks which are subsets of the actual pallet. They try to 
maximize the space within each block, by either filling it with a large box or with several 
smaller boxes. As expected, when new blocks are generated, the criteria is to use boxes 
that have not been previously selected, use the bigger boxes first, and lastly use as few 
boxes as possible. This is important since it will make it easy to pack the next layer. By 
packing the larger boxes first, either the volume of the block will be filled, or the larger 
boxes provide a good foundation for the boxes placed above them. 

This algorithm has many features required by the Air Force. However, the 
authors note that expanding its capability so that boxes cannot by grouped by similar 
height and have different base dimensions is an area for improvement. 


A-l 




Abdou, G., and J. Arghavani. “Interactive ILP procedures for stacking 
optimization for the 3D palletization problem,” International Journal of Production 
Research 35 :1287-1304 (1997). 

The authors develop an algorithm that first maximizes the utilization of the base 
area and then attempts to maximize the stacking height of each sub area. The authors 
note that a limitation of this problem is high computational times, which limits the 
complexity of the models. Thus, the authors attempt to expand on a two-dimensional 
model so that it can be applied in the third dimension. 

The authors acknowledge future research needs to be done to increase the 
capability of their model. The model does not address stability, and the model does not 
allow for a stochastic arrival of boxes with different dimensions. Lastly, possible 
modifications or better rules may be applied to the algorithm to aid in the heuristic 
procedure used. 

Askin, Ronald G., and Charles R. Standridge. Modeling and Analysis of 
Manufacturing Systems . New York: John Wiley and Sons, Inc., 1993. (320-321) 

The author describes two types of pallet packing problems. He first details the 
Manufacturer’s pallet packing problem. This problem deals with loading boxes of the 
same dimensions. He next describes the Distributor’s pallet-packing problem. This is 
more complex and involves boxes of different dimensions. This is the problem facing the 
Air Force and as the author states is very similar to the bin-packing and cutting stock 
problems. 

“Astrokettle Algorithms.” http://www4.bcity.com/astrokettle/data.html . 29 July 
1999. 

This article provides algorithms for the three-dimensional bin-packing problem. 

It also provides a demonstration for the bin-packing problem illustrating how effective 


A-2 


their current algorithm is at finding a good solution. Again, there is a concern on how the 
program takes the weight of the boxes into account and how good of a solution is the 
program really finding. Thus, for the program to be useful for the Air Force, these 
questions need to be addressed. 

Bischoff, E. E., F. Janetz, and M. S. W. Ratcliff. “Loading pallets with non-identical 
items,” European Journal of Operational Research 84 : 681-692 (1995). 

The authors develop a three-dimensional heuristic approach to packing multiple¬ 
sized boxes onto a pallet. This problem is known as the ‘Distributors Pallet Packing 
Problem.’ The objective for their algorithm is to maximize pallet utilization while 
ensuring that the load is stable. Unlike the bin-packing problem where there are vertical 
walls ensuring the packing is stable, the packing on a pallet must be inherently stable to 
ensure the boxes don’t topple. Additionally, the algorithm packs the boxes from the 
bottom upwards using single layers of up to two different box types at a time. 

The algorithm attempts to pack the layers where vertical dimensions are the same. 
Additionally, the algorithm favors a layer in which one type of box can cover the entire 
layer. Also, larger gaps between boxes are favored over smaller ones in hopes a box 
might be able to fill the vacancy. The authors found that using the layering approach is 
beneficial in terms of achieving stability whereas other algorithms that attempt to pack 
columns are generally unstable. Also, with more box types the packing utilization 
decreased since it was more difficult for the algorithm to form layers with the boxes. 

Overall I felt this was a good layered approach to the problem even though there 
was nothing more than an explanation of their algorithm. Lastly, the authors did add a 
merging criteria to their algorithm to prevent fragmentation. Even though this may have 


A-3 



added to the content in the article it seemed to me to add very little to the quality of the 
solution found. 

Bischoff, E. E., and M. S. W. Ratcliff. “Loading Multiple Pallets,” Journal of the 
Operational Research Society 46 :1322-1336 (1995). 

This paper focuses on the ‘Distributors Pallet Packing Problem’ and is mostly 
concerned with packing multiple pallets at a time. However there is a small portion of 
the article that is concerned with packing only one pallet at a time. Packing stability is 
addressed in this paper and the underlying algorithm used is the single-pallet algorithm 
by Bischoff. Unfortunately, this article packs the boxes on the pallet using a semi- 
layered approach. It tries to back boxes that have equivalent dimensions first to get them 
the same height. The author found when packing the multiple pallets sequentially as 
opposed to simultaneously the algorithm produced better utilization. He also found that 
with single-pallet packing a better utilization is found when there are fewer box sizes that 
need to be packed. 

Chen, C. S., S. Sarin, and B. Ran. “The pallet packing problem for non-uniform 
box sizes,” International Journal of Production Research 29 : 1963-1968 (1991). 

The authors develop an algorithm minimizing the number of pallets required to 
pack boxes of non-uniform size. The algorithm takes into account box orientation and 
allows the size of boxes to be non-integer. The formulation is for the two-dimensional 
case and according to the authors does find the optimal packing. The constraints in the 
formulation ensure there is no overlap among the boxes, every box is placed on the pallet, 
and that each box is placed within the confines of the pallet. 


A-4 




Dowsland, Kathryn A. “An exact algorithm for the pallet loading problem,” 
European Journal of Operational Research 31 : 78-83 (1987). 

The author develops an algorithm for the ‘manufacturers pallet loading problem.’ 

The problem is reduced to the two dimensional problem of packing identical rectangles 

onto a larger containing rectangle. The author concedes that this problem is NP-complete 

and that most of the emphasis has been on finding good heuristic solution. The author 

uses a graph-theoretic model of the problem, but found that the problem becomes too 

large to use this method directly. She provides some problem reduction techniques 

allowing the problem to become more manageable. The information in this paper does 

not appear to be very applicable to the three-dimensional packing problem. 

Dowsland, Kathryn A., and William B. Dowsland. “Packing problems,” European 
Journal of Operational Research 56 : 2-14 (1992). 

Most of this article is spent describing the different types of packing problems and 
the constraints found in those problems. They begin with the two-dimensional 
rectangular packing problems. The authors state that the problem lends itself to dynamic 
programming, however they go on to state that the problem is generally formulated as an 
integer programming problem where there is one binary variable for each possible 
position for a piece on the pallet. They describe the pallet-loading problem, packing 
identical sized boxes, as well as the bin-packing problem. The bin-packing problem is 
similar to the pallet-packing problem however with the bin-packing problem there are 
vertical columns which provide vertical stability. 

The authors then dive into the three-dimensional packing problem and state that 
the increased combinatorial complexity over the two-dimensional case means that exact 
solutions are unlikely to be found. Also, when moving to the third dimension load 


A-5 



stability becomes an issue and has been found to be difficult to formulate. Lastly, due to 
the complexity of moving to the third dimension it becomes increasingly difficult to 
check the feasibility of a solution by eye. 

Dowsland, Kathryn A. “Some experiments with simulated annealing techniques for 
packing problems,” European Journal of Operational Research 68 : 389-399 (1993). 

The first part of the article is concerned with the classical pallet loading problem, 
packing identical rectangles into a larger containing rectangle. The second part of the 
article is concerned with the packing of non-identical pieces into a larger containing 
rectangle. For both parts the author was working on the two-dimensional case. 

Generally with the packing of identical items the objective function attempts to maximize 
the number of boxes packed, whereas with the packing on non-identical items the 
objective function attempts to minimize wasted space. 

The paper describes the simulated annealing process for both types of problems in 
good detail making it pretty easy to follow and understand. Unfortunately for the non- 
uniform box size case the annealing process often produced infeasible solutions. The 
author found that after a good feasible solution was found the process would move away 
from that solution to a worse solution. The author concluded that simulated annealing 
could be a good solution technique for this problem if a few changes were made to the 
algorithm she developed. 

Dowsland, William B. “Three-dimensional packing—solution approaches and 
heuristic development,” International Journal of Production Research 29 : 1673- 
1685 (1991). 

Much of the work concerning the pallet-packing problem has been done in two 
dimensions. The author attempts to look at the third dimension and how heuristic 
methods can be improved to provide better results. Additionally, he looks at the 


A-6 



possibility of expanding the two-dimensional heuristics so that they can be used in the 
three-dimensional packing problems. Unfortunately when looking at the third dimension 
the level of complexity increases dramatically and constraints such as load stability make 
it difficult to expand heuristics designed for the two-dimensional cases into the third 
dimension. 

The author states that research on the three-dimensional packing problem is still 
in its early stages, thus most of the research states successful implementation, yet fails to 
show proof of scientific success. The author spends a lot of time discussing the wall 
building approach in which the pallet is filled in from the sides. However he discusses 
some of the troubles associated with this approach. The main concern was the lack of 
load stability which is a major concern of the Air Force. Additionally, he states that it is 
generally good packing practice to build a load up from the base of the pallet. Overall, 
this article provided good insight especially regarding the lack of transferability of the 
two-dimensional heuristics to the three-dimensional case. 

Dowsland, W. B. “Improving palletisation efficiency—the theoretical basis and 
practical application,” International Journal of Production Research 33 : 2213-2222 
(1995). 

The basis of the article is the “manufacturers” pallet-loading problem in which the 
goal is to maximize the number of identical sized boxes onto a pallet. The goal of the 
paper was to determine the potential benefits of modifying the box sizes by some fixed 
percentage, either maintaining constant box volume or giving a slightly smaller box 
volume. The author tested this hypothesis with set percentage change, thus the paper 
does not answer the question, ‘What volumetric change is needed to provide an 


A-7 



improvement?’ The research is interesting but does not pertain to the actual packing of 
the boxes onto the pallet. 

Fuh-Hwa, F. Liu and C-J Hsiao. “A three-dimensional pallet loading method for 
single-size boxes,” Journal of the Operational Research Society 48 : 726-735 (1997). 

The author addresses the packing of single-sized boxes onto a single pallet trying 
to maximize utilization while maintaining stability. It allows the boxes to be packed in 
any of the six orientations. However, this article uses the layered approach to pack the 
boxes. Thus once one box is packed a certain way, then the other boxes in that layer are 
also packed that same way so that they have the same height throughout the layer. The 
author does use LINDO to solve his problems. 

In this paper the algorithm does not allow boxes to be packed if they will not be 

stable. Most algorithms that address stability wait until a layer is packed and then check 

to see if stability is met. If it is then good, if not then that packing is thrown out. 

Han, Ching Ping, Kenneth Knott, and Pius J. Egbelu. “A heuristic approach to the 
three-dimensional cargo-loading problem,” International Journal of Production 
Research 27 : 757-774 119891. 

The authors develop a heuristic approach to the three-dimensional packing 
problem. This article is concerned with single-sized boxes. The packing is accomplished 
by packing the boxes so that one of the edges of each box is initially placed along a 
vertical edge of the pallet. Additionally, the third dimension is approached using the 
layered approach. Thus, the algorithm tries to find the correct orientation of the box to 
both maximize utilization and maximize the number of boxes packed. 


A-8 


Healy, Patrick, Marcus Creavin and Ago Kuusik. “An optimal algorithm for 
rectangle placement,” Operations Research Letters 24 : 73-80 (1999). 

The author approached this problem as the cutting stock problem, when no 
overlapping is feasible. The bottom-left heuristic technique for placing boxes is used to 
increase the speed of the solver. This paper focuses on a two-dimensional problem and is 
closely related to the largest empty rectangular problem. Thus, after a box has been 
placed, depending on which bottom-left location is chosen, the program searches for the 
largest empty area and tries to find a box that will best fill that area. 

This article emphasizes the two-dimensional case. However, the author claims 
this formulation can easily be extended into the third dimension. Instead of just sweeping 
the width and the depth of the boxes, one would also need the sweep the height. Again, 
the problem with this is the explosion of variables and complexity required to include the 
third dimension. 

Herbert, Edward A. and Kathryn A. Dowsland. “A family of genetic algorithms for 
the pallet loading problem,” Annals of Operations Research 63 : 415-436 (1996). 

The authors develop a generic algorithm that can be applied to the two- 
dimensional pallet-packing problem. The authors explain that this problem requires 
binary coding and is a NP-Hard problem. Their algorithm allows the initial packing to be 
infeasible and then works toward a feasible solution. Although the initial packing may 
not be feasible, the algorithm sufficiently penalizes this to drive the algorithm back to 
feasibility. The objective of the algorithm is to pack the maximum number of boxes onto 
the pallet while avoiding overlap. The authors conclude that although their algorithm is 
not able to compete with traditional heuristic solution methods, they do suggest that such 
an approach could prove fruitful for more complex problems. 


A-9 



Ivancic, N., Kamlesh Mathur, and Bidhu B. Mohanty. “An Integer Programming 
Based Heuristic Approach to the Three-dimensional Packing Problem,” Journal of 
Manufacturing and Operations Management 2 : 268-298 (1989). 

The authors develop a three-dimensional packing algorithm. They are attempting 
to minimize cost, where cost is essentially equivalent to maximizing the utilization of the 
total packing. Their work focuses on loading multiple containers whereas my research is 
focused on the loading of a single pallet at a time. However, they do perform some test 
instances where they are only loading one container. To aid in the solution the authors 
employ a greedy heuristic search for the “biggest bang for the buck.” Unfortunately to 
apply this heuristic requires knowledge of all the packing patters which can be 
computationally prohibitive. The heuristic is used in two steps: first determining a 
packing pattern for a container and then choosing the next box to pack. 

Their algorithm is set up so that boxes of which there are more left and with 
smaller volume are more likely to be packed. 

Manship, Wesley E., and Jennifer L. Tilley. A Three-Dimensional 364L Pallet 
Packing Model and Algorithm . MS thesis, AFIT/GIM/LAL/98S-3. School of 
Systems and Logistics, Air Force Institute of Technology (AU), Wright-Patterson 
AFB, OH, September 1998. 

The focus of this thesis is to explain the background of the pallet-loading problem 
and provide information on many of the existing models. They go into great detail on the 
background information and why this is such an important issue for the Air Force. They 
look at some of the different algorithms that have been used in attempting to solve this 
problem. In addition, the authors suggest a non-linear algorithm that can be used to assist 
in the pallet loading process. 


A-10 



The authors built a model consisting of three different components to handle the 

different areas of the pallet-packing problem. The first component dealt with hazardous 

cargo since they found that this often is a cause for re-packing the pallets. The next 

component of the model helps limit the candidate list of boxes that may fit on the pallet. 

This aids in the manageability of the problem. The last component of the model focuses 

on putting the actual boxes onto the pallet. They use a nonlinear objective function to 

load the boxes as tightly as possible. The authors mention one difficult aspect of the 

problem is determining with constraints and variables to include in the model. The 

models in this thesis provide feasible, but sub-optimal solutions. 

Morabito, R. and S. Morales. “A simple and effective recursive procedure for the 
manufacturer’s pallet loading problem,” Journal of the Operational Research 
Society 49 : 819-828 (1998). 

The focus of the paper is the packing of uniform sized boxes, the 
“manufacturer’s” problem. Additionally, the authors implemented the face-up principal 
which allows the boxes to be packed only one of two ways. Basically the problem is 
broken up into two smaller problems. The first problem is to determine how many boxes 
can be placed on a layer and then the second problem determines how many layers to 
pack. The authors also ignore all constraints related to weight, density, and fragility. 

The authors use a depth-first tree search method to find the best packing for a 
particular problem. Only in 18 of the more than 20,00 problems was the algorithm 
unable to find the optimal packing. The authors developed two different algorithms to 
find the best packing. One of the algorithms was much quicker but did not perform as 
well on the whole. 


A-ll 


“PowerPack™ 6 Easy Steps to Lower Freight Costs.” 
http://www.remarkable.co.nz/prod04.htm . 29 July 1999. 

This article describes a three-dimensional packing software that allows for 
different size boxes with different attributes be loaded into the program. The program 
then determines the optimal packing of boxes onto the pallet to minimize empty space, 
and lastly prints the solution for the user. Some concerns I have with this product are 
how the weight of the boxes is factored into the problem and if there are limitations on 
the pallet size. Since the Air Force has weight limitations on its cargo and a center of 
gravity requirement, for a software package to be useful these things must be included. 
Secondly, most algorithms that attempt to solve this problem deal with pallets much 
smaller than what the Air Force uses, thus it is important this software is able to solve the 
problem using the 463L pallet size. Also, it does not say anything about the limitation on 
the number of boxes that can be loaded into the program for each problem. The cost of 
this software is only $995. 

Pisinger, David. “David Pisinger’s optimization codes.” 
http://www.diku.dk/~pisinger/codes.html . 29 July 1999. 

This article describes an algorithm in C-code that solves three-dimensional 
packing problems either as a heuristic or to optimality. The code as expected is quite 
lengthy, but could be used as a possible foundation in my thesis. One limitation for this 
code is that it does not allow the boxes to be rotated in any direction. Most algorithms 
allow boxes to be rotated 90° around the vertical axis, however by rotating the boxes, a 
lot of complexity is introduced. Thus, this may be one area where the code can be 
improved to increase its capabilities. 


A-12 


Romaine, Jonathan M. Solving the Multidimensional Multiple Knapsack Problem 
with Packing Constraints Using Tabu Search . MS thesis, AFIT/GOR/ENS/99M-15. 
Graduate School of Engineering, Air Force Institute of Technology (AU), Wright- 
Patterson AFB, OH, March 1999. 

This thesis approaches the pallet-packing problem in two-dimensional space, 
however it allows for modifications to include the third dimension. Due to the solution 
time required to solve the problem the author employs Tabu search coded in JAVA to 
efficiently determine the best solution. Three approaches are used in loading the pallets. 
The first method is loading the pallets for the first plane before even thinking about the 
next plane. The next strategy is that each aircraft in the fleet is feasible and packable at 
thesame time. The last strategy is that only one plane needs to be feasible and packable 
at a time. The last strategy provided the best solutions. Adding a third dimension to the 
model would make the model more realistic and allow one to take into account height 
restrictions. 

Scheithauer, Guntram and Johannes Terno. “The G4-Heuristic for the Pallet 
Loading Problem,” Journal of the Operational Research Society 47 : 511-522 (1996). 

The authors use this G4-heuristic to pack single-sized boxes in two dimensions. 
Thus this paper focuses on the ‘Distributor’s Problem’. They claim that this heuristic 
finds solutions at least as good as any other heuristic to date. Their presentation of their 
algorithm is very confusing and hard to follow. In addition I do not feel this article will 
be very helpful with my formulation since it is only concerned with two dimensions and 
it is only packing single-sized boxes. 


A-13 






Taylor, Gregory S. A Pallet Packing Postprocessor for the Logistics Composite 
Model . MS thesis, AFIT/GST/ENS/94M-11. Graduate School of Engineering, Air 
Force Institute of Technology (AU), Wright-Patterson AFB, OH, March 1994. 

This paper provides an excellent description of the current problems with pallet 
packing in the Air Force and the needs for an algorithm that will enable the Air Force to 
better utilize pallet space to save money on airlift. The difficulty of the problem stems 
from the fact that this is the distributor’s problem meaning there are multiple box sizes 
that need to be loaded. The author explains that the main constraining factor in the 
pallet-packing problem is the volume. Pallet space is usually used up before the weight 
constraint becomes a factor. 

The author defines three models in the thesis. The objective function in the first 

model minimizes the maximum deviation in height of all the boxes. The second model 

both maximizes area coverage and minimizes deviation in heights. The third model, 

which was not tested in the paper, is based on model two except it minimizes the wasted 

volume for all of the packed boxes. The paper emphasizes the complexity of file 

problem. This paper does not take into account the center of gravity constraint, which 

requires a majority of the weight be in the center of the pallet. 

Tsai, R.D., E.M. Malstrom, and W. Kuo. “Physical Simulation of a Three 
Dimensional Palletizing Heuristic,” International Journal of Production Research 
32:1159-1171 (1994). 

The authors develop a three-dimensional heuristic to maximize the pallet load. 
Since, this problem is NP-Hard a heuristic is imposed to reduce computational time so 
that a close to optimal solution will be reported. They model this problem with four 
different size boxes arriving randomly to the loading dock. Once to the loading dock the 
critical path method was used to determine the placement and sequence of the boxes. For 


A-14 



example, for a box to be placed on another box there must be a solid, uniform foundation 
to place the box. It is not allowed to overhang. 

The authors simplify the problem by only using four different box sizes. In 

addition, although the technique may be transferable to the problem I am attacking, the 

idea is different. The authors have developed this model to pack boxes arriving on a 

conveyor belt as opposed to loading boxes already at the loading site. 

Tsai, R.D., E.M. Malstrom, and W. Kuo. “Three Dimensional Palletization of Mixed 
Box Sizes,” HE Transactions 25 : 64-74 (1993). 

The authors develop a model that generates exact optimal solutions in terms of 
volume utilization of the pallet. Due to computational limits this model is limited in the 
size of problems that it can solve. The authors do not place any restrictions on the box 
sizes, the pallet sizes, or the allowable number of different sized boxes. However, the 
model does not address the issue of load stability when determining where to pack the 
boxes. Additionally this model was developed for the individual pallet case, thus the 
objective is not to minimize the number of pallets required to fit the boxes. Lastly, the 
model only allows the boxes to be packed in one of two ways. They are allowed to rotate 
90° around the vertical axis. 

However, the model does ensure no two boxes on the pallet overlap, as well as 
ensure that each box is placed completely within the confines of the pallet. Once a 
solution has been found the model outputs the exact placement of a box on a pallet. 
Unfortunately since this is an NP-Hard problem as the number of boxes increases the 
computation time required to find the optimal solution increases limiting the practical use 
of this model. 


A-15 



Appendix B - LINGO Formulation 


B.l LINGO Formulation 

To verify that the mathematical formulation we developed for the three- 
dimensional pallet-packing problem performed correctly, we input the formulation into 
LINGO. In this appendix we break down the formulation into segments and describe in 
detail the purpose of each segment. Then we provide the results of the formulation and 
describe in detail their significance. First, we have provided a list and description of each 
variable used in the formulation. 


VOLUME(x) 


PACK(x) 


B(ijkx) 


E 


The variable represents the volume for each of the 
three boxes. The volume of each box is initialized 
at the end of the program 

This is a binary variable which represents whether 
Box x is packed or not 
0 = box is not packed 

1 = box is packed 

This is a binary variable which represents whether 
box x is packed in pallet location i, j, k where x, i, j, 
and k all go from 1 to 3 for this problem 
0 = box x is not packed in location i, j, k 
1= box x is packed in location i, j, k 

The amount of unused pallet space after the boxes 
are packed 


B-l 



B.2 Model Initialization and Objective Function 

This part of the formulation initializes all the variables and defines the number of 
boxes, and the length, width, and height of the pallet to be three. Since this is the 
beginning of the formulation a brief description of the model is presented within the 
code. After the variables have been initialized within the SETS routine, the objective 
function value is defined. It is obvious that we are attempting to minimize unpacked 
pallet space. Lastly, after the objective function value is defined we declare variable 
PACK(x) and variable B(ijkx) to be binary variables. 


MODEL: 

! Description: This formulation packs rectangular boxes; 

! on a pallet in three dimensions; 

! Both the variables B and Pack are binary variables; 

SETS: 

BOXES/1..3/: VOLUME,PACK; 

PALL/1..3/; 

PALW/1..3/; 

PALH/1..3/; 

PACKAGE(PALL, PALW, PALH, BOXES): B; 
ENDSETS 

! The objective function attempting to minimize empty space; 
! E is empty space; 

[MIN] MIN - E; 

@FOR(BOXES(X): @BIN(PACK(X))); 
@FOR(PACKAGE(IJ,K,X): @BIN(B(IJ,K,X))); 


B-2 


B.3 First and Second Constraints 


Each of these constraints are well commented within the coding of the model. 
The first constraint is a nonlinear constraint which determines the amount of unpacked 
space on the pallet. The second constraint is actually a set of constraints where the 
number of constraints is equal to the number of boxes to be packed. For this problem, it 
is a set of three constraints. As the comment within the code describes the constraint 
ensures that each box is packed with the correct volume. 


/ First constraint attempts to find the amount of space left unpacked; 
! This ensures the packed box volume is less than the available; 

! pallet volume; 

@SUM(BOXES(X): VOLUME(X)*PACK(X)) + E = 27; 


! This set of constraints ensure that the boxes are; 
! packed with the correct box volume; 


@FOR( BOXES(X): 
@SUM(PALL(I): 

@SUM( PAL W(J): 
@SUM( PALH(K): 
B(IJXX) 

) 

) 

) = VOL UME(X) *PA CK(X) 

); 


B-3 


B.4 Third and Fourth Constraints 

Again the function of each of these two constraints is commented into the code. 
The first constraint below is also a set of constraints where the number of constraints in 
the set is equal to the volume of the pallet. For this problem the number of constraints in 
this set is equal to 27. The second constraint of this page is also a set of constraints 
where the number of constraints in the set is equal to: 

L*W*(H-l) where L = length of pallet 
W - width of pallet 
H = height of pallet 


! This set of constraints ensure no two boxes occupy; 

! the same space; 

@FOR( PALL (I): 

@FOR( PALW(J): 

@FOR ( PALH(K): 

@SUM( BOXES(X): 

B(I,J,K,X) 

;<=7 

); 

! This set of constraints ensure a box is packed on top of; 

! another box; 

! Each box must have a complete foundation for it to be packed; 

@FOR (PALL(I): 

@FOR (PALW(J): 

@SUM(BOXES(X): 

B(I,J,1,X) - B(I,J,2,X))>= 0)); 

@FOR (PALL(I): 

@FOR (PALW(J): 

@SUM(BOXES(X): 

B(I,J,2,X) - B(I,J,3,X) ) >= 0)); 


B-4 



B.5 Constraint Five 


This constraint is well described by the comments within the code. The constraint 

for box 3 did not fit on this page and is located on the following page. Since LINGO 

does not converge on the globally optimal solution for nonlinear formulations we had to 

assign boxes two and three to the packing otherwise it did not come up with the globally 

optimal solution and we were unable to check if the constraints were being violated. 

/ The last set of constraints ensure that the boxes are packed; 

! with the correct dimensions; 

! This ensures that the number of adjacent faces for each; 

! box is the correct number of adjacent faces for that box; 

! This assigns boxes 2 and 3 to the packing; 

!PACK( 1) = 1; 

PACK( 2) = 1; 

PACK( 3) = 1; 

’.Box 1; 

@SUM(PALL(I): 

@SUM (PALW(J): B(I,J,1,1)*B(I,J,2,1)+B(I,J,2,1)*B(I,J,3,1))) 

+ 

@SUM (PALL(I): 

@SUM (PALH(K): B(I,1,K,1)*B(1,2,K,1)+B(I,2,K,1)*B(I,3,K,1))) 

+ 

@SUM (PALW(J): 

@SUM (PALH(K): B(1,J,K,1)*B(2,J,K,1)+B(2,J,K,1)*B(3,J,K,1))) 

- (PACK(1)*33) = 0; 


IBox 2; 


@SUM (PALL(I): 

@SUM (PALW(J): B(I,J,1,2)*B(I,J,2,2)+B(I,J,2,2)*B(I,J,3,2))) 

+ 

@SUM (PALL(I): 

@SUM(PALH(K): B(I,1,K,2)*B(I,2,K,2)+B(I,2,K,2)*B(I,3,K,2))) 

+ 

@SUM (PALW(J): 

@SUM(PALH(K): B(1,J,K,2)*B(2,J,K,2)+B(2,J,K,2)*B(3,J,K,2))) 
- (PACK( 2)*33) = 0; 


B-5 



!Box 3; 


@SUM (PALL(I): 

@SUM (PALW(J): B(I,J,1,3)*B(I,J,2,3)+B(I,J,2,3)*B(I,J,3,3))) 

+ 

@SUM (PALL(I): 

@SUM (PALH(K): B(I,1,K,3)*B(I,2,K,3)+B(I,2,K,3)*B(I,3,K,3))) 

+ 

@SUM (PALW(J): 

@SUM (PALH(K): B(1,J,K,3)*B(2,J,K,3)+B(2,J,K,3)*B(3,J,K,3))) 
- (PACK( 3)*7) = 0; 


B.6 End of Program 

As described in the comments this is where the volume of each box is initialized; 
right before the end of the program. 


/ Data required for the problem; 
DATA: 

VOLUME= 18, 18, 6; 
ENDDATA 
END 


B-6 



B.7 Results when Boxes One and Three are Packed 

The output from LINGO when boxes one and three are packed is shown below. 
The objective function value is three which we know to be the optimal solution for this 
problem. Additionally, PACK(l) and PACK(3) are equal to one which reemphasizes that 
boxes one and three are packed in the solution while PACK(2) equals zero. Lastly, the 
long columns under each box illustrates where each box is packed. As we would expect 


the entire column is zero for 
constraints. 


Objective value: 

Variable 

E 

PACK( 1) 
PACK( 2) 
PACK( 3) 

Box 1 

B( 1,1, 1,1) 0.0000000 

B( 1,1, 2,1) 0.0000000 

B( 1,1, 3,1) 0.0000000 

B( 1,2, 1,1) 0.0000000 

B( 1,2, 2,1) 0.0000000 

B( 1, 2, 3,1) 0.0000000 

B( 1,3, 1,1) 0.0000000 

B( 1,3, 2,1) 0.0000000 

B( 1,3, 3,1) 0.0000000 

B( 2,1,1,1) 1.000000 

B( 2,1,2,1) 1.000000 

B(2,1,3,1) 1.000000 

B( 2, 2, 1,1) 1.000000 

B( 2, 2, 2, 1) 1.000000 

B( 2, 2, 3, 1) 1.000000 

B(2,3, 1,1) 1.000000 

B( 2, 3, 2, 1) 1.000000 

B( 2, 3, 3,1) 1.000000 


Box 2. Also, we found Boxes 


3.000000 

Value 

3.000000 

1.000000 

0.0000000 

1.000000 

Box 2 

B( 1,1,1,2) 0.0000000 

B(l, 1,2,2) 0.0000000 

B( 1,1, 3, 2) 0.0000000 

B( 1,2,1,2) 0.0000000 

B( 1, 2, 2, 2) 0.0000000 

B( 1,2, 3, 2) 0.0000000 

B( 1,3, 1,2) 0.0000000 

B( 1, 3, 2, 2) 0.0000000 

B( 1, 3, 3,2) 0.0000000 

B(2,1,1,2) 0.0000000 

B( 2,1,2,2) 0.0000000 

B( 2,1,3,2) 0.0000000 

B(2,2,1,2) 0.0000000 

B( 2, 2, 2, 2) 0.0000000 

B( 2, 2, 3, 2) 0.0000000 

B(2,3,1,2) 0.0000000 

B( 2, 3, 2, 2) 0.0000000 

B( 2,3, 3,2) 0.0000000 


1 and 3 do not violate any 


Box 3 

B( 1,1,1,3) 1.000000 

B( 1,1,2, 3) 1.000000 

B( 1,1,3, 3) 1.000000 

B( 1,2,1,3) 1.000000 

B( 1,2,2, 3) 1.000000 

B( 1,2, 3, 3) 1.000000 

B( 1,3,1,3) 0.0000000 

B( 1, 3, 2, 3) 0.0000000 

B( 1,3,3, 3) 0.0000000 

B( 2,1,1,3) 0.0000000 

B( 2,1,2,3) 0.0000000 

B( 2,1,3,3) 0.0000000 

B( 2,2,1, 3) 0.0000000 

B( 2, 2,2, 3) 0.0000000 

B( 2, 2, 3, 3) 0.0000000 

B(2,3,1,3) 0.0000000 

B( 2, 3,2, 3) 0.0000000 

B( 2,3,3, 3) 0.0000000 


B-7 



B( 3, 1,1, 1) 1.000000 B( 3, 1,1, 2) 0.0000000 B( 3, 1,1, 3) 0.0000000 

B( 3,1,2,1) 1.000000 B( 3,1,2,2) 0.0000000 B( 3, 1,2,3) 0.0000000 

B(3,1,3,1) 1.000000 B( 3,1,3,2) 0.0000000 B( 3,1,3,3) 0.0000000 

B( 3,2,1,1) 1.000000 B( 3,2,1, 2) 0.0000000 B( 3,2,1, 3) 0.0000000 

B( 3,2, 2, 1) 1.000000 B( 3, 2, 2, 2) 0.0000000 B( 3, 2, 2, 3) 0.0000000 

B( 3,2, 3,1) 1.000000 B(3,2,3,2) 0.0000000 B( 3,2, 3, 3) 0.0000000 

B( 3, 3,1,1) 1.000000 B(3,3,1,2) 0.0000000 B(3,3,1,3) 0.0000000 

B( 3, 3, 2, 1) 1.000000 B( 3, 3, 2, 2) 0.0000000 B( 3, 3, 2, 3) 0.0000000 

B( 3,3,3, 1) 1.000000 B(3,3,3,2) 0.0000000 B(3,3,3,3) 0.0000000 


B.8 Results when Boxes Two and Three are Packed 

As expected the objective function value when Boxes 2 and 3 are packed equals 
3. Also, we can see that PACK(l) equals zero while the other two boxes equal 1. 
Lastly, the columns for each box, illustrating where each box is packed, shows that we 
again have a feasible packing. 


Objective value: 3.000000 


Variable 

Value 





E 

3.000000 




PACK( 1) 

0.0000000 




PACK( 2) 

1.000000 




PACK( 3) 

1.000000 




Box 1 

Box 2 


Box 3 

B( 1,1, 1,1) 

0.00000000 

B( 1,1,1,2) 

1.000000 

B( 1,1,1,3) 

0.0000000 

B( 1, 1, 2, 1) 

0.0000000 

B( 1, 1, 2, 2) 

1.000000 

B( 1,1, 2, 3) 

0.0000000 

B( 1, 1, 3, 1) 

0.0000000 

B( 1, 1, 3, 2) 

1.000000 

B( 1,1, 3, 3) 

0.0000000 

B( 1,2, 1,1) 

0.0000000 

B( 1,2, 1,2) 

1.000000 

B( 1,2,1,3) 

0.0000000 

B( 1, 2, 2, 1) 

0.0000000 

B( 1, 2, 2,2) 

1.000000 

B( 1, 2, 2, 3) 

0.0000000 

B( 1, 2, 3, 1) 

0.0000000 

B( 1, 2, 3, 2) 

1.000000 

B( 1, 2, 3, 3) 

0.0000000 

B( 1,3, 1,1) 

0.0000000 

B( 1,3, 1,2) 

1.000000 

B( 1,3, 1,3) 

0.0000000 

B( 1, 3, 2, 1) 

0.0000000 

B( 1,3,2, 2) 

1.000000 

B( 1, 3, 2, 3) 

0.0000000 

B( 1, 3, 3, 1) 

0.0000000 

B( 1, 3, 3, 2) 

1.000000 

B( 1, 3, 3, 3) 

0.0000000 


B-8 



B( 2, 1,1,1) 0.0000000 
B(2,1,2,1) 0.0000000 
B(2, 1,3, 1) 0.0000000 
B( 2, 2,1, 1) 0.0000000 
B( 2, 2, 2, 1) 0.0000000 
B( 2,2, 3,1) 0.0000000 
B( 2, 3, 1, 1) 0.0000000 
B( 2, 3, 2, 1) 0.0000000 
B( 2, 3, 3, 1) 0.0000000 

B(3, 1,1, 1) 0.0000000 
B(3,1,2,1) 0.0000000 
B(3, 1,3, 1) 0.0000000 
B(3,2,1,1) 0.0000000 
B( 3, 2, 2, 1) 0.0000000 
B( 3,2, 3,1) 0.0000000 
B(3, 3,1,1) 0.0000000 
B( 3, 3, 2, 1) 0.0000000 
B( 3, 3, 3, 1) 0.0000000 


B( 2, 1,1,2) 1.000000 
B( 2,1,2,2) 1.000000 
B( 2, 1,3,2) 1.000000 

B(2,2, 1,2) 1.000000 

B( 2, 2,2, 2) 1.000000 
B( 2, 2, 3, 2) 1.000000 

B(2,3,1,2) 1.000000 

B( 2, 3, 2, 2) 1.000000 

B( 2, 3, 3, 2) 1.000000 

B( 3,1,1,2) 0.0000000 
B( 3, 1,2,2) 0.0000000 
B( 3, 1,3,2) 0.0000000 
B(3,2,1,2) 0.0000000 
B( 3, 2, 2, 2) 0.0000000 
B( 3, 2, 3, 2) 0.0000000 
B(3,3,1,2) 0.0000000 
B( 3, 3, 2, 2) 0.0000000 
B( 3, 3, 3, 2) 0.0000000 


B(2,1,1,3) 0.0000000 

B( 2, 1,2,3) 0.0000000 

B( 2,1,3,3) 0.0000000 

B(2,2,1,3) 0.0000000 

B( 2, 2, 2, 3) 0.0000000 

B( 2, 2, 3, 3) 0.0000000 

B(2,3,1,3) 0.0000000 

B( 2, 3, 2, 3) 0.0000000 

B( 2, 3, 3, 3) 0.0000000 

B( 3,1,1,3) 0.0000000 

B( 3,1,2,3) 0.0000000 

B( 3,1,3,3) 0.0000000 

B(3,2, 1,3) 1.000000 

B( 3, 2,2, 3) 1.000000 

B( 3, 2, 3, 3) 1.000000 

B(3,3, 1,3) 1.000000 

B( 3, 3, 2, 3) 1.000000 

B( 3, 3, 3, 3) 1.000000 


B-9 



Appendix C - Genetic Algorithm Evaluation Function 


C.l Description of Evaluation Function and Variables used in Program 

In this appendix we provide the evaluation function that we coded using the 
programming language C. GENESIS calls the evaluation function and sends it a 
solution. The evaluation function determines the objective function value of that solution 
and the penalties that should be assessed on that solution before returning the objective 
function value including any penalties that were assessed. There are comments 
throughout the code explaining what the code is doing. This code is written for the 
simple three box test case. Below is a list and description of the variables used in the 
program. 

GENESIS sends these four variables to the evaluation function: 


char str[]; 

int length; 
double vect[]; 
int genes; 


This variable represents the actual Is and Os found 
in the solution. 

This variable represents the length of the bit stream. 
Neither of these two variables are used in this 
program since all variables are binary. 


The following variables are all used within the evaluation function: 


int box_vol[3J = {18, 18, 6}; 
int box_L[3] = {3, 3, 3}; 
int box_w[3] = {3, 2, 2}; 
int box_h[3] = {2, 3, 1}; 
int adjj~aces[3] = {33, 33, 7}; 


Actual volumes for each box 
Actual lengths for each box 
Actual widths for each box 
Actual heights for each box 
Number of adjacent faces for each 
box 


int numjboxes = 3; 
int pal_L ~ 3; 
int pal_w = 3; 
int palji = 3; 
int paljvol = 27; 


Number of boxes to be packed 
Length of the pallet 
Width of the pallet 
Height of the pallet 

Available packing volume on the pallet 


C-l 


int box_pal[3J[3][3][3]; Four dimensional array which holds the 

solution sent by GENESIS. The first 
dimension is for the boxes, and the last three 
dimensions are for the length, width, and 
height of the pallet 

Each of the following constraints are used to check whether a solution sent by 
GENESIS violates a certain constraint. 


int pack_pal[3][3][3]; This checks to see whether only one box is 

placed at each location 

int pack_pal_mod[3][3][3]; This checks whether each box has a 



foundation on which to be packed 

int count_adj_Jaces[3]; 

This checks whether each box has the 
correct number of adjacent faces 

int sum_box[3]; 

This checks whether each box is packed 
with the correct volume 

int wrong_L[3]; 

This checks whether each box is packed 
with the correct length 

int wrong_w[3]; 

This checks whether each box is packed 
with the correct width 

int wrong_h[3] ; 

This checks whether each box is packed 
with the correct height 

int violation[3]; 

This checks whether each box is packed 
with the correct dimensions 

int mistake[3]; 

This counts how much the packed volume 
for each box differs from the actual volume 
of the box 


Each of these constraints ensure that for each time the evaluation function is 
called the penalties are reset to zero. 


int penalty 1 = 0; 
int penalty2 = 0; 
int penalty3 - 0; 

int penalty4 = 0; 
int penally5 = 0; 

int penalty6 = 0; 

int total_penalty = 0; 


Checks whether boxes have correct volume 
Checks whether available pallet volume is exceeded 
Checks whether more than one box is packed at 
each location 

Checks whether each box has a foundation 
Checks whether each box has the correct number of 
adjacent faces 

Checks whether boxes are packed with the correct 
dimensions 

Total of all the above penalties 


C-2 



int same[3]; This variable checks whether the dimensions of 

each individual box are the same 

int done; Used to determine which orientation box was 

packed in 

int match = 0; Also used to determine which orientation box was 

packed in 

Each of the following constraints are used to help determine if there are constraint 
violations. 

int count_L = 0; Used to ensures boxes are packed with 

correct length 

int countjw = 0; Used to ensure boxes are packed with 

correct width 

int countJi = 0; Used to ensure boxes are packed with 

correct height 

intpack_vol = 0; Used to ensure the available pallet volume is 

not exceeded 

char temp[2]; This variable enables us to change the 

character string to an integer string 

double obj Jun_yal = 0; Value returned to GENESIS after all 

penalties have been assessed 


C.2 Function Preventing Negative Penalties 

This function is called twice within the evaluation function to ensure no negative 
penalties are assessed. 

/* This function ensures we do not get negative penalties */ 

int no_negative(int x, inty) 

{ 

if(( x ~y) >= 0) 

return (x - y); 
else 

return (y - x); 


C-3 


C.3 Initialization of Variables 


/* These are the variables which are passed in by Genesis */ 

double eval (str, length, vect, genes) 

char strfj; 

int length; 

double vect[]; 

int genes; 

{ 

int pack_pal[3][3][3]; 
int pack_pal_mod[3][3][3]; 
int box_vol[3] = {18, 18, 6}; 
int box_L[3] = {3, 3, 3}; 
int box_w[3J = {3,2,2}; 
int box_h[3J = {2, 3, 1}; 
int adj Jaces[3] = {33, 33, 7}; 
int count_adj_faces[3]; 

int penalty 1 = 0; 
int penalty2 = 0; 
int penalty3 = 0; 
int penalty 4 = 0; 
int penalty 5 = 0; 
int penalty6 = 0; 
int done; 

int total_penalty = 0; 

int sum_box[3]; 
int wrong_L[3] ; 
int wrong_w[3]; 
int wrong_h[3]; 
int violation[3]; 
int mistake[3]; 
int same[3]; 

int box j>al[3][3][3][3]; 

int numjboxes = 3; 
int palji = 3; 
int pal_L = 3; 
int pal_w = 3; 
int paljyol = 27; 

int match = 0; 
int count_L = 0; 
int count_w = 0; 


C-4 



int count Ji = 0; 
double obj_fun_val = 0; 
int pack_yol = 0; 

int i,H, W,L; 

char temp[2]; 

for (H= 0; H <palji; H++) 
for (W = 0; W < pal_w; W++) 
for (L — 0; L < pal_L; L~+) 

{ 

pack_pal[L] [W] [H] = 0; 
pack_pal_mod[L] [W] [H] = 0; 

} 


for (i = 0; i < numjboxes; i++) 

{ 

sum_box[i] = 0; 
count_adjJaces[i] = 0; 
wrong_L[i] = 0; 
wrong_w[i] = 0; 
wrong_h[i] = 0; 
violation [i] = 0; 
mistake[i] = 0; 
same[i] = 0; 

} 


C.4 Determine Whether Each Boxes Length, Width and Height are the Same 

This is used in the constraint which checks whether each box is packed with the 

correct dimensions. 

for (i = 0; i < numjboxes; i++) 

{ 

if ((box_L[i] == box_w[i]) && (box_L[i] == boxjifi])) 
same[i] = 3; 
else 

same[i] = 0; 


C-5 


C.5 Convert Character String to Binary String 


This converts the character string into a binary string and puts the binary string 

into a four dimensional array. The first dimension represents the boxes, and the other 

three dimensions represent the length, width and height of the pallet respectively. 

Additionally, within the loop the program calculates the packed volume of each box in 

the solution as well as determine how many boxes are placed in each location. 

/* Must read in solution and put that solution into matrix form */ 

for (i = 0; i < num_boxes; i++) 
for (H = 0; H < palji; H++) 
for (W - 0; W < pal_w; W++) 
for (L = 0;L< pal_L; L++) 

{ 

temp[0] - strfpal_vol*i + pal_h*pal_w*H + pal_L*W + L]; 
temp[l] = 'l O'; 

box_pal[i] [L] [W] [H] = atoi(temp); 

sum_box[i] = sum_box[i] + box_pal[i] [L] [W] [H]; 

pack_pal[L] [W] [H] = pack_pal[L] [W] [H] + box_pal[i] [L][W][H]; 

} 


C.6 First Feasibility Check 

This checks whether the packed volume of each box is equal to the actual volume 
of that box. If there is a violation then a penalty is assessed. 

/* First feasibility check is to see if the volume of the boxes packed are the actual box 
volume */ 


for (i = 0; i < numjboxes; i++) 

if ((sum _box[i] != box_vol[iJ) && (sum_box[i] != 0)) 

mistake[i] = mistake[i] + no_negative(box_vol[i], sum_box[i]); 

for (i = 0; i < numjboxes; i++) 

penalty 1 = penalty 1 + mistake[i]; 


C-6 



C.7 Second Feasibility Check 

This checks whether the packed volume exceeds the available volume. If it does 
then a penalty is assessed. 

/* Second feasibility check is to see if the volume of the solution is greater than the 
available volume on the pallet */ 

for (i = 0; i < numjboxes; i++) 
pack_vol = packjvol + sum_box[iJ; 

if (pack_vol > paljvol) 
penalty2 = packjvol - pal_vol; 


C.8 Third Feasibility Check 

This checks whether more than one box occupies each location on the pallet and 
assesses a penalty for each violation. 

/* Third feasibility check only allows one box to be placed in each location */ 

for (H = 0; H <palh; H++) 
for (W = 0; W< pal_w; W++) 
for (L = 0; L < pal_L; L++) 

{ 

if (pack_pal[L][W][H] > 1) 
penalty3 = penalty3 + (pack_pal[L] [W][H] - 1); 

} 


C-7 


C.9 Fourth Feasibility Check 

This checks whether each box has a foundation on which to be packed and assigns 
a penalty for each location where the foundation does not exist. 

/* Fourth feasibility check only allows a box to be packed if there is a foundation for it */ 

for (H = 0; H <pal_h; H++) 
for (W= 0; W < pal_w; W++) 
for (L = 0; L < pal_L; L++) 

{ 

if (pack_pal[L] [W] [H] > 0) 
pack_pal_mod[L] [W][H] = 1; 
else 

pack_pal_mod[L] [W] [H] = 0; 

} 

for (W = 0; W <pal_w; W++) 
for (L = 0; L <pal_L; L++) 

for (H = 1; H < palji; H++) 

{ 

if ((pack_pal_mod[L] [W] [H] -packj>al_mod[L] [W] [H-l]) > 0) 
penalty 4 = penalty 4 + 1; 

} 


C-8 



C.10 Fifth Feasibility Check 


This checks whether the number of adjacent faces for each box in the solution is 
equal to the actual number of adjacent faces for that box. For each violation a penalty is 
assessed. 

/* Fifth constraint ensures that the box is linked together */ 

for (i = 0; i < num_boxes; i++) 

{ 

for (H = 0; H < palji; H++) 

{ 

for (W = 0; W < pal_w; W++) 

{ 

for (L — 1; L < pal_L; L++) 

{ 

if ((box_pal[i] [L] [W] [H] == 1) && (box_pal[i][L-l][W][H] == 1)) 
count_adjjaces[i] = count_adj_faces[i] + 1; 

} 

- } 

for (L = 0; L < pal_L; L++) 

{ 

for (W = 1; W <pal_w; W++) 

{ 

if ((box_pal[i] [L] [W] [H] == 1) && (box_pal[i] [L] [W-1J [H] == 1)) 
count_adjJaces[i] = count_adjJaces[i] + 1; 

} 

} 

} 

for (W - 0; W < pal_w; W++) 
for (L = 0; L < pal_L; L++) 
for (H — 1; H <palji; H++) 

{ 

if ((box_pal[ij [L] [W] [H] ==!)&& (box_pal[i] [L] [W] [H-1J == 1)) 
count_adj_faces[i] = count_adjJaces[i] + 1; 

} 


for (i = 0; i < num_boxes; i++) 

if ((countjxdjJaces[i] != adj_faces[i]) && (sum_box[i] > 0)) 
penally5 = penalty5 + no_negative(adjJaces[i], count_adj_faces[i]); 


C-9 



C.ll Sixth Feasibility Check 

This constraint checks to ensure each box is packed with the correct dimensions. 
It allows the box to be packed with any orientation. If the dimensions of a particular box 
are the same then the check is quite simple. Otherwise the check is quite intensive and 
consists of multiple loops to determine the orientation in which the box is packed. For 
each violation a penalty is assessed. 

/* The sixth constraint ensures that each box is packed with the correct L, W, &H*/ 

for (i = 0; i < numjboxes; i++) 

{ 


/* This first part is for boxes with all the same dimensions */ 
if (same[i] -= 3) 

f 

for (H = 0; H <palji; H++) 

{ 

for (W = 0; W < pal_w; W++) 

{ 

countJL = 0; 

for (L - 0; L < pal_L; L++) 
if (box_pal[i] [L][W] [H] == 1) 
count_L = count JL + 1; 
if ((count JL 1= box_L[i]) && (count JL 1=0)) 
wrong_L[i] = wrong_L[i] + 1; 

} 

for (L = 0; L < pal_L; L++) 

{ 

count_w = 0; 

for (W = 0; W < pal_w; W++) 
if (box_pal[i] [L] [W] [H] == 1) 
count_w = countjw + 1; 
if ((count_w != box_w[iJ) && (count_w != 0)) 
wrong_w[i] = wrong_w[i] + 1; 

} 

} 

for (W= 0; W < pal_w; W++) 

{ 

for (L = 0; L < pal_L; L++) 


C-10 



{ 

countJt = 0; 

for (H = 0; H < palji; H++) 
if (box_pal[i] [L] [W] [H] == 1) 
countJi = count_h + 1; 
if ((countJ!- box_h[i]) && (countJi /= Of) 
wrong_h[i] = wrong_h[i] + 1; 

} ... 

} 

/* The rest of this is for boxes that do not have all three dimensions equal */ 
else 

{ 

match = 0; 
countJL = 0; 
done = 0; 

W=0; 

H=0; 

- while (done == 0) 

{ 

tf((W== (palw - 1)) && (H == (palji - 1))) 
done = 1; 

for (L = 0; L < pal_L; L++) 
if (box_pal[i][L][W][H] == 1) 
countJL = countJL + 1; 

W= W+ 1; 
if (countJL, > 0) 
done = 1; 

else if (W--pal_w) 

{ .. 

H = H+1 ; 

W=0; 

} 

else 

{} 

. } 

if (count J == boxJ^[i]) 
match = 1; 

else if (countJL == box_w[i]) 
match = 2; 

else if (countJL, == boxjfi]) 
match = 3; 


C-ll 


else if (count_L != 0) 

{ 

violationfi] = violation[i] + 1; 
match = 1; 

} 

else 

{} 

/* This is for boxes whose length is packed along the length of the pallet */ 

if (match == 1) 

{ 

for (H = 0; H < palji; H++) 

{ 

for (W - 0; W < palw; W++) 

{ 

count_L = 0; 

for (L = 0; L < palJL; L++) 
if (box_pal[i] [L] [W] [H] == 1) 
count_L - count_L + 1; 
if (( count_L /= box_L[i]) && (count_L !- 0)) 
wrong_L[i] = wrong_L[i] + 1; 

} 

} 

done = 0; 
count_w = 0; 

L = 0; 

H = 0; 

while (done == 0) 

{ 

if ((L == (pal_L - 1)) && (H == (palji -1))) 
done = 1; 

for (W - 0; W < pal_w; W++) 
if (box_pal[i] [L] [W] [H] == 1) 
count w = count w + 1; 


L - L + 1; 
if (count_w > 0) 
done = 1; 

else if (L ==pal_L) 

{ 

H - H + 1; 

L = 0; 

} 


C-12 


if (count_w == box_w[i]) 
match = 4; 

else if (count_w == box_h[i]) 
match = 5; 
else if (count_w != 0) 

{ 

violation [i] = violation [i] + 1; 
match = 4; 

} 

else 

0 

/* This is for boxes whose width is packed along the width of the pallet * 

/ 

if (match == 4) 

{ 

for (H - 0; H <palji; H++) 

{ 

for (L = 0; L < pal_L; L++) 

{ 

count = 0; 

for (W = 0; W < pal_w; W++) 
if (box_pal[i] [L] [W] [H] == 1) 
count_w = countjw + 1; 
if ((count_w!- box_w[i]) && (count_w != 0)) 
wrong_w[i] = wrong_wfi] + 1; 

} . . ' 

for (W=0;W< palw; W++) 

{ 

for (L = 0; L < pal_L; L++) 

{ 

countJi = 0; 

for (H = 0; H <palji; H++) 
if (box_pal[i] [L] [W] [H] == 1) 
countji = count Ji + 1; 
if ((count_h != box_h[i]) && (countJi /= 0)) 
wrongJifiJ = wrong_h[i] + 1; 


} 


/* This is for boxes whose height is packed along the width of the pallet */ 

if (match == 5) 

{ 

for (H = 0; H <palji; H++) 

{ 

for (L = 0; L < pal_L; L++) 

{ 

count_w = 0; 

for (W=0;W< pal_w; W++) 
if (box_pal[i] [L] [W] [H] == 1) 
countjw = countjw + 1; 
if ((count_w != boxJi[i]) && (count_w !— 0)) 
wrong_w[i] = wrong_w[i] + 1; 

} 

} 

for (W = 0; W < palw; W++) 

{ 

for (L = 0; L < pal_L; L++) 

{ 

count_h = 0; 

for (H= 0; H < palji; H++) 
if (box_pal[i][L] [W] [H] == 1) 
counth = countji + 1; 
if ((count_h != box_w[i]) && (count_h != 0)) 
wrong_h[i] = wrong_h[i] + 1; 

} 

} 

} 

} 

/* This is for boxes whose width is packed along the length of the pallet */ 

if (match == 2) 

{ 

for (H = 0; H <palji; H++) 

{ 

for (W - 0; W < pal_w; W++) 

{ 

count J; - 0; 

for (L = 0; L < palJL; L++) 
if (box_pal[i] [L] [W] [H] == 1) 
countJL = count_L + 1; 
if ((count_L != box_w[iJ) && (count_L != 0)) 
wrong_L[i] - wrong_L[i] + 1; 


C-14 



} 


done = 0; 
countpw = 0; 

L = 0; 

H = 0; 

while (done == 0) 

{ 

if ((L == (pal_L -1)) && (H == (palji -1))) 
done = 1; 

for (W - 0; W <pal_w; W++) 
if (box_pal[i] [L] [W] [H] == 1) 
countpw = count_w + 1; 

L = L + 1; 
if (countpv > 0) 
done = 1; 

else if (L==pal_L) 

{ 

H = H+ 1; 

L = 0; 

} 

else 

0 

} 

if (count_w == box_L[i]) 
match = 4; 

else if (count_w == box_h[i]) 
match = 5; 
else if (count_w !— 0) 

{ 

violationfi] = violation[i] + 1; 
match = 4; 

} 

else 

{} 

/* This is for boxes whose length is packed along the width of the pallet */ 

if (match == 4) 

{ 

for (H = 0;H<palji; H++) 

{ 

for (L - 0; L < pal_L; L++) 


C-15 


{ 

countjw = 0; 

for (W - 0; W < pal_w; W++) 
if (box_pal[i] [L][W] [H] == 1) 
countjw = count_w + 1; 
if ((count _w /= box_L[i]) && ( countjw!- 0)) 
wrong_w[i] - wrong_w[i] + 1; 

} 

} 

for (W - 0; W <pal_w; W++) 

{ 

for (L = 0; L < pal_L; L++) 

{ 

countJi = 0; 

for (H = 0; H < palji; H++) 
if (box_pal[i] [L][W][H] == 1) 
count_h = countji + 1; 
if ((count_h != box_h[i]) && (countji !— 0)) 
wrong_h[i] = wrong_h[i] + 1; 

} 

} 

- } 

/* This is for boxes whose height is packed along the width of the pallet */ 

if (match == 5) 

{ 

for (H - 0; H <palji; H++) 

{ 

for (L = 0; L < pal_L; L++) 

{ 

countw = 0; 

for (W = 0; W < pal_w; W++) 
if (box_pal[i] [L] [W][H] == 1) 
count_w = count ja) + 1; 
if ((count _w != box_h[iJ) && (count_w != 0)) 
wrong_yv[i] = wrong ja>[ i] + 1; 

} 

} 

for (W = 0; W <pal_w; W++) 

{ 

for (L = 0; L < pal_L; L++) 

{ 

countji = 0; 

for (H = 0; H <palji; H++) 
if (box_pal[i] [L] [W][H] == 1) 


C-16 



countJi = countJi + 1; 
if ((count_h != box_L[iJ) && (countJi != 0)) 
wrong_h[i] - wrong_h[i] + 1; 

} 

} 

} 

} 

/* This is for boxes whose height is packed along the length of the pallet */ 

if (match == 3) 

{ 

for (H = 0; H < pal_h; H++) 

{ 

for (W=0;W< pal_w; W++) 

{ 

count_L = 0; 

for (L = 0; L < pal_L; L++) 
if (box_pal[ij [L] [W] [H] == 1) 
count_L - count_L + 1; 
if ((countJL != box_h[i]) && (count_L != 0)) 
wrong_L[i] = wrong_L[i] + 1; 

} 

} 

done = 0; 
countjw = 0; 

L = 0; 

H = 0; 

while (done == 0) 

{ 

if ((L == (palJL - 1)) && (H == (palji - 1))) 
done = 1; 

for (W = 0; W < pal_w; W++) 
if (box_pal[i] [L] [W] [H] ==1) 
countjw - countjw + 1; 

L= L + 1; 
if (count_w > 0) 
done = 1; 

else if (L ==pal_L) 

{ 

H - H + 1; 

L = 0; 

} 


C-17 


else 

{} 


} 


if (count_w == box_L[i]) 
match = 4; 

else if (count_w == box_w[i]) 
match = 5; 
else if (count_w /= 0) 

{ 

violation [i] = violation [i] + 1; 
match = 4; 

} 

else 

0 

/* This is for boxes whose length is packed along the width of the pallet */ 

if (match == 4) 

{ 

for (H - 0; H <palji; H++) 

{ 

for (L = 0; L < pal_L; L++) 

{ 

count_w = 0; 

for (W = 0; W <pal_w; W++) 
if (box_pal[ij [L] [W][H] == 1) 
count_w = count_w + 1; 
if ((count_w != box_L[i]) &<& (count_w != 0)) 
wrong_w[i] = wrong_w[i] + 1; 

} 

} 

for (W - 0; W < pal_w; W++) 

{ 

for (L - 0; L < pal_L; L++) 

{ 

count_h - 0; 

for (H= 0; H < palji; H++) 
if (box_pal[i] [L] [W] [H] == 1) 
count_h = count_h + 1; 
if ((countJi /= box_w[iJ) && (countji /= 0)) 
wrongJifiJ = wrong_h[i] + 1; 

} 

} 

} 


C-18 


/* This is for boxes whose width is packed along the width of the pallet */ 
if (match == 5) 

{ 

for (H = 0; H <palji; H++) 

{ 

for (L = 0; L < palJL; L++) 

{ 

count_w = 0; 

for (W = 0; W < palw; W++) 
if (box_pal[i] [L] [W] [H] == 1) 
count_w = count_w + 1; 
if ((count_w != box_w[i]) && (count_w != 0)) 
wrong_w[i] = wrong_w[i] + 1; 

} 

} 

for (W=0;W< pal_w; W++) 

{ 

for (L = 0; L < pal_L; L++) 

{ 

countji = 0; 

for (H = 0; H <palji; H++) 
if (box_pal[i][L]fWJ [H] == 1) 
countJi - count_h + 1; 
if ((count_h /= box_L[i]) && (count_h /= 0)) 
wrong_h[i] = wrong_h[i] + 1; 

} 

} 

- } 

} 

} 

} 

for (i = 0; i < numfboxes; i++) 

if ((violationfij > 0) || (wrong_L[i] > 0) || (wrong_w[iJ > 0) || (wrong_h[i] > 0)) 
penalty6 =penalty6 + violationfij + wrong_L[i] + wrong_w[i] + wrong_h[i]; 


C-19 


C.12 Objective Function Value 

This calculates the total penalty associated with all the violations and then 
calculates the objective function value which is returned to GENESIS. 

/* This calculates the objective function value */ 

totaljpenalty = 50*penaltyl + 500*penalty2 + 500*penalty3 + 500*penalty4 + 
100*penalty5 + 100*penalty6; 

obj_fun_val = (pal_vol -packjyol) + total_penalty; 

return (obj Junjyal); 

} - 


C-20 


Appendix D - Results of Genetic Algorithm on Test Problems 


D.l Introduction 

For each of these test problems we will show the genetic algorithms settings we 
used, the number of generations it took to find the reported solution, as well as provide 
the reported solution. We attempted to solve three separate test problems. The first test 
problem consisted of three boxes, the second test problem consisted of six boxes and the 
third test problem consisted of eleven boxes. Additionally, the available pallet volume 
for the first two test problems was 27, while for the third test problem the available pallet 
volume was 112. 


D.2 Results of Test Problem One 

The genetic algorithm settings we used for this problem are illustrated below. 

Experiments = 1 
Total Trials = 50000 
Population Size = 50 
Structure Length = 81 
Crossover Rate = .85 
Mutation Rate = .01 
Generation Gap = .9 
Scaling Window = 5 
Report Interval = 250 
Structures Saved = 10 
Max Gens w/o Eval = 2 
Dump Interval = 0 
Dumps Saved = 0 
Options = cel 
Random Seed = 123456789 
Rank Min = 0.75 


D-l 


The settings we adjusted were the total trials (number of generations), population 

size, crossover rate, mutation rate, and generation gap. We found that these initial setting 

forced the genetic algorithm to converge on the optimal solution in less than 200 

generations. The optimal solution is provided below. Each group of three bits represents 

a row, and each group of nine bits represents a layer of the pallet. 

Oil Oil Oil || Oil Oil Oil || Oil Oil Oil Box 1 

000 000 000 II 000 000 000 jj 000 000 000 Box 2 

100 100 100 II 100 100 100 II 000 000 000 Box 3 

Objective Function Value = 3.0000e+00 


D.3 Results of Test Problem Two 


For this test problem the size of the pallet remained the same as in the first test 
problem, however the number of boxes to be packed doubled. Therefore, the structure 
length of the bit stream also doubles from 81 variables to 162 variables. The input file 


used for this test problem is shown below. 


Experiments 
Total Trials 
Population Size 
Structure Length 
Crossover Rate 
Mutation Rate 
Generation Gap 
Scaling Window 
Report Interval 
Structures Saved 
Max Gens w/o Eval 
Dump Interval 
Dumps Saved 
Options 
Random Seed 
Rank Min 


1 

65000 

100 

162 

.95 

.01 

.9 

5 

500 

10 

2 

0 

0 

cel 

123456789 

0.75 


D-2 




These were the settings we found to work best for this test problem. 

Unfortunately we were unable to get the genetic algorithm to converge on the optimal 
solution. Instead it converged on a sub-optimal feasible solution in 655 generations. The 
solution found is provided below. 


Oil 

Oil 

000 

II 011 

Oil 

000 

II 000 

000 

000 

Box 

1 

000 

000 

000 

II 000 

000 

000 

II 000 

000 

000 

Box 

2 

000 

000 

000 

II 000 

100 

100 

II 000 

100 

100 

Box 

3 

100 

000 

000 

II100 

000 

000 

II 000 

000 

000 

Box 

4 

000 

000 

111 

II 000 

000 

000 

II 000 

000 

000 

Box 

5 

000 

100 

000 

II 000 

000 

000 

II 000 

000 

000 

Box 

6 


Objective function value = 9.0000e+00 


D.4 Results of Test Problem Three 

This test problem is quite a bit larger than the other test problem and has a 
structure length of 1,232 variables. Therefore, it took a very long time for GENESIS to 
find solutions for this problem size. Additionally, since GENESIS only uses single-point 
crossover it did not come close to converging on a feasible solution in a reasonable 
amount of time. However, we did use the settings shown on the following page to solve 
the problem. 


D-3 






Experiments 
Total Trials 
Population Size 
Structure Length 
Crossover Rate 
Mutation Rate 
Generation Gap 
Scaling Window 
Report Interval 
Structures Saved 
Max Gens w/o Eval 
Dump Interval 
Dumps Saved 
Options 
Random Seed 
Rank Min 


1 

100000 

100 

1232 

.85 

.01 

.9 

5 

2000 

10 

2 

0 

0 

cel 

123456789 

0.75 


Using these settings, GENESIS was unable to converge on a feasible solution. 
Also, it took GENESIS 45 minutes to run through all 1,000 generations. At the 99,907 
iteration the best solution was found with an objective function value of 28,876. 


D-4 


Bibliography 


Abdou, G., and M. Yang. “A systematic approach for the three-dimensional 

palletization problem,” International Journal of Production Research 32 : 
2381-2394(1994). 

Abdou, G., and J. Arghavani. “Interactive ILP procedures for stacking optimization for 
the 3D palletization problem,” International Journal of Production Research 35 : 
1287-1304(1997). 

Askin, Ronald G., and Charles R. Standridge. Modeling and Analysis of Manufacturing 
Systems . New York: John Wiley and Sons, Inc., 1993. (320-321) 

“Astrokettle Algorithms.” httD://www4.bcity.com/astrokettle/data.html . 29 July 1999. 

Beasley, D., D.R. Bull, and R.R. Martin. “An overview of genetic algorithms: Part 1, 
fundamentals,” University Computing 15 : 58-69 (1993). 

Beasley, D., D.R. Bull, and R.R. Martin. “An overview of genetic algorithms: part 2, 
research topics,” University Computing 15 : 170-181 (1993). 

Bischoff, E. E., F. Janetz, and M. S. W. Ratcliff. “Loading pallets with non-identical 
items,” European Journal of Operational Research 84 : 681-692 (1995). 

Bischoff, E. E., and M. S. W. Ratcliff “Loading Multiple Pallets,” Journal of the 
Operational Research Society 46 : 1322-1336(1995). 

Chen, C. S., S. Sarin, and B. Ran. “The pallet packing problem for non-uniform box 
sizes,” International Journal of Production Research 29 : 1963-1968(1991). 

Cheng, Runwei and Mitsuo Gen. Genetic Algorithms and Engineering Design . New 
York: John Wiley & Sons, Inc., 1997. 

Chocolaad, Christopher A. Solving Geometric Knapsack Problems using Tabu Search 
Heuristics . MS thesis, AFIT/GOR/ENS/98M-05. Graduate School of 
Engineering, Air Force Institute of Technology (AU), Wright-Patterson AFB, 

OH, March 1998. 

Computer Sciences Corporation. Unit Type Code Development, tailoring, and 

Optimization (UTC-DTOf Phase 2 Final Report . Contract DC A 100-94-D-00144. 
Falls Church VA: Defense Enterprise Integration Services, December 1997. 

Dowsland, Kathryn A. “An exact algorithm for the pallet loading problem,” European 
Journal of Operational Research 31 : 78-83 (1987). 


BIB-1 




Dowsland, Kathryn A., and William B. Dowsland. “Packing problems,” European 
Journal of Operational Research 56 : 2-14 (1992). 

Dowsland, Kathryn A. “Some experiments with simulated annealing techniques for 
packing problems.” European Journal of Operational Research 68 : 389-399 
(1993). 

Dowsland, William B. “Three-dimensional packing—solution approaches and heuristic 
development.” International Journal of Production Research 29 : 1673-1685 
(1991). 

Dowsland, W. B. “Improving palletisation efficiency—the theoretical basis and practical 
application.” International Journal of Production Research 33 : 2213-2222 (1995). 


Fuh-Hwa, F. Liu and C-J Hsiao. “A three-dimensional pallet loading method for single¬ 
size boxes,” Journal of the Operational Research Society 48 : 726-735 (1997). 

Grefenstette, John J. A User’s Guide to GENESIS Version 5.0 . 1990. 

Han, Ching Ping, Kenneth Knott, and Pius J. Egbelu. “A heuristic approach to the three- 
dimensional cargo-loading problem,” International Journal of Production 
Research 27 : 757-774 (1989). 

Healy, Patrick, Marcus Creavin and Ago Kuusik. “An optimal algorithm for rectangle 
placement,” Operations Research Letters 24 : 73-80 (1999). 

Herbert, Edward A. and Kathryn A. Dowsland. “A family of genetic algorithms for the 
pallet loading problem,” Annals of Operations Research 63 : 415-436 (1996). 

Ivancic, N., Kamlesh Mathur, and Bidhu B. Mohanty. “An Integer Programming Based 
Heuristic Approach to the Three-dimensional Packing Problem,” Journal of 
Manufacturing and Operations Management 2 : 268-298 (1989). 

Kemighan, Brian W. and Dennis M. Ritchie. The C Programming Language 2 nd Edition . 
New Jersey: Prentice-Hall, Inc., 1988. 

Manship, Wesley E., and Jennifer L. Tilley. A Three-Dimensional 364L Pallet Packing 
Model and Algorithm . MS thesis, AFIT/GIM/LAL/98S-3. School of Systems 
and Logistics, Air Force Institute of Technology (AU), Wright-Patterson AFB, 
OH, September 1998. 

Morabito, R. and S. Morales. “A simple and effective recursive procedure for the 
manufacturer’s pallet loading problem,” Journal of the Operational Research 
Society 49 : 819-828 (1998). 


BIB-2 


“PowerPack™ 6 Easy Steps to Lower Freight Costs.” 

http://www.remarkable.co.nz/prod04.htm . 29 July 1999. 

Pisinger, David. “David Pisinger’s optimization codes.” 

http://www.diku.dk/~pisinger/codes.html . 29 July 1999. 

Reeves, Colin R. Modem Heuristic Techniques for Combinatorial Problems . London: 
McGraw-Hill Book Company, 1995. (151-188) 

Romaine, Jonathan M. Solving the Multidimensional Multiple Knapsack Problem with 
Packing Constraints Using Tabu Search . MS thesis, AFIT/GOR/ENS/99M-15. 
Graduate School of Engineering, Air Force Institute of Technology (AU), Wright- 
Patterson AFB, OH, March 1999. 

Scheithauer, Guntram and Johannes Temo. “The G4-Heuristic for the Pallet Loading 
Problem,” Journal of the Operational Research Society 47 : 511-522 (1996). 

TASC, Inc. (8 May 1998) Interim Project Report on the Feasibility of Finding Optimal 
Solutions to Three-Dimensional Packing Problems . Contract number F41624-97- 
D-5002, Air Force Research Labs/HESR, Wright-Patterson AFB OH. 

Taylor, Gregory S. A Pallet Packing Postprocessor for the Logistics Composite Model . 
MS thesis, AFIT/GST/ENS/94M-11. Graduate School of Engineering, Air Force 
Institute of Technology (AU), Wright-Patterson AFB, OH, March 1994. 

Tsai, R.D., E.M. Malstrom, and W. Kuo. “Physical Simulation of a Three Dimensional 
Palletizing Heuristic.” International Journal of Production Research 32 : 1159- 
1171 (1994). 

Tsai, R.D., E.M. Malstrom, and W. Kuo. “Three Dimensional Palletization of Mixed Box 
Sizes,” HE Transactions 25 : 64-74 (1993). 


BIB-3 




Vita 


2Lt. Brian Ballew was bom on 7, July 1976 in Panorama City, California. He 
grew up in Santa Clarita, California and eventually graduated from William S. Hart High 
School. He then attended the United States Air Force Academy in Colorado Springs, 
Colorado. On 27, May 1998 he received his commission as well as his Bachelors of 
Science degree in Operations Research and a minor in Mathematics. In August of 1998, 
he entered the Air Force Institute of Technology in pursuit of a Master’s degree in 
Operations Research. His next assignment is to Shriever AFB, Colorado as a scientific 
analyst. 


V-l