# 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