Journal of Service Science and Management, 2011, 4, 513522 doi:10.4236/jssm.2011.44059 Published Online December 2011 (http://www.SciRP.org/journal/jssm) Copyright © 2011 SciRes. JSSM 513 Solving the ThreeDimensional PaletPaking Problem Using Mixed 0  1 Model Adel Mohammed AlShayea Industrial Engineering Department, College of Engineering, King Saud University, Riyadh, Saudi Arabia. Email: alshayea@ksu.edu.sa Received October 6th, 2011; revised November 16th, 2011; accepted November 28th, 2011. ABSTRACT The distribution of Pa llet Packing Problem is to lo ad a set of distinct boxes with given dimensions on pa llets or in con tainers to maximize volume utilization. This problem is still in its early stages of research, but there is a high level of interest in developing effective models to solve this NPhard problem to reduce the time, energy and other resources spent in pa cking pallets. In this pap er, the threedimensional pallet loading with mixed box sizes model has been devel oped. This loading model allows many boxes of various sizes to be placed onto the same pallet. The model also consid ers the number or proportion of each box size that can be loaded on a pallet. No restrictions are placed on the dimen sions of the boxes, the pallets, or the number of different box sizes that can be considered. Therefore, the objective of this work is to determine how to most efficiently load a given pallet by maximizing the volume occupied by its load of boxes. Tests on several problems were implemented using OR library in order to show the validation of the proposed model. The results showed that the formulated mixed 0  1 models provide exact solutions for the palletpacking prob lem. The computational time requirements of the developed model prevent its use in realtime palletizing applications. As microcomputer chip technology continues to evolve the lengthy computation time may prove to be less of a problem in real time applications. Keywords: Pallet, Packing Problem, Optimization, Mixed 0  1 Models, 3D Pallet Loading 1. Introduction Everyday many items are shipped from one place to an other. These items are put in containers or pallets. To ship more items while spending less energy, time, and money, the items should be packed optimally or at least near op timally [1]. This problem becomes even more important in the field of air shipping [2]. The palletloading prob lem is a problem with many different variants. The early form of this type of problem was the onedimensional loading or packing problem, in which a set of posi tive values n w, e.g. weight values, must be partitioned into the minimum number of subsets so that the total va lue in each subset does not exceed a given pallet capacity . The twodimensional of palletloading problem ex tends the onedimensional palletloading problem. Instead of considering only one set of positive values, two diffe rent sets of positive values are considered, namely two different dimensions, e.g. width and length of the rec tangular pieces to be cut out. As expected, this problem is harder to solve than the one or twodimensional pallet loading problems [35]. W These palletloading problems are NPhard problems. NP stands for ‘nondeterministic polynomial’. NPhard means the solution time increases exponentially as the si ze of the problem increases. The threedimensional pallet loading problem is strongly NPhard because the three dimensional palletloading problem is a special case of the onedimensional problem [6,7]. The threedimensional packing problem is a natural generalization of the classical one and twodimensional problems. In general, optimal solutions are computationa lly impractical to achieve [8]. For this reason, most of the studies have focused on the practical aspects of loading a container and developing heuristic solutions based on the concept of filling out the container with boxes organized in layers, walls, and columns. In other cases, twodimen sional pallet packing heuristics are applied to the general threedimensional containerloading problem. These heu ristics are, in general, online packing algorithms, which mean they pack boxes onebyone in a given order. More precisely, when the algorithm is packing a box, it has information only about the boxes previously packed, and
Solving the ThreeDimensional PaletPaking Problem Using Mixed 0  1 Model 514 once a box is packed, it cannot be moved to another pla ce. This technique is not efficient and is also not applica ble, when applying the load balance and other constraints. Since the palletpacking problem has a large solution spa ce, it is extremely difficult to prove that a solution is the global optimum. Only with many different sets of boxes can an algorithm be tested and its performance evaluated. 2. Review of Relevant Literature Gehring et al.’s paper [9] presents a heuristic for packing nonidentical items within a container. They, like George and Robinson [4], utilized the idea of packing sections of the container across the full width and height. They utili zed an ordering based on decreasing volume, having placed the first block in a section (layer), and the layer determining box (LDB). They also developed a packing across the container floor first and then upwards. This tends at first to produce something of a decreasing wedge across the width of the container. This approach does en sure that cargo sections can be moved around so as to provide appropriate weight redistribution, but it will clear ly lead in some instances to reduced volume utilization. A further aspect associated with not allowing boxes to straddle sections is that of load stability. Packing where boxes do straddle between layers can produce a more cohesive load. Han, Knott and Egbelu [10] showed that the idea of walls needs not to be restricted to the vertical sides of the container. They described an algorithm in which the container (major prism) is packed with identi cal boxes (minor prisms). The algorithm as described is designed for only a single box type that is constant in both size and shape and no practical constraints are con sidered. The approach is to produce packing of Lshaped modules, with the initial module considered spanning the whole of the container base, and one of the container walls. The arrangement within the “L” is determined by dynamic programming (similar to the approach of Steu del [11], which maximizes the edge utilization). The idea of building walls along any of the six faces of the con tainer is an interesting one; however, the example they used fits one less box than that obtained by stacking mul tiples of two different ‘wall’ arrangements on the floor of the container. The weakness in the approach of Han et al. [10] is a result of maximizing the utilization of the perimeter of the “L” module. No evidence was presented to suggest why an Lshaped module approach should be adopted. Their example consists of packing a container of size 48'' by 42" and 40" with boxes 11" by 6" by 6". They were able to fit 195 boxes, a 95.16% volume utilization of the container. They quoted the US General Services Admini stration whose published results (1966) for the same pro blem only provide 82.5% utilization). Mohanty et al. [12] proposed a multidimensional kna psack problem approach to the threedimensional pack ing problem dealing with filling up various containers with boxes. Their objective was to maximize utilization of the space in the containers or the value of the contents of the containers. They used a column generating proce dure which heuristically uses a “greedy approach” to ge nerate columns one at a time, without considering any constraints other than overlapping and dimensions of the containers. Since they used a “greedy approach”, their app roach was not robust and was strongly affected by the number of different items to be packed. Kocjan and Holmstrِm [13] developed a model produ cing a high degree of stability. The results obtained dur ing evaluation showed great improvement in the number of stable patterns in comparison with results reported earlier. Moreover, most of the solved cases also ensured optimality in terms of utilization of a pallet. Recently, Junqueira et al. [14] developed mixed integer linear pro gramming models for the container loading problem that consider the vertical and horizontal stability of the cargo and the load bearing strength of the cargo. The models can also be used for loading rectangular boxes on pallets where the boxes do not need to be arranged in horizontal layers on the pallet. A comprehensive performance ana lysis using optimization software with 100s of randomly generated instances showed that those developed models are able to handle only problems of a moderate size. Terno et al. [15] employed a different heuristic algori thm. In addition to the dimension and overlapping con straint, they took total weight limit of the pallet and the stability constraints into account. They employed a laye ring approach while packing each layer by using a branch and bound solution method. They solved 700 problem sets among the problems that Bischoff et al. [16] solved and made comparisons with past work. Their solutions were better than Bischoff et al.’s solutions, but since their model was mainly designed for the “Manufacturer’s Pal let Packing Problem”, as the number of different items increases the volume utilization declines. Martello et al. [6] developed a branchandbound me thod to solve the threedimensional packing problem. They tried to orthogonally pack all the items into the mi nimum number of pallets. A computational test was pre sented showing that problems with the number of boxes less than 30 and 50 were solved. One weakness of their method is that when the average number of items per pallet gets bigger, the problem becomes harder to solve. Another weakness was that they assumed that the items might not be rotated. They considered only basic type of constraints (overlapping and pallet dimension limits). Ballew [17] developed a mathematical formulation si milar to the analytical method of Chen et al. [18], by us Copyright © 2011 SciRes. JSSM
Solving the ThreeDimensional PaletPaking Problem Using Mixed 0  1 Model515 ing nonlinear integer programming on a simplified ver sion of the problem. He developed a general mathemati cal formulation. Unfortunately, when implemented, the solver package hyper lingo found a local optimum to a very simplified and small problem of just three boxes wi thout considering several important constraints. The formu lation of a bigger problem with more boxes was unrealis tic because the number of variables and constraints in creases incredibly fast as the number of boxes increases. 3. Statement of the Problem The problem is a threedimensional palletpacking prob lem which is related to the two general types of pallet pa cking problems. These types are the “manufacturer’s pa llet packing problem” and the “distributor’s pallet pack ing problem.” The ‘manufacturer’s pallet packing prob lem’ is easier to solve since it seeks the optimum layout of identical rectangular boxes on a rectangularly shaped pallet. On the other hand, the “distributor’s pallet pack ing problem,” is more difficult to solve since the object tive is to load boxes of varying dimensions onto as few pallets as possible [19]. This objective changes to mini mize unused pallet space for the case in which only one pallet is loaded. However, most of the time, the items pa cked are rectangular, and this property makes the prob lem easier to solve, compared to trying to pack items wi th different shapes. The problem at hand is to pack as many boxes as pos sible from a given set of rectangularshaped items into a threedimensional rectangular pallet. The objective is to minimize the unused pallet volume while considering many different kinds of constraints. These constraints are explained in the Scope and Methodology Section. The purpose of this paper is to develop a threedimensional palletpacking model that can be solved using LINDO software. 4. Solution Methodology This paper proposes a zeroone mixed integer linear pro gramming model for the general threedimensional con tainerloading problem. The problem involves packing a set of nonuniform cartons into unequalsized containers. The model considers the issues of carton orientations, mul tiple carton sizes, multiple container sizes, avoidance of carton overlapping, and space utilization. This model is a modified version of the general palletpacking model. The modification to the general model is represented by introducing to the model other concerns of the container loading problem such as weight restriction. 4.1. The Proposed ThreeDimensional Pallet Loading Model The threedimensional palletloading model is a mixed 0  1 integerprogramming model which generates an exact optimal solution. The solution of the mixed 0  1 model explicitly defines the desired number of boxes of each size and the x, y, z coordinates of each box’s placement location on the pallet. A branchandbound technique is employed to solve the mixed 0  1 integerprogramming model. 4.2. The Mixed 0  1 Model Consider a collection of boxes, expressed by set nS 12 ,,, n bb b h W Each box has length i l, width i, and height i. A loading of into a pallet of length , wid th , and height limit i b Sw L is an assignment of boxes to a position within the pallet such that: 1) No two boxes in the pallet overlap. 2) Each box is contained entirely with the pallet, with its sides parallel to the sides of the pallet. 3) The proportion of the number of boxes of a given si ze to the total number of boxes of a full pallet load must closely approximate the user’s specification. 4) The total of boxes’ weights must be less than the wei ght allowed to be in the pallet. An optimal loading is achieved if the use of pallet spa ce is maximized under the consideration of the above constraints. Boxes in set may or may not have the same dimen sions. In addition, the orientations of the boxes in set are fixed permanently. The length, width, and height of a box must be aligned with the length, width, and height of the pallet, respectively. Length is defined as the dimen sion along the Xaxis. Width is the dimension along the Yaxis, and height is the dimension along Zaxis in Car tesian coordinate space. In this paper, the orientation of box height is assumed to be fixed. Only the length and width of a box are interchangeable. Thus, a box can be placed either in the ( SS lwh ) or () directions on the pallet. Individual elements representing these two orien ttations must be separately included in set . In addition, the placement location of a box in Cartesian coordinate space is measured relative to the front bottom left corner of the box. wlh S 4.3. Initial Notation The following notation defines all symbols used for the formulations of threedimensional model. Denote: S: A collection of boxes to be considered, in par ticular, it is n , n b 12 ,,bb . ,, iii lwh: The dimensions of in set , and they are length, width, and height, respec tively. ii box bS ,,LW H: The dimensions of a pallet cube, and they are length, width, and height, respectively. ,, YZ : Pallet location in Cartesian coordinate Copyright © 2011 SciRes. JSSM
Solving the ThreeDimensional PaletPaking Problem Using Mixed 0  1 Model 516 space along the x, the y, and the zaxis, respectively. ,, iii yz : Decision variables; the x, y, z coordinates of placement location of the front bottom left corner of box . i k P: A binary decision variable associated with the  th box in set . k S Where 1 k P if Box k is loaded onto the pallet 0 k P if Box is discarded from set kS V: The volume of the pallet LW H k V: The volume of box ii klwh i R: The desired box proportion of type . k G: The weight of box . k G: Total boxes’ weight allowed. C: A subset of ; consists of all boxes of size S regardless of box orientation.  ,1 kk kkggg gg g Cblwhlwh or wlhkn : An extremely large number. r: Total number of box types, . rn Each box with different orientations, either in lwh S or must be individually considered in set . wlh 4.4. Preventing Box Overlaps This section describes the process of converting the re quirements of box overlap avoidance into mathematical constraints. Consider two partially overlapped boxes, A and B shown in Figure 1 (a). The projections of these boxes on the xy, the xz and the yz planes are illustrated in Figures 1 (b), (c) and (d), respectively. Figure 1. Boxes Overlaps. (a): Two overlapped boxes; (b): Illustrates overlap condition in X and Y; (c): Illustrates o verlap condition in X and Z; (d): Illustrates overlap condi tion in Y and Z. Suppose the location of box A is fixed, and that box B is free to move arbitrarily in Cartesian coordinate space. To avoid overlap of these two boxes, the following conditions must be satisfied: – AA xl (1) or ABB xl (2) A yyw A (3) or AB yyw B (4) A zz h A (5) or AB B zz h (6) where , AB ll: Lengths of boxes A and B, respectively. , AB ww: Widths of boxes A and B. , AB hh: Heights of boxes A and B. ,, AAA yz : Front bottom left corner coordinate of box A. ,, BB yz : Front bottom left corner coordinate of box B. At least one of these six constraints must hold to pre vent overlap of the two boxes. 4.5. Determination of Proportion of Assigned Number of Boxes in a Pallet The number of boxes of each type to be considered in set S can be determined using the following two equations. i nn R g (7) 11 rr ii ii nvV (8) where n: The number of boxes of type to be considered in set . S Equation (7) states that the ratio of the number of type boxes to the total number of boxes on a pallet should equal to R, the desired box proportion of type . E quation (8) indicates that the total cumulative box volu mes should equal to the pallet’s volume. By solving Equations (7) and (8), the number of boxes for type can be obtained as: 1 g gr ii i RV nRv (9) Copyright © 2011 SciRes. JSSM
Solving the ThreeDimensional PaletPaking Problem Using Mixed 0  1 Model517 4.6. Formulation of ThreeDimensional Model The threedimensional pallet loading problem can now be formulated as a mixed 0  1 integer programming model. Maximize 1 n kk k vP (10) Subject to: 1) Avoid overlap of boxes – ij xl ij (11) or – ij i xl ij (12) or i yy w j ij (13) or ij yy w i ij (14) or i zz h j ij (15) or ij zz h i ij (16) 2) Confine placement boundary kk XP k (17) ka YP k (18) k zZP k k (19) () kk XLl (20) k () kk YWw (21) k () k zZHh k k (22) 3) Weight limitation 11 n kk m km GP GP g (23) 4) Proportion of boxes assigned g m mC PR (24) 0,1 k P ,, 0 kkk Xyx 1, 2,,1in 1,2, ,ji in 1, 2,,kn 1, 2,, r The front bottom left corner of the pallet is located at the coordinate ,, YZ in Cartesian coordinate spa ce. The location of the pallet ,, YZ is selected such that all boxes in set can be completely placed into the large cube. S The values of ,, YZ may be determined using the following expressions: max , i nl x , i w xi maYn ma nh 1 k P . The objective function, Equation (10), maximizes the total pallet volume occupied by boxes to be loaded. In the final solution, any box having is used to construct a pallet pattern. Any box having 0 k P is discarded from consideration. This formulated mixed 0  1 integerprogramming model for the threedimensional palletloading problem thus gives the required number of boxes of each type, i.e., every box whose associated k equals to one. It also generates the exact placement of a box on the pallet, namely the coordinate P ,, kkk yz . 4.7. Converting MultipleChoice Constraints Equations (11)  (16) in the model make the problem one of multiplechoice programming. To apply existing algo thms for mixed 0  1 integer programming, the multiple choice (either/or) constraints must be converted to stan rd “AND” constraints. The conversion can be accomli shed by introducing additional binary variables (Table 1) for each set of multiplechoice constraints. The six possible combinations of different binary values are: u1 u 2 u 3 1 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0 1 Table 1. Binary variable and associated RHS values. Binary variablesRHS values of equations U1U2U3(25) (26) (27) (28) (29) (30) Applicable Constraint Equation 1 0 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 1 –lj M M M 2M M M –li M M M 2M M M –wj 2M M M M M 2M –wi M M 2M M M M –hj M M 2M M M M –hi (25) (26) (27) (28) (29) (30) Copyright © 2011 SciRes. JSSM
Solving the ThreeDimensional PaletPaking Problem Using Mixed 0  1 Model 518 The multiple choice constraints of Equations (11)  (16) in the model are equivalent to: 23ji j xlMuu (25) 13ij j xlMuu (26) 12ji j ywMuu (27) 12 2 ij i yy wMuu (28) 23 2 ji j zz hMuu (29) 13 2 ij i zz hMuu (30) where: 123 12uuu 123 ,,,0,1uuu 4.8. Box Proportions Users of the proposed developed model can determine the value of R (box proportions) by using the follow ing equation: 1 Number ofboxes oftype umber ofboxes oftype gn i Ri (30) Where () is the number of distinct box types. r Since different box orientations must be considered separately in set , set contains en tries which exceed the value of . If 12 ,, , n Bbb b r B R s not placed in the model’s constraints, the optimal solution may generate a pallet pattern that contains only identical boxes. 5. Testing and Validating the Proposed Model In order to test the efficiency of the proposed model, an illustrative example is presented first to explain how the model formatted. Then, the model is tested utilizing five problems randomly selected from the OR library that is shown in the reference. 5.1. Numerical Example Consider a distribution warehouse using 36" by 24" pal lets for shipment. The stacking height limit of a pallet load is 16". The maximum load capacity allowed is 60 lb. A customer order requests 100 units of product A and 200 units of product B. Product A is packaged using carton with the height of 16" and weigh 15 lb. Product B uses carton with the height of 8" and weigh 20 lb. 12" 24" 24" 24" Prior to formulating the 3dimensional model, a colle ction of cartons, sets, and the location of the pallet in Cartesian coordinate space ,, Table 2. Example parameter. BoxProductLengthWidthHeight Volume Coordinatei P i b i b i b i b i b 1 bA 12 24 16 4608 111 ,, yz 1 P 2 bA 24 12 16 4608 222 ,, yz 2 P 3 bB 24 24 8 4608 333 ,, yz 3 P 4 bB 24 24 8 4608 444 ,, yz 4 P 11001002001 3R and carton proportion of B is equal to; 22001002002 3R. The number of boxes of individual types to be considered in set S can also determined 1, 2 AB nn 12" 24" . Since a carton is not square, a carton with dimensions 24"12" must be included in set S, there fore: 1234 ,,,Sbbbb Where: 112"24" 16"b 224" 12" 16"b 324" 24" 8"b 424"24" 8"b Let , ,100,100,100XYZ and 500M The model will be as following: Maximize 123 4608460846084608 4 PPPP Subject to: 2 112 13 24 500 xu u 1211 13 12 500 xuu 2111 12 12 500 yu u 1211 12 24500 2yyu u 2 11213 16500 2zz uu 1 211 13 16500 2zzu u 11 1213 12uuu 3 12223 24 500 xu u 1 32123 12 500 xuu 3 121 22 24 500 yu u 1321 22 24500 2yyuu 3 12223 85002zzu u 1 32123 16500 2zzu u YZ must be deter mined. Carton proportion of product A is equal to; 21 2223 12uuu Copyright © 2011 SciRes. JSSM
Solving the ThreeDimensional PaletPaking Problem Using Mixed 0  1 Model519 4 13233 24 500 xu u 1 431 33 12 500 xuu 4131 32 24 500 yuu 1431 32 24500 2yyu u 4 13233 8500 2zzuu 1 431 33 16500 2zzu u 31 3233 12uuu 3 24243 24 500 xu u 2 341 43 24 500 xu u 324142 24 500 yu u 2341 42 12500 2yy uu 3 24243 85002zzu u 2 341 43 16500 2zzuu 41 4243 12uuu 4 252 53 24 500 xu u 245153 24 500 xu u 425152 24 500 yu u 2451 52 12500 2yyuu 4 252 53 85002zzu u 2 451 53 16500 2zzu u 51 5253 12uu u 4 362 63 24 500 xu u 3 461 63 24 500 xuu 4361 62 24 500 yuu 3461 62 24500 2yyu u 4 36263 85002zzu u 3 461 63 85002zzu u 61 6263 12uuu 11 100 P 11 100yP 1100 P 11 100 3612x 1100 2424y 1100 1616z 22 100 P 22 100yP 22 100zP 2100 3624x 2100 2412y 2100 1616z 33 100 P 33 100yP 33 100zP 3100 3624x 3100 2424y 3100 168z 44 100 P 44 100yP 44 100zP 4100 3624x 4100 2424y 4100168z 12 1234 13PP PPPP 34 1234 23PP PPPP 1234 15 15202060PP P P 12 3 ,, 0,1 ii i uuu 12 3 ,, 0,1 ii i uuu ,, 0 iii xyz 1,2, 3,4i One of possible optimal solutions for the formulated problem is: 1234 ,, ,1,0,1,1PPPP 111 , ,124,100,100xyz 222 , ,100,100,84xyz 333 , ,100,100,108xyz 444 , ,100,100,100xyz 11 12 13 ,, 0,1,1uuu 2122 23 ,, 1,0,0uuu 31 32 33 ,, 1,0,0uuu 41 42 43 ,, 1,0,1uuu 51 52 53 ,, 1,0,1uuu 61 6263 ,, 0,1,1uuu Note that 20P and , ,100,100,84xyz 222 . This indicates that box 2 ,bb 4 and b 2is placed outside the valid pallet space. Therefore, only boxes 1, 3 and 4 13 are considered in the resulting pallet loading pattern. b Recall that the pallet’s corner is placed at coordi nate , ,100,100,100XYZ . By subtracting ,, Y Copyright © 2011 SciRes. JSSM
Solving the ThreeDimensional PaletPaking Problem Using Mixed 0  1 Model 520 the resulting placement location of a box ,, iii yz can be converted back to the original coordinates. This yield the following results that are illustrated in Figure 2: 111 , ,24,0,0xyz 333 ,, 0,0,8xyz 444 ,, 0,0,0xyz and 222 ,,0,0, 16xyz 5.2. The Efficiency of the Proposed Model Another four problems were randomly selected from OR library that is shown in the reference and run in LINDO software. It was noticed with increasing number of boxes included in the pallet, the execution time is significantly increased so that in the last problem the execution time exceeds 3 hours and the computer stopped running showing out a sign “out of memory.” All problems were running in Pentium(R) 4 CPU 1.7 GHz with 256 MB of RAM. The following table shows the change in the num ber of orientations associated with execution time. (Table 3). Therefore, another six problems were chosen in which 2 problems with two different box sizes, another two problems with three different box sizes and finally two problems with four different box sizes. All have different orientations forming 12 positions shapes. Unfortunately, none of them succeed to present a solution except when one of the constraint is removed such eliminating propor tion constraints. It may get a reasonable solution in a rea sonable time. Figure 2. The optimal pallet pattern of the numerical exam ple. Table 3. Execution time for selected proble ms. Problem number Number of orientation Execution time Result 1 4 5 seconds Optimum solution is obtained 2 6 15 seconds Optimum solution is obtained 3 10 24 minutes Optimum solution is obtained 4 12 3 hours and 40 minutes Stopped because of “out of memory.” 6. Results and Discussions The developed mixed 0  1 integer model for the three di mensional problem has been solved by using a branch and bound procedure, which employed linear program ming techniques to solve for continuous solutions. The branchandbound procedure did not destroy the primal feasibility of the LP solution. As a result, less computer memory and computation time were required. The formulated mixed 0  1 models provided exact so lutions for the palletpacking problem. However, use of 0  1 integer variables and multiple choice constraints may require extremely long computation times to reach final optimal solutions. The issue of the developed model’s com putation time requirements is addressed in more detail in the following: Computation Time Requirements The developed model has robust computation time re quirements. The computation time increases significantly as the number of boxes increases. The size of the mixed 0  1 integerprogramming problem is related to both the number of different box sizes and the number of different entries in set , previously described. Recall that. S n = the number of different boxes in set S, and r = the number of different box sizes. The developed model considers the location relation ship between every pair of entries in set S for each box size. Each pair of placement alternatives for each box may be denoted as: i b, and b, < ; ij,1,2,,ij n . It follows that there are 1nn2 combinations to be formulated. The problem size may now be formulated in terms of the number of variables and constraint equa tions. The problem size is a function of both the number of different box sizes and the number of elements in set S. If only one box orientation is permitted, the number of elements in set S may be reduced by half. Alternatively, if only boxes with identical lengths or widths or heights are considered, the problem may be reduced to two di mensions. Computation time increase exponentially as the number of different box sizes increases. Copyright © 2011 SciRes. JSSM
Solving the ThreeDimensional PaletPaking Problem Using Mixed 0  1 Model521 An illustrated example was conducted to evaluate the effectiveness of the developed model. Two different box sizes corresponding to four elements in set S were used. Computation times rang exceeds 45 seconds of processor time on a microcomputer. Also, it was obvious from Ta ble 3 that it was hard to get appropriate answer for the problems with four different box sizes forming 12 dif ferent positions shapes because of memory limitations. Therefore, these computational requirements limit the mo del’s use in realtime palletizing applications. The model was responsive to significant and immediate changes in the distributions of box sizes to be loaded. The continu ing evolvement of faster microcomputer hardware may remove the model’s limitation for use in realtime pallet izing applications in the foreseeable future. 7. Conclusions This paper has presented a transformation procedure for converting the three dimensional pallet loading problem to an exact mixed 0  1 integer programming model in which all position relationships among boxes must be considered. The position constraints can be determined by establishing the constraints specified by Equations (1)  (6). Since only two boxes are considered in each con straint set of Equations (1)  (6), there are n(n1)/2 com binations to be formulated. The developed model does not address the issue of load stability. Use of some sets of carton dimensions may result in some partial voids in the pallet pattern. These voids can be minimized or eliminated thorough the use of filler cartons or standardized carton dimensions. The com putational time requirements of the developed model pre vent its use in realtime palletizing applications. As mi crocomputer chip technology continues to evolve the len gthy computation time may prove to be less of a problem in real time applications. REFERENCES [1] E. G. Jr. Coffman and P. W. Shor, “AverageCase Analy sis of Cutting and Packing in TwoDimensions,” Euro pean Journal of Operational Research, Vol. 44, No. 2, 1990, pp. 134145. doi:10.1016/03772217(90)90349G [2] J. Verstichel, W. Vancroonenburg, W. Souffriau and G. V. Berghe, “A Mixed Integer Programming Approach to the Aircraft Weight and Balance Problem,” Procedia Social and Behavioral Sciences, No. 20, 2011, pp. 10511059. [3] W. Q. Huang and K. He, “An Efficient Algorithm for Solving the Container Loading Problem,” 2007. http://mscmga.ms.ic.ac.uk/jeb/orlib/thpackinfo.html [4] J. A. George and D. F. Robinson, “A Heuristic for Pack ing Boxes into a Container,” Computers and Operational Research, Vol. 7, 1980, pp. 147156. doi:10.1016/03050548(80)900015 [5] C. H. Che, W. Huang, A. Lim and W. Zhu, “The Multiple Container Loading Cost Minimization Problem,” Euro pean Journal of Operational Research, Vol. 214, 2011, pp. 501511. doi:10.1016/j.ejor.2011.04.017 [6] S. Martello, D. Pisinger and D. Vigo, “The ThreeDimen sional Bin Packing Problem,” Operations Research, In forms, Vol. 48, No. 2, 2000, pp. 256267. doi:10.1287/opre.48.2.256.12386 [7] T. Dereli and G. S. Das, “A Hybrid ‘Bee(s) Algorithm’ for Solving Container Loading Problems,” Applied Soft Computing, No. 11, 2011, pp. 28542862. doi:10.1016/j.asoc.2010.11.017 [8] J. Liu, Y. Yue, Z. Dong, C. Maple and M. Keech, “A Novel Hybrid Tabu Search Approach to Container Load ing,” Computers & Operations Research, No. 38, 2011, pp. 797807. [9] H. Gehring, K. Menschner and M. Meyer, “A Com PuterBased Heuristic for Packing Pooled Shipment Con tainers,” European Journal of Operational Research, Vol. 44, No. 2, 1990, pp. 277289. doi:10.1016/03772217(90)90363G [10] C. P. Han, K. Knott and P. J. Egbelu, “A Heuristic Ap proach to the ThreeDimensional CargoLoading Prob lem,” International Journal of Production Research, Vol. 27, No. 5, 1989, pp. 757774. doi:10.1080/00207548908942585 [11] H. J. Steudel, “Generating Pallet Loading Patterns: A Special Case of the TwoDimensional Cutting Stock Problem,” Management Science, Vol. 25, No. 10, 1979, pp. 9971004. doi:10.1287/mnsc.25.10.997 [12] B. B. Mohanty, K. Mathur and N. J. Ivancic, “Value Con siderations in ThreeDimensional Packing—A Heuristic Procedure Using the Fractional Knapsack Problem,” European Journal of Operational Research, Vol. 74, No. 1, 1994, pp. 143151. doi:10.1016/03772217(94)902127 [13] W. Kocjan and K. Holmstrِm, “Computing Stable Loads for Pallets,” European Journal of Operational Research, Vol. 207, No. 2, 2010, pp. 980985. doi:10.1016/j.ejor.2010.05.005 [14] L. Junqueira, R. Morabito and D. S. Yamashita, “Three Dimensional Container Loading Models with Cargo Sta bility and Load Bearing Constraints,” Computers & Op erations Research, Vol. 39, No. 3, 2012, pp. 7485. doi:10.1016/j.ejor.2010.05.005 [15] J. Terno, G. Scheithauer, U. Sommerweiß and J. Riehme, “An Efficient Approach for the MultiPallet Loading Problem,” Institute for Numerical Mathematics, Technical University Dresden Mommsenstr, Dresden, Vol. 13, 1997. [16] E. E. Bischoff and M. S. W. Ratcliff, “Issues in the De velopment of Approaches to Container Loading,” Omega Institute, Vol. 23, No. 4, 1995, pp. 377390. doi:10.1016/03050483(95)00015G [17] P. B. Ballew, “The Distributor’s ThreeDimensional Pal letPacking Problem: A Mathematical Formulation and Heuristic Solution Approach,” MS Thesis, Graduate School of Engineering, Air Force Institute of Technology (AU), Wright Patterson AFB OH, 2000. [18] C. S. Chen, S. M. Lee and Q. S. Shen, “An Analytical Copyright © 2011 SciRes. JSSM
Solving the ThreeDimensional PaletPaking Problem Using Mixed 0  1 Model Copyright © 2011 SciRes. JSSM 522 Model for Container Loading Problem,” European Jour nal of Operational Research, Vol. 80, No. 1, 1995, pp. 6876. doi:10.1016/03772217(94)00002T [19] R. G. Askin, and R. S. Charles, “Modeling and Analysis of Manufacturing Systems,” John Wiley and Sons Inc., New York, 1993, pp. 320321.
