Journal of Service Science and Management, 2011, 4, 513-522
doi:10.4236/jssm.2011.44059 Published Online December 2011 (http://www.SciRP.org/journal/jssm)
513
Solving the Three-Dimensional Palet-Paking
Problem Using Mixed 0 - 1 Model
Adel Mohammed Al-Shayea
Industrial Engineering Department, College of Engineering, King Saud University, Riyadh, Saudi Arabia.
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 NP-hard problem to reduce the time, energy and other resources
spent in pa cking pallets. In this pap er, the three-dimensional 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 pallet-packing prob-
lem. The computational time requirements of the developed model prevent its use in real-time 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, 3-D 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 pallet-loading prob-
lem is a problem with many different variants. The early
form of this type of problem was the one-dimensional
loading or packing problem, in which a set of posi-
tive values
n
j
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 two-dimensional of pallet-loading problem ex-
tends the one-dimensional pallet-loading 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 two-dimensional pallet-
loading problems [3-5].
W
These pallet-loading problems are NP-hard problems.
NP stands for ‘non-deterministic polynomial’. NP-hard
means the solution time increases exponentially as the si-
ze of the problem increases. The three-dimensional pallet-
loading problem is strongly NP-hard because the three-
dimensional pallet-loading problem is a special case of
the one-dimensional problem [6,7].
The three-dimensional packing problem is a natural
generalization of the classical one- and two-dimensional
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, two-dimen-
sional pallet packing heuristics are applied to the general
three-dimensional container-loading problem. These heu-
ristics are, in general, on-line packing algorithms, which
mean they pack boxes one-by-one 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 Three-Dimensional Palet-Paking 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 pallet-packing 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
non-identical 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 L-shaped
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 L-shaped 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 multi-dimensional kna-
psack problem approach to the three-dimensional 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 branch-and-bound me-
thod to solve the three-dimensional 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-

Solving the Three-Dimensional Palet-Paking 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 three-dimensional pallet-packing 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 rectangular-shaped items into a
three-dimensional 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 three-dimensional
pallet-packing model that can be solved using LINDO
software.
4. Solution Methodology
This paper proposes a zero-one mixed integer linear pro-
gramming model for the general three-dimensional con-
tainer-loading problem. The problem involves packing a
set of non-uniform cartons into unequal-sized 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 pallet-packing 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 Three-Dimensional Pallet
Loading Model
The three-dimensional pallet-loading model is a mixed 0
- 1 integer-programming 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 branch-and-bound technique is
employed to solve the mixed 0 - 1 integer-programming
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
H
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 X-axis. Width is the dimension along the
Y-axis, and height is the dimension along Z-axis 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 three-dimensional 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.


,,
X
YZ

: Pallet location in Cartesian coordinate

Solving the Three-Dimensional Palet-Paking Problem Using Mixed 0 - 1 Model
516
space along the x-, the y-, and the z-axis,
respectively.

,,
iii

x
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


g
R: The desired box proportion of type
g
.
k
G: The weight of box . k
G: Total boxes’ weight allowed.
g
C: A subset of ; consists of all boxes of size S
g
regardless of box orientation.




|
,1
g
kk kkggg
gg g
Cblwhlwh
or wlhkn

 
M
: 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 x-y, the x-z and the y-z 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:
–
B
AA
x
xl (1)
or
ABB
x
xl

 (2)
B
A
yyw
A

 (3)
or
AB
yyw
B

 (4)
B
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
x
yz : Front bottom left corner coordinate of
box A.


,,
B
BB
x
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.
g
i
nn R
g

(7)
11
rr
ii
ii
nvV



 (8)
where
g
n: The number of boxes of type
g
to be considered
in set . S
Equation (7) states that the ratio of the number of type
g
boxes to the total number of boxes on a pallet should
equal to
g
R, the desired box proportion of type
g
. 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
g
can be obtained as:
1
g
gr
ii
i
RV
nRv

 (9)

Solving the Three-Dimensional Palet-Paking Problem Using Mixed 0 - 1 Model517
4.6. Formulation of Three-Dimensional Model
The three-dimensional pallet loading problem can now be
formulated as a mixed 0 - 1 integer programming model.
Maximize
1
n
kk
k
Z
vP

 (10)
Subject to:
1) Avoid overlap of boxes
–
–
j
ij
x
xl ij

(11)
or
–
–
ij i
x
xl ij

(12)
or
j
i
yy w
j
ij

(13)
or
ij
yy w
i
ij

(14)
or
j
i
zz h
j
ij

(15)
or
ij
zz h
i
ij

(16)
2) Confine placement boundary
kk
x
XP k

(17)
ka
y
YP k

(18)
k
zZP
k
k

(19)
()
kk
x
XLl
 (20) k
()
kk
y
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,,
g
r
The front bottom left corner of the pallet is located at
the coordinate

,,

X
YZ
 
in Cartesian coordinate spa-
ce. The location of the pallet

,,

X
YZ
 
is selected
such that all boxes in set can be completely placed
into the large cube.
S
The values of ,,
X
YZ

may be determined using the
following expressions:

max ,
i
X
nl

x ,
i
w

xi
 

 maYn 

ma
Z
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 integer-programming model for the three-dimensional
pallet-loading 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
x
yz .
4.7. Converting Multiple-Choice Constraints
Equations (11) - (16) in the model make the problem one
of multiple-choice 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 multiple-choice 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)

Solving the Three-Dimensional Palet-Paking Problem Using Mixed 0 - 1 Model
518
The multiple choice constraints of Equations (11) - (16)
in the model are equivalent to:


23ji j
x
xlMuu (25)


13ij j
x
xlMuu (26)


12ji j
y
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
g
R (box proportions) by using the follow-
ing equation:
1
Number ofboxes oftype
N
umber ofboxes oftype
gn
i
g
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
g
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 3-dimensional 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
,,
x
yz 1 P
2
bA 24 12 16 4608

222
,,
x
yz 2 P
3
bB 24 24 8 4608 
333
,,
x
yz 3 P
4
bB 24 24 8 4608

444
,,
x
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
Z
PPPP


Subject to:


2 112 13
24 500
x
xu u


1211 13
12 500
x
xuu


2111 12
12 500
y
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
x
xu u


1 32123
12 500
x
xuu


3 121 22
24 500
y
yu u


1321 22
24500 2yyuu 






3 12223
85002zzu u


 




1 32123
16500 2zzu u

  



X
YZ
 
must be deter-
mined. Carton proportion of product A is equal to; 21 2223
12uuu

 

Solving the Three-Dimensional Palet-Paking Problem Using Mixed 0 - 1 Model519

4 13233
24 500
x
xu u

1 431 33
12 500
x
xuu

4131 32
24 500
y
yuu

1431 32
24500 2yyu u  


4 13233
8500 2zzuu   


1 431 33
16500 2zzu u

 

31 3233
12uuu 

3 24243
24 500
x
xu u

2 341 43
24 500
x
xu u

324142
24 500
y
yu u

2341 42
12500 2yy uu 


3 24243
85002zzu u

 


2 341 43
16500 2zzuu

 

41 4243
12uuu 

4 252 53
24 500
x
xu u

245153
24 500
x
xu u

425152
24 500
y
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
x
xu u

3 461 63
24 500
x
xuu

4361 62
24 500
y
yuu

3461 62
24500 2yyu u

 


4 36263
85002zzu u

 


3 461 63
85002zzu u   

61 6263
12uuu 
11
100
x
P
11
100yP
1100
z
P

11
100 3612x

1100 2424y

1100 1616z
22
100
x
P
22
100yP
22
100zP


2100 3624x




2100 2412y




2100 1616z


33
100
x
P
33
100yP
33
100zP


3100 3624x




3100 2424y




3100 168z


44
100
x
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

,,
X
Y


Solving the Three-Dimensional Palet-Paking Problem Using Mixed 0 - 1 Model
520

Z
 the resulting placement location of a box


,,
iii
x
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
branch-and-bound 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 pallet-packing 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 integer-programming 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
j
b, < ; ij,1,2,,ij n



.
It follows that there are 1nn2 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.

Solving the Three-Dimensional Palet-Paking 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 real-time 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 real-time 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(n-1)/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 real-time 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, “Average-Case Analy-
sis of Cutting and Packing in Two-Dimensions,” Euro-
pean Journal of Operational Research, Vol. 44, No. 2,
1990, pp. 134-145. doi:10.1016/0377-2217(90)90349-G
[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. 1051-1059.
[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. 147-156.
doi:10.1016/0305-0548(80)90001-5
[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. 501-511. doi:10.1016/j.ejor.2011.04.017
[6] S. Martello, D. Pisinger and D. Vigo, “The Three-Dimen-
sional Bin Packing Problem,” Operations Research, In-
forms, Vol. 48, No. 2, 2000, pp. 256-267.
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. 2854-2862.
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. 797-807.
[9] H. Gehring, K. Menschner and M. Meyer, “A Com-
Puter-Based Heuristic for Packing Pooled Shipment Con-
tainers,” European Journal of Operational Research, Vol.
44, No. 2, 1990, pp. 277-289.
doi:10.1016/0377-2217(90)90363-G
[10] C. P. Han, K. Knott and P. J. Egbelu, “A Heuristic Ap-
proach to the Three-Dimensional Cargo-Loading Prob-
lem,” International Journal of Production Research, Vol.
27, No. 5, 1989, pp. 757-774.
doi:10.1080/00207548908942585
[11] H. J. Steudel, “Generating Pallet Loading Patterns: A
Special Case of the Two-Dimensional Cutting Stock
Problem,” Management Science, Vol. 25, No. 10, 1979,
pp. 997-1004. doi:10.1287/mnsc.25.10.997
[12] B. B. Mohanty, K. Mathur and N. J. Ivancic, “Value Con-
siderations in Three-Dimensional Packing—A Heuristic
Procedure Using the Fractional Knapsack Problem,”
European Journal of Operational Research, Vol. 74, No.
1, 1994, pp. 143-151. doi:10.1016/0377-2217(94)90212-7
[13] W. Kocjan and K. Holmstrِm, “Computing Stable Loads
for Pallets,” European Journal of Operational Research,
Vol. 207, No. 2, 2010, pp. 980-985.
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. 74-85.
doi:10.1016/j.ejor.2010.05.005
[15] J. Terno, G. Scheithauer, U. Sommerweiß and J. Riehme,
“An Efficient Approach for the Multi-Pallet 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. 377-390.
doi:10.1016/0305-0483(95)00015-G
[17] P. B. Ballew, “The Distributor’s Three-Dimensional Pal-
let-Packing 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

Solving the Three-Dimensional Palet-Paking Problem Using Mixed 0 - 1 Model
522
Model for Container Loading Problem,” European Jour-
nal of Operational Research, Vol. 80, No. 1, 1995, pp.
68-76. doi:10.1016/0377-2217(94)00002-T
[19] R. G. Askin, and R. S. Charles, “Modeling and Analysis
of Manufacturing Systems,” John Wiley and Sons Inc.,
New York, 1993, pp. 320-321.