New Warehouse Designs: Angled Aisles and Their E ects on Travel
Distance
by
Omer Ozt urko glu
A dissertation submitted to the Graduate Faculty of
Auburn University
in partial ful llment of the
requirements for the Degree of
Doctor of Philosophy
Auburn, Alabama
August 6, 2011
Keywords: warehouse, distribution center, aisle design, pickup and deposit point
Copyright 2011 by Omer Ozt urko glu
Approved by
Kevin R. Gue, Chair, Associate Professor of Industrial and Systems Engineering
Alice E. Smith, Professor of Industrial and Systems Engineering
Robert L. Bul n, Professor of Industrial and Systems Engineering
Russell D. Meller, Professor of Industrial Engineering, University of Arkansas
Abstract
In supply chain and logistics systems, warehouses and third-party logistics cen-
ters have become the backbone of distribution networks that store and deliver goods.
However, these facilities are still built to look much as they have been for the past
fty years (Gue and Meller, 2009). This dissertation builds on some recent research
that challenges traditional ways of organizing picking aisles and cross aisles in unit-
load warehouses. The designs in this dissertation, and the models that produced
them, o er to the research and practicing communities a new and fundamentally
di erent way to extract cost and improve the performance of industrial warehouses.
For warehouses with one, two and three cross aisles, we develop closed form,
single-command travel distance functions in a continuous warehouse space. We use
these functions to minimize expected travel distance in a unit-load warehouse with
a centrally located pickup and deposit (P&D) point under randomized storage. We
propose three optimal unit-load warehouses with respect to the inserted cross aisles,
the Chevron, the Leaf and the Butter y. In order to provide a more accurate model
and to analyze the wasted space for angled aisle designs, we build a discrete model
of aisles and pallet locations that better represents warehouse designs.
We develop a general warehouse design tool that models aisles, pallet locations
and dock doors as discrete objects. The tool implements a network representation of
the warehouse, a shortest path algorithm to determine travel distances, and a particle
swarm meta-heuristic to search for the best arrangement of aisles. To illustrate the
use of model, we de ne ve design problems that are di erentiated by the locations
of multiple P&D points. We propose improved non-traditional aisle designs for each
design problem with one and two inserted cross aisles.
ii
Last, we introduce the idea of robustness in non-traditional aisle designs with
respect to a varying number of P&D points. For two commonly found ow patterns
in industry, we use our models to determine optimal designs for an increasingly large
block of P&D points to nd the point at which the structure \breaks." The results
suggest that the Chevron design, in particular, is robust over a wide range of P&D
points.
iii
Acknowledgments
If the pages of this dissertation could talk, they would say that this dissertation
is far more than the culmination of years of study. This dissertation has been a
big portion of my life in the past ve years. Today, I stand on my own two feet
with the honor of completing my doctoral study with the support of many generous,
admirable, inspiring and honorable people.
First, I would like to express my deepest gratitude to my advisor, Dr. Kevin
R. Gue, for his excellent guidance, support, and for providing me with an excellent
atmosphere for doing research. His knowledge, wisdom and commitment to the
highest standards of academic excellence contributed to my development as a scholar
and teacher.
I would also like to thank my committee members, Dr. Alice E. Smith, Dr. Robert
L. Bul n and Dr. Russell D. Meller for guiding my research and for their thoughtful
criticism, time and attention. I am grateful to the National Science Foundation,
which supported this research under Grants DMI-0600374 and DMI-0600671, the
Material Handling Education Foundation, which honored me with a scholarship,
and the Auburn University Industrial and Systems Engineering Department and
Graduate School, which funded my graduate work.
I would probably have not completed my dissertation without the support of
several people: my grandparents, parents, sister, my wife and, of course, my daugh-
ter. I would like to thank my grandparents, Sevim and Abit, for their endless support
since my childhood. I would like to express my deepest gratitude and love to my
parents, _Ifakat and Halil, for their presence, endless support, love and understand-
ing during my whole life. I would like thank my sister, Ozlem, for her best wishes
iv
and for supporting my parents when I am far away from them. I would also like to
apologize to her for missing her gorgeous wedding and thank for her understanding.
I would like to thank my wife, Y ucel, for her understanding, patience and love
during the last seven years. I thank her being with me and loving me during both
good days and bad, and also further dedication through hard times that we faced in
the past ve years. She deserves a medal.
Last, but not least, of course, I would like to thank to my little \pure light",
Duru Nur for her patience, good behavior, especially when I am not with her. I still
remember her saying \do not leave, daddy!", when I needed to go to the o ce at
nights. I also feel sorry for missing her third birthday and not being with her for
ve months. My little daisy, I will always love you.
I dedicate this dissertation to my parents. I aspire to guide my daughter.
v
Table of Contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi
1 Warehousing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Organization of the Dissertation . . . . . . . . . . . . . . . . . . . . . 5
2 Warehouse Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Receiving and Shipping . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 Picking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3 Designing Warehouses . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 Non-Traditional Aisle Designs . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Material Flow Designs in Nature and Other Structures . . . . . . . . 21
4 Optimal Unit-Load Warehouse Designs for Single Command Operations 25
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2 Related Literature . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.3 One Cross Aisle Warehouse Designs . . . . . . . . . . . . . . . . . . . 30
4.3.1 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.3.2 One Cross Aisle Designs for Non-Square Half-Warehouses . . 35
4.4 A Two Cross Aisle Design . . . . . . . . . . . . . . . . . . . . . . . . 36
vi
4.5 Three Cross Aisle Design . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.6 Comparison of Continuous Warehouse Designs . . . . . . . . . . . . . 45
4.7 A Continuum of Designs . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.8 Implications for Practice . . . . . . . . . . . . . . . . . . . . . . . . . 53
5 Non-Traditional Unit-Load Warehouse Designs with Multiple Pickup-
and-Deposit Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.2 Previous Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.3 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.4 The Warehouse Network Model . . . . . . . . . . . . . . . . . . . . . 61
5.5 Optimization Methodology: Particle Swarm Optimization (PSO) . . . 65
5.5.1 Formulation of the problem . . . . . . . . . . . . . . . . . . . 66
5.5.2 PSO Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.6 Optimization of Layouts for Unit-Load Warehouses . . . . . . . . . . 74
5.6.1 Design Problem A . . . . . . . . . . . . . . . . . . . . . . . . 76
5.6.2 Design Problem B . . . . . . . . . . . . . . . . . . . . . . . . 83
5.6.3 Design Problem C . . . . . . . . . . . . . . . . . . . . . . . . 88
5.6.4 Design Problem D . . . . . . . . . . . . . . . . . . . . . . . . 94
5.6.5 Design Problem E . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.7 Computational Complexity . . . . . . . . . . . . . . . . . . . . . . . . 101
5.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6 Robustness of Non-Traditional Aisle Designs with respect to a Varying
Number of P&D Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
6.2 Model and Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.3 Unit-Load Warehouse Designs with P&D Points at the Bottom of the
Warehouse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.3.1 One Cross Aisle Designs . . . . . . . . . . . . . . . . . . . . . 108
vii
6.3.2 Two Cross Aisle Designs . . . . . . . . . . . . . . . . . . . . . 111
6.4 Unit-Load Warehouse Designs with P&D Points at the Bottom and
the Top of the Warehouse . . . . . . . . . . . . . . . . . . . . . . . . 115
6.4.1 One Cross Aisle Designs . . . . . . . . . . . . . . . . . . . . . 115
6.4.2 Two Cross Aisle Designs . . . . . . . . . . . . . . . . . . . . . 118
6.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
7 Conclusions and Future Research . . . . . . . . . . . . . . . . . . . . . . 122
7.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
7.2 Future Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
7.2.1 Dynamics of inserted P&D points . . . . . . . . . . . . . . . . 126
Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
A.1 Closed form expressions for E[WR] . . . . . . . . . . . . . . . . . . . 139
A.2 Proof of Observation 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 139
A.3 Expected travel distances in a three cross aisle model . . . . . . . . . 140
A.4 Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
B.1 Two Cross Aisle Model Cases . . . . . . . . . . . . . . . . . . . . . . 144
B.2 Computational Results in Design Problem A . . . . . . . . . . . . . . 146
B.2.1 Results for Design A1 . . . . . . . . . . . . . . . . . . . . . . 146
B.2.2 Results for Design A2 . . . . . . . . . . . . . . . . . . . . . . 149
B.3 Computational Results in Design Problem B . . . . . . . . . . . . . . 152
B.3.1 Results for Design B1 . . . . . . . . . . . . . . . . . . . . . . . 152
B.4 Computational Results in Design Problem C . . . . . . . . . . . . . . 158
B.4.1 Results for Design C1 . . . . . . . . . . . . . . . . . . . . . . . 158
B.4.2 Results for Design C2 . . . . . . . . . . . . . . . . . . . . . . . 161
B.5 Computational Results in Design Problem D . . . . . . . . . . . . . . 164
B.6 Computational Results in Design Problem E . . . . . . . . . . . . . . 167
viii
B.6.1 Results for Design E1 . . . . . . . . . . . . . . . . . . . . . . . 167
B.6.2 Results for Design E2 . . . . . . . . . . . . . . . . . . . . . . . 167
C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
C.1 One Cross Aisle Designs with P&D Points at the Bottom of the Ware-
house . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
C.2 Two Cross Aisle Designs with P&D Points at the Bottom of the Ware-
house . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
C.3 One Cross Aisle Designs with P&D Points at the Bottom and the Top
of the Warehouse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
C.4 Two Cross Aisle Designs with P&D Points at the Bottom and the
Top of the Warehouse . . . . . . . . . . . . . . . . . . . . . . . . . . 178
ix
List of Figures
1.1 Traditional warehouse designs. . . . . . . . . . . . . . . . . . . . . . . . 3
3.1 A traditional warehouse layout with design elements. . . . . . . . . . . . 16
3.2 Two main variations of traditional warehouses. . . . . . . . . . . . . . . 16
3.3 Non-rectangular warehouses with radial aisles (White, 1972). N is the
number of regions that are de ned by radial cross aisles. Travel in these
regions is along the cross aisles rst and then parallel to either x or y axis. 19
3.4 Proposed designs for a single P&D point by Gue and Meller (2009). . . . 20
3.5 Proposed designs for multiple P&D points at the bottom of the ware-
house by Gue et al. (2010). . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.6 A continuum of veins in a leaf that is developed and represented by
Runions et al. (2005). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.7 A developed orchid leaf by Runions et al. (2005). . . . . . . . . . . . . . 23
3.8 (a) The picture shows the Palis de Chailot and Jardins du Trocadero. It is
taken from the Ei el Tower by \http://www.planetware.com/picture/paris-
palais-de-chaillot-f-f1037.htm." (b) By Rolland et al. (2011). . . . . . . . 23
4.1 Traditional rectangular warehouse. . . . . . . . . . . . . . . . . . . . . . 26
4.2 The Flying-V (Left) and Fishbone (Right). . . . . . . . . . . . . . . . . . 28
4.3 One cross aisle warehouse design. . . . . . . . . . . . . . . . . . . . . . . 30
x
4.4 Example travel paths based on some possible R?s. . . . . . . . . . . . . 32
4.5 The representation of case 1 (left) and case 2 (right) for the one cross
aisle model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.6 The optimal one cross aisle design. . . . . . . . . . . . . . . . . . . . . . 35
4.7 Change in optimal R for non-square half-warehouses. Solid lines rep-
resent optimal angles of picking aisles; dashed lines with circle markers
represent angles of the diagonal on the right side. . . . . . . . . . . . . . 36
4.8 A two cross aisle warehouse. . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.9 (a) An infeasible symmetric warehouse design with two cross aisles when
RC < 90?, (b) sample travel paths to the point P with di erent RC. . . . 37
4.10 Cases in the two cross aisle model. . . . . . . . . . . . . . . . . . . . . . 38
4.11 Travel paths according to the de ned areas in two cross aisle design.. . . 39
4.12 The Leaf: Optimal two cross aisle design for square half-warehouses. . . 41
4.13 Travel paths in regions on the right side of the three cross aisle design. . 41
4.14 Cases in the three cross aisle model. . . . . . . . . . . . . . . . . . . . . 42
4.15 Representation of the Butter y design. . . . . . . . . . . . . . . . . . . . 46
4.16 Equally distributed imperfections in designs. . . . . . . . . . . . . . . . . 47
4.17 Equal travel distance in dual designs shown via parallelogram. . . . . . . 48
4.18 The Chevron design. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.19 The Leaf design. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
xi
4.20 The Butter y design. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.21 Comparison of several approximately square half-warehouses with an
equivalent traditional warehouse. (Data for the plots are in Appendix A.4.) 52
4.22 Chevron versus Traditional in an equivalent small size warehouse: Chevron
has lower expected distance, but requires more space. . . . . . . . . . . . 52
4.23 An implementation of non-traditional aisles at Generac Power Systems. . 55
5.1 Traditional rectangular warehouses. . . . . . . . . . . . . . . . . . . . . . 56
5.2 The Modi ed Flying-V and the Inverted-V designs for multiple P&D
points. From Gue et al. (2010). . . . . . . . . . . . . . . . . . . . . . . . 58
5.3 The intersecting and non-intersecting cross aisles in a warehouse. . . . . 60
5.4 Description of the warehouse design tool . . . . . . . . . . . . . . . . . . 61
5.5 The procedure to represent a discrete space warehouse design for given
set of parameters. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.6 Network representation of a small, example warehouse. (Each storage
location is represented by an access node in a real network.) . . . . . . . 63
5.7 Possible arrangements of one cross aisle. (Numbers on the cross aisles
represent cases in the one cross aisle model.) . . . . . . . . . . . . . . . . 68
5.8 Possible directions of cross aisles . . . . . . . . . . . . . . . . . . . . . . 68
5.9 Possible region de nitions and angles of aisles in these region. . . . . . . 69
5.10 Issues show that the variable goes out of its boundary if vtisd is applied,
when 0 90?. By the triangle inequality,
jOAj+jAXjh, the
optimal R decreases as w=h increases (the warehouse gets wider), but it remains
above the diagonal.
35
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
2 4 6 8 10
h?w
0
20
40
60
80
angle?
Figure 4.7: Change in optimal R for non-square half-warehouses. Solid lines rep-
resent optimal angles of picking aisles; dashed lines with circle markers represent
angles of the diagonal on the right side.
P&D w w
h
RC LC
R L
Figure 4.8: A two cross aisle warehouse.
4.4 A Two Cross Aisle Design
In this section we insert into the warehouse two angled cross aisles, in addition
to the bottom cross aisle. We call this design a two cross aisle warehouse.
We make the same assumptions discussed in the one cross aisle model. There-
fore, the two angled cross aisles are placed on each side, symmetric with respect to
a vertical axis drawn through the P&D point. This axis divides the warehouse into
two equal parts. We use the following variables depicted Figure 4.8.
Variables:
R, L angles of the right and left cross aisles
R, L angles of picking aisles in the rightmost and leftmost sections
RC, LC angles of the central picking aisles on the right and left sides
36
Because the feasible space for angles of picking and cross aisles has many cases
to consider, we prove two propositions to limit the search space. Additionally, it is
enough to search for the optimal RC, because RC and LC are symmetric.
Proposition 4.3. In an optimal two cross aisle design, LC = RC = 90?.
Proof. When RC <90?, we have an infeasible design because some locations in the
central region are unreachable (see Figure 4.9a). Now consider RC 90? in Fig-
ure 4.9b, and let point P be a random storage location on the right side of the central
region. Point O is the P&D point. Let A, B, and C be points of access to the picking
aisle containing point P corresponding to RC = 90?, 90? < RC < 180?, RC = 180?
respectively. Path OA is common travel for all three paths in Figure 4.9b. From the
triangle inequality,
jAPj 0;
@2E[WR2]
@ 2R
arccos 6 +
p6
10 ; =2 arccos
6 +p6
10
!
> 0;and
@2E[WR2]
@ 2R
arccos 6 +
p6
10 ; =2 arccos
6 +p6
10
!
> 0:
where H is the Hessian matrix of E[WR2]. We veri ed these inequalities in Math-
ematica. Because the determinant of H is not always greater than or equal to 0
for all possible values of R and R in their de ned ranges, E[WR2] is not posi-
tive semi-de nite and not convex. However, we applied the Extreme Value Theo-
rem to check the boundaries of E[WR2]. For this, we solve f R( R; R) = 0 and
f R( R; R) = 0 simultaneously by xing one of the boundary conditions ( R = 0?,
R = 45?, R = 45? and R = 90?) and solving for the other variable. Based on the
four solutions, we see that the values of E[WR2] at its boundaries are greater than
40
P&D w w
h
R 32.33? L 147.67?
C =90? R 57.67? L 122.33?
Figure 4.12: The Leaf: Optimal two cross aisle design for square half-warehouses.
P&D w w
h
R L C
R
L
CR
CL
B
A
CD
Figure 4.13: Travel paths in regions on the right side of the three cross aisle design.
the local optimum. Similar analysis for case 1 and case 3 also yields local optima
greater than the local optimum for case 2. The single root for case 1 is: = =4
and R = arcsin(p2 1). For case 3, = =2 and R = =4. Hence, although
E[WR2] is not convex,
arccos 6+
p6
10 ; =2 arccos
6+p6
10
is the global minimum be-
cause there is an unique root, it is the local optimum, and the extreme values are
larger.
Figure 4.12 illustrates the optimal two cross aisle design, which we call the Leaf
because of its veiny structure and organic appearance.
41
Case 1
P&D w w
h
R L
CR CL
R L
Case 2
P&D w w
h
R L
CR CL
R L
Case 3
P&D w w
h
R
CR CL
L
R L Case 4
P&D w w
h
R
CR CL
L
R L
Figure 4.14: Cases in the three cross aisle model.
4.5 Three Cross Aisle Design
Development of the three cross aisle model is as before. There are three inserted
cross aisles, in addition to the bottom cross aisle (see Figure 4.13). Due to the
assumption of symmetry, C = 90?, and this vertical cross aisle divides the warehouse
into two equal parts. Therefore, we can focus on nding the optimal angles of aisles
on the right half because the left half is a mirror image.
De ne A, B, C and D as regions on the right side of the warehouse (see Fig-
ure 4.13). Travel in regions A and B is the same as travel to the same regions in two
cross aisle designs (see Figure 4.11). Therefore, travel distance functions in regions
A (TA) and B (TB) are de ned by equations (4.3) and (4.4) given in Section 4.4.
Travel in region D is also the same as travel in region B in a one cross aisle design
(see Figure 4.5), and the travel function in this region (TD) is de ned by equation
(4.2) given in Section 4.3. Therefore, we need only develop a travel distance function
(TC) to a random point (x, y) in region C. The rst part is the travel distance along
42
the cross aisle; the second part is along the appropriate picking aisle.
TC(x;y) =
p
x2 +y2
cos
arctan yx R
sin
arctan yx R
cot( R R)
+
p
x2 +y2
sin arctan yx R
sin( R R)
!
:
There are four cases determined by possible orientations of the cross and picking
aisles on the right side of the warehouse (see Figure 4.14). According to Proposi-
tion 4.4, these cases are
1. 0?< R R, 0?< R R and R CR R,
2. 0?< R R, 0?< R R and R CR < 90?,
3. R R < 90?, 0?< R R and R CR < 90?, and
4. R R < 90?, R < R R and R CR < 90?,
where R is the angle of the diagonal on the right side of the warehouse. E[WR1],
E[WR2], E[WR3] and E[WR4] are the associated expected travel distances. Closed
form expressions are in Appendix A.3.
E[WR1] = 1wh
Z w
0
Z xtan R
0
TA(x;y) dydx+
Z w
0
Z xtan R
xtan R
TB(x;y) dydx
+ 1wh
Z w
0
Z xtan CR
xtan R
TC(x;y) dydx
+ 1wh
Z w
0
Z h
xtan CR
TD(x;y) dydx
; (4.8)
43
E[WR2] = 1wh
Z w
0
Z xtan R
0
TA(x;y) dydx+
Z w
0
Z xtan R
xtan R
TB(x;y) dydx
+ 1wh
Z
h=tan CR
0
Z xtan CR
xtan R
TC(x;y) dydx
!
+ 1wh
Z w
h=tan CR
Z h
xtan R
TC(x;y) dydx
+ 1wh
Z
h=tan CR
0
Z h
xtan CR
TD(x;y) dydx
!
; (4.9)
E[WR3] = 1wh
Z w
0
Z xtan R
0
TA(x;y) dydx+
Z w
h=tan R
Z h
xtan R
TB(x;y) dydx
+ 1wh
Z
h=tan R
0
Z xtan R
xtan R
TB(x;y) dydx
!
+ 1wh
Z
h
0
Z y=tan R
y=tan CR
TC(x;y) dxdy
!
+ 1wh
Z
h
0
Z y=tan CR
0
TD(x;y) dxdy
!
;and (4.10)
E[WR4] = 1wh
Z
h
0
Z w
y=tan R
TA(x;y) dxdy +
Z h
0
Z y=tan R
y=tan R
TB(x;y) dxdy
!
+ 1wh
Z
h
0
Z y=tan R
y=tan CR
TC(x;y) dxdy
!
+ 1wh
Z
h
0
Z y=tan CR
0
TD(x;y) dxdy
!
: (4.11)
Proposition 4.5. An optimal three cross aisle, square half-warehouse has R = =4
and CR = 90? R.
Proof. Follows from a simple argument of symmetry.
The proposition allows us to focus only on nding the optimal R. We derive an
expected travel distance function only on the right side of the warehouse according
to cases 2 and 3, because the optimal design occurs in these cases for square half-
warehouses. E[AB] is the expected travel distance in regions A and B in these cases,
when R = =4.
44
E[AB] = 1wh
Z
w
0
Z xtan R
0
TA(x;y) dydx+
Z w
0
Z xtan =4
xtan R
TB(x;y) dydx
!
= w
3
6
tan R + sec R
1 +p2 sec R 2 sin
R + 4
tan R
:
The rst order condition is
d E[AB]
d R =
w3 2 +p2 +p2 sin R
6p2 cos2 R = 0:
The solution produces only one root: R = arcsin(p2 1). The second order con-
ditions show that E[AB] is convex in the range 0 R < 90? (see Proposition 4.1).
d2E[AB]
d 2R =
w3
12 cos3 R
3 + cos(2 R) + 4( 1 +p2) sin R
: (4.12)
That d2E[AB]d 2
R
is strictly positive can be seen by setting cos(2 R) and sin R to
their maximum values of 1, and noting that cos3 R is positive. Therefore, E[AB]
is convex and the solution is a global minimum. In an optimal three cross aisle,
square half-warehouse design: R = =4, C = =2, R = arcsin(p2 1) and
CR = =2 arcsin(p2 1). We call this design the \Butter y" (Figure 4.15).
4.6 Comparison of Continuous Warehouse Designs
Gue and Meller (2009) give a lower bound on expected travel distance for a
continuous warehouse with a single P&D point. We call this model \Travel by
Flight." In terms of our model parameters, the lower bound for Travel-by-Flight is
E[TF ] = 16wh
2hwph2 +w2 +w3 ln
h+ph2 +w2
w
!
+h3 ln
w +ph2 +w2
h
!!
:
45
P&D w w
h
R = 45? L = 135? C = 90?
R 24:47? L 155:53?
CR 65:53? CL 114:47?
Figure 4.15: Representation of the Butter y design.
Christo des and Eilon (1969) and Stone (1991) develop similar expressions for Travel
by Flight in square and rectangular areas, respectively.
If travel is rectilinear, as in a traditional warehouse, the expected travel distance
for a warehouse with a single, centrally located P&D point de nes a reasonable upper
bound. In terms of our model parameters, expected value for rectilinear travel TR
is
E[TR] = (w +h)2 :
Table 4.1 shows the relative cost performance of several designs, where the cost
of a traditional design serves as the base 100%. The Chevron and Fishbone designs
o er 19.53% less expected travel distance than an equivalent traditional warehouse.
The Leaf design o ers a 21.72% savings and is only 1.76% worse than the Travel-
by-Flight design. The Butter y design reduces expected travel distance by 22.52%
and is 0.96% worse than Travel-by-Flight. All of these results are for the continuous
space representation of a warehouse.
Observation 1. In an optimal two cross aisle design for a square half-warehouse,
R + R = 90?.
46
Table 4.1: The relative expected travel distance comparison among equivalent ware-
house designs based on the continuous model.
Warehouse Performance %
Traditional 100
Chevron 80.47
Fishbone 80.47
Leaf 78.28
Butter y 77.48
Travel-by-Flight 76.52
P&D w w
h
A
B
CD
Figure 4.16: Equally distributed imperfections in designs.
The observation follows directly from the optimal values in Theorem 4.1. Un-
fortunately, we are unable to interpret it in terms of warehousing. However, this
observation is likely related to,
Observation 2. In the optimal two cross aisle design for a square half-warehouse,
the expected travel distance in the region below the median picking aisle (E[A] in
Figure 4.16) is the same as expected travel distance in the central region (E[D]).
The expected travel distance in regions above and below the diagonal in the half
space are also the same (E[A] +E[B] = E[C] +E[D]).
See Appendix A.2 for a proof. The observation suggests that optimal solu-
tions exhibit a sort of spatial uniformity of costs, similar in spirit to the \optimal
distribution of imperfection" in Bejan (1996).
47
P&D w w
h
0
1 2
1
2
3
P&D w w
h
1 3
2
1 4
2 3
Figure 4.17: Equal travel distance in dual designs shown via parallelogram.
Observation 3. For any warehouse with an even number k of angled cross aisles
and one bottom cross aisle, there is a \dual" warehouse with k+1 angled cross aisles
having the same expected travel distance, such that the angles of the picking (cross)
aisles in one can be determined directly from the cross (picking) aisles in the other.
The observation can be shown by noting equivalent parallelograms in dual de-
signs (see Figure 4.17) and by an inductive argument. Note also that the Chevron
and Fishbone are dual designs, and that both o er the same savings over traditional
designs. Costs in dual warehouses are not the same in practice, where aisles occupy
space and pallet positions are discrete. We explain why in the next section.
4.7 A Continuum of Designs
With a continuous model of warehouse space, we have shown that two cross
aisles is better than one, and three is better than two. Why not four, ve, or ten?
The answer, of course, is that the continuous model fails to account for the space
lost to aisles. The greater the number of cross aisles, the more space is lost to
those aisles, and the farther pallet locations are pushed away from the P&D point.
Moreover, because cross aisles meet at the P&D point, increasing their number
eliminates more and more of the best locations, which are those nearest the P&D
point. We have, then, a tradeo : increasing the number of properly placed cross
aisles tends to decrease expected distance to locations, but it also tends to push
48
Figure 4.18: The Chevron design.
those locations farther away. How many cross aisles is best, and for what range of
warehouse sizes?
To investigate these questions, we build a discrete model of aisles and pallet
locations that better represents designs that could be implemented in practice (see
Figures 4.18{4.20). In the discrete model, we assume pallet locations are square,
that picking and cross aisles are the width of three pallets (about 12 feet), and that
there is a bottom cross aisle. We measure travel distance from the P&D point to
the location in a picking aisle from which the pallet can be accessed. The expected
travel distance for a design is the total distance to all pallet locations divided by the
number of locations in that design.
Is it possible to transfer the results of the continuous model directly into dis-
crete space? That is, is a discrete design with angles of cross aisles and picking
aisles taken from the optimal continuous solution also optimal in discrete space? To
assess the robustness of optimal solutions from the continuous space model, we per-
turbed slightly these optimal angles in the discrete design to look for lower expected
distance. In some cases, we were able to improve very slightly on the continuous
result, but the improvements were always less than 0.01%. Part of the discrepancy
is likely due to our method of calculating expected cost in a discrete design, in which
49
Figure 4.19: The Leaf design.
Figure 4.20: The Butter y design.
50
a very slight change of angle could allow a single distant pallet location to t into
a crevice that previously could not quite contain it (a careful look at Figure 4.20
should make this clear). In any real implementation, of course, there would be many
reasons why neither of our models would be exact: aisle widths may vary because of
vehicle types, pallet locations may not be exactly square, there is clearance between
racks, and so on. Nevertheless, we contend that direct transfer of results from the
continuous model to the discrete model is appropriate, and for our purposes the
resulting discrete designs are \optimal."
Figure 4.21 shows the expected distances for designs having approximately a
2:1 width to depth ratio. (We say \approximately," because the discrete nature
of the designs precludes maintaining an exact ratio.) All designs o er more than
approximately 13% improvement in expected travel distance over equivalent tradi-
tional warehouses of di erent sizes (data for the number of pallet locations in these
warehouses are in Appendix A.4.) Also, as the size of the warehouse increases, the
advantage of inserting angled cross aisles increases, and the percentage of additional
space required for angled aisles decreases.
Among all non-traditional designs, Chevron is the best design for warehouses
with 27 or fewer aisles. As the size of the Chevron increases from 19 aisle-widths to
27 aisle-widths, savings increase from approximately 16.1% to 17.1% and additional
space requirements decrease from 11.2% to 7.3%. Chevron always has less expected
travel distance than the equivalent traditional design, even if the warehouse is small
(see Figure 4.22). Although the Chevron and the Fishbone o er the same bene t
in continuous space, the Chevron has slightly lower expected travel distance in a
discrete design. Nevertheless, the concept of duality does explain why, even in a real
layout, the costs of a Chevron and Fishbone are so close.
For warehouses with more than 27 aisles, the Leaf o ers more savings than the
Chevron, but requires slightly more space due to having two inserted cross aisles.
As the size of the warehouse increases, the additional savings of the Leaf increase
51
# aisles
Percent Improvement in
Expected Travel Distance
Leaf
Butterfly
Chevron
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ?
?
?
?
?
?
?
? ? ? ? ?
? ? ?
?
20 30 40 50 60 70
14
15
16
17
18
19
20
# aisles
Percent Increase in Area
Chevron
Butterfly
Leaf
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ?
? ? ? ?
? ? ?
? ?
20 30 40 50 60 70
5
10
15
20
25
Figure 4.21: Comparison of several approximately square half-warehouses with an
equivalent traditional warehouse. (Data for the plots are in Appendix A.4.)
Figure 4.22: Chevron versus Traditional in an equivalent small size warehouse:
Chevron has lower expected distance, but requires more space.
52
and the additional space requirement decreases compared to the equivalent Chevron
and traditional designs. Even for a huge warehouse with 63 aisles, the Leaf provides
more bene t than the Butter y and requires less space. For a large warehouse with
51 aisles, the Leaf has 19.3% improvement over an equivalent traditional design and
uses 6% more space.
Although the Butter y o ers more improvement than the Leaf in the continuous
space model, in a discrete design it has less savings for most warehouse sizes because
of the wasted space due to more cross aisles. However, the Butter y o ers slightly
more improvement than the Leaf for warehouses larger than 65 aisles.
4.8 Implications for Practice
We have shown that there are new ways to arrange aisles in a unit-load ware-
house such that expected distance to store and retrieve pallets is signi cantly lower.
The goal, of course, is to reduce the labor costs for such operations, but as Figure 4.21
illustrates, reducing expected travel distances comes at a cost of lower storage den-
sity, or equivalently, of larger facilities. This tradeo suggests that rms facing the
task of designing unit-load storage areas, whether for exclusive pallet-handling op-
erations or for bulk reserve operations in support of order picking, should weigh the
xed cost of a larger space against the operational savings of lower travel distances.
The details of such problems will vary with the operational situation, of course.
Our models are based on several important assumptions. First, we have as-
sumed uniform picking density, which is roughly equivalent to the randomized stor-
age policy (Schwarz et al., 1978) used in many bulk storage areas. Pohl et al. (2010)
showed that the Fishbone design, which is similar to the designs we describe here,
o ers signi cant bene t even under turnover-based storage, so we expect similar
results would be found for the Chevron, Leaf, and Butter y. A second important
assumption is that travel begins and ends at a single pickup and deposit point,
which is more restrictive. In practice, this assumption would be appropriate when,
53
for example, picks must pass through a single stretch-wrap machine, or when re-
ceived pallets must pass through a processing station (we describe examples below).
Our nal important assumption is that all travel is for single-command cycles. This
is true for many operations in practice, but even operations capable of executing
dual-commands must execute single commands when there are no stows (picks) in
the queue. Furthermore, as Pohl et al. (2009b) show, designs that reduce single-
command travel also perform well for dual commands because two of the three legs
in a dual command cycle are essentially single command distances.
Our computational results show that Chevron is the best design for warehouses
with fewer than 27 aisles, which, in our experience, is the majority of unit-load
warehouses in practice. The Leaf o ers slightly lower expected travel distances for
larger warehouses, but the penalty cost in terms of space is high. For example, the
Leaf is 0.15% better than Chevron for a 31 aisle-width warehouse, but requires 4%
more space. It is hard to imagine such a small operational bene t overcoming the
xed cost of such additional space. Even for warehouses equivalent to a traditional
design with 57 aisles (an unrealistic size, in our experience), the Chevron is within
one percent of the bene t o ered by the Leaf. The Butter y o ers no improvement
over the Leaf for warehouses smaller than 65 aisles, and is simply too space-ine cient
to be a viable candidate design. For these reasons, we believe the Chevron design is
the best choice for any realistic scenario that might be encountered in industry.
But will distributors actually use these ideas? There is now evidence that, un-
der the right conditions, they will. At the time of writing, the authors knew of ve
implementations of non-traditional aisles, each motivated by the results in Gue and
Meller (2009). Generac Power Systems in 2007 implemented a modi ed Fishbone
design at its nished goods warehouse in Whitewater, Wisconsin (Figure 4.23). The
lower left and right triangles in the design contain oor stacked pallets and pallet
ow rack, whereas the central region is single-deep pallet rack. Pallets are taken
by counterbalanced fork truck from receiving doors to a central P&D point, where
54
Figure 4.23: An implementation of non-traditional aisles at Generac Power Systems.
they are transferred to a second, more expensive vehicle capable of vertically lifting
them to their storage locations. A second implementation, in Florida, uses almost
exclusively oor stacked pallets (goods are extremely heavy, making pallet rack in-
feasible due to oor loading constraints). All picks are taken to a single stretch-wrap
machine, thus satisfying the single P&D requirement. Unfortunately, for di erent
reasons, neither of these warehouses could establish a before-and-after comparison
of performance, but both have reported satisfaction with the designs.
Of course, there were unanticipated details in the implementations, some good,
some not as good. For example, even though forklift drivers rarely need to make
a 135? turn when coming out of a picking aisle, still they must look both ways
before entering the cross aisle, and that sometimes requires looking back 135?. Semi-
hemispherical mirrors were installed to improve safety at these intersections. On the
other hand, workers at one warehouse reported that they liked the design because
they were \able to take [the 45?] turns at full throttle," a bene t that had not
occurred to us.
Non-traditional aisle designs are not right for every operation. The bene t
for small warehouses, or for those that do not consume much labor, likely would
not overcome the xed cost of needing a larger storage space. Such warehouses
should use conventional designs, for which storage density is highest. Labor-intensive
operations, however, should consider the long-term bene ts of the Chevron design.
55
Chapter 5
Non-Traditional Unit-Load Warehouse Designs with Multiple Pickup-and-Deposit
Points
5.1 Introduction
In global logistics and transportation systems, warehousing plays a critical role
in assuring high levels of customer service and overall supply chain performance.
Among warehouses in a supply chain network, unit-load receiving and retrieving,
where one item or pallet is carried at a time, often makes up a considerable portion
of warehouse operations, especially in 3rd party distribution centers. According
to Rogers (2009), during times of economic downturn, in addition to increasing
customer and supplier satisfaction, many warehouses are also looking internally for
ways to cut costs. Among operations costs in a warehouse, labor cost is signi cant
because workers in distribution centers spend their time traveling to store or retrieve
items (sometimes traveling empty). Also, because 3rd party distribution centers
pay their forklift drivers for work-hours and bill their customers for two movements
(receiving and retrieving) for each pallet, reducing travel time and increasing the
number of handles per hour are two of the cornerstones of running a warehouse
e ciently and pro tably (Bartholdi and Hackman, 2008).
(a) Trad-A (b) Trad-B (c) Trad-C
Figure 5.1: Traditional rectangular warehouses.
56
In traditional warehouses, forklift drivers travel along the aisles, where cross
aisles are arranged at right angles to parallel picking aisles, to reach a storage location
(see Figure 5.1). Because of the rectilinear travel paths in traditional unit-load
warehouses, inserting an orthogonal cross aisle o ers no advantage in travel distance
to and from a pickup and deposit point when it is placed at the bottom or top
of the warehouse (Roodbergen and de Koster, 2001). However, if there is more
than one P&D location and at least one of them is placed on the right or left side
of the warehouse, a cross aisle is needed to facilitate travel from P&D points in
traditional warehouses (see Figure 5.1b and 5.1c). Additionally, it is not uncommon
that warehouses in industry have multiple entry points to access the storage area.
For example, while one side of the warehouse has receiving docks, the other side
might have shipping docks. Or, receiving and shipping docks might be on the same
side of the warehouse.
Gue et al. (2010) took the idea of non-traditional warehouse designs and investi-
gated unit-load warehouses for multiple P&D points on one side. They inserted two
angled cross aisles that form \modi ed Flying-V" and \Inverted-V" designs, into the
traditional warehouses (Figure 5.2). They showed that the modi ed Flying-V design
can reduce travel by 3-6%, and the Inverted-V o ers less than 1% in savings com-
pared to a traditional warehouse. Additionally, they suggested that if the inserted
P&D points are concentrated toward the center of the bottom of the warehouse, the
bene t of the Flying-V would be increased.
Although Gue et al. (2010) considered multiple P&D points for non-traditional
aisles, the resulting designs still assume that picking aisles should be vertical and
parallel to each other. In Chapter 4, by inserting a number of cross aisles, we
showed that the expected travel distance between a centrally located pickup and
deposit (P&D) point and a storage location can be reduced by 15% to 20%. We
also showed that allowing picking aisles and cross aisles to take any angle provides
additional reduction in expected travel distances in warehouses. In this chapter we
57
(a) The Modi ed Flying-V (b) The Inverted-V
Figure 5.2: The Modi ed Flying-V and the Inverted-V designs for multiple P&D
points. From Gue et al. (2010).
take these ideas further and propose new aisle designs close to the optimal for unit-
load storage spaces that have multiple access locations. Additionally, whereas Gue
et al. (2010) focused on multiple P&D points on only one side of the warehouse,
we consider multiple P&D points both on one side and on di erent sides of the
warehouse to cover more practical cases seen in industry.
In the next section, we review relevant literature in non-traditional warehouse
designs. In Section 5.3, we discuss underlying assumptions of a general warehouse
network model we present in Section 5.4. Then, in Section 5.5, we discuss our
implementation of Particle Swarm Optimization. In Section 5.6, we introduce new
warehouse designs to some speci c cases di erentiated by the locations of P&D
points. In the nal section, we summarize our ndings.
5.2 Previous Research
The rst discussions of non-orthogonal aisle designs came from Moder and
Thornton (1965), Francis (1967a,b), Berry (1968) and White (1972). White (1972)
investigated \Euclidean e ciencies" by inserting radial aisles into a continuous ware-
house space. Then, Gue and Meller (2009) proposed two non-traditional designs,
the Flying-V and the Fishbone. Pohl et al. (2009a) showed that for dual command
operations the optimal placement of a \middle" orthogonal cross aisle in traditional
58
designs is slightly beyond the middle. Pohl et al. (2009b) studied the Fishbone
design for dual-command operations (also called task interleaving). They showed
that the Fishbone design o ers a reduction in expected travel distance compared to
several common traditional designs. They also o ered a modi ed Fishbone design
for dual-command operations. Pohl et al. (2010) analyzed three traditional designs,
as well as Fishbone and Flying-V designs, under turnover-based storage policies and
both single- and dual-command operations.
Some research has been done on multiple depots and their di erent con gura-
tions in a warehouse. Randhawa et al. (1991) evaluated an unit-load AS/RS for two
di erent con gurations of dual-dock layouts on performance such as throughput and
waiting time. Yano et al. (1998) discussed decentralized receiving in a manufactur-
ing assembly facility. They developed an optimization-based procedure to determine
some variables including multiple access points to the building so as to minimize the
cost. Eisenstein (2008) considered dual depots in a discrete order picking system
to minimize required walking distance. In addition to the warehousing literature,
Garces-Perez et al. (1996) examined facility layout problems for pre-speci ed I/O
locations for departments by using Dijkstra?s shortest path algorithm with genetic
programming. Also, Kim and Kim (2000) focused on the facility layout problem
with predetermined shape and input and output points. They placed one input and
one output point on di erent sides of a facility represented by four di erent shapes.
5.3 Assumptions
We assume a randomized storage policy, which is common in unit-load ware-
houses, for the same reasons described in Chapter 4. With this policy, pallets are
stored in the closest available locations, as opposed to reserved locations in a dedi-
cated storage policy. Thus, pallets may be stored at any location in the warehouse
that increases the space utilization. In this policy, the probability of picking or
59
Figure 5.3: The intersecting and non-intersecting cross aisles in a warehouse.
storing any pallet in the warehouse is the same. For easier representation, our stor-
age locations have a square-shaped footprint and one pallet length is the adopted
measure of distance.
From the perspective of warehouse design, we assume that picking aisles, which
are within regions determined by cross aisles, are parallel to each other. Picking
aisles and cross aisles can take on any angle. Contrary to our model in Chapter 4
and the model of White (1972), we take into account aisle width and its e ect on
travel distances in our new model. Each picking and cross aisle is assumed to have
a width of 3 pallet locations. We assume standard, single-deep pallet rack, although
our models could easily be modi ed for double-deep rack or deeper lane storage. The
model allows for no more than two angled cross aisles. Cross aisles are not allowed to
intersect, but they can originate from the same point. This limitation is serious, but
is necessary for computations reasons. The number of cases to consider for the case
of intersecting aisles is much greater than the number of cases we describe below.
To allow for P&D points along the periphery of the warehouse, we assume that
there are no storage racks along the sides of the warehouse. We call these available
spaces on the periphery of the warehouse \side cross aisles" so that they can facilitate
travel between locations. In a warehouse, P&D points could be places which have
palletizing or shrink-wrap machines, or pick lists for workers. All travel is from the
P&D points located on any side of the warehouse to any location in the warehouse
(i.e. there are no zones). We assume only one pallet is carried at a time in a single
60
Warehouse Network
Model
OptimizerEvaluator
Graph-Based Network
Representation
Warehouse
Representation
Cross Aisles
P&D Points
Warehouse Size
Picking Aisles
Travel Edges
Travel Nodes
Travel Distance
Calculation
Shortest Path
Algorithm
Figure 5.4: Description of the warehouse design tool
command cycle, comprised of travel to a random storage location and back to the
P&D point.
Because of the single-command cycle, the same distances are traveled into the
storage space and out of it, which enables us to consider only the half of the actual
distance traveled. Hence, travel distance in our model is the shortest distance from
the P&D point to the location on the picking aisle that accesses the center of a
storage location. Picking aisles can also be traversed to reach a location if the travel
path through that aisle has the shortest distance. The expected travel distance
to pick (store) an item is the sum of the one-way shortest distances to all storage
locations from all P&D points divided by the total number of storage locations and
the number of P&D points in that design. Therefore, we assume that each P&D
point has the same probability of being visited or used.
5.4 The Warehouse Network Model
Our warehouse network model consists of four main modules (Figure 5.4). These
modules are designed as the fundamental classes of our conceptual software.
61
Warehouse representation: In this module, the warehouse as an entity is de ned
the width (W) and length (H) of the space, the width of the cross and picking aisles
(a), the location of P&D points, the number of cross aisles, and the angles of cross
and picking aisles in a suitable coordinate system (see Figure 5.6 for an example
warehouse). P&D points are placed along the side cross aisles that provide direct
travel to the storage area based on the angles of aisles. Based on the aisle width,
cross aisles are de ned by a straight line going through the storage space and whose
start and end points are de ned on di erent sides of warehouse. Single-deep racks
are constructed in a space divided by cross aisles based on the angle and width of
related picking aisles. Picking aisles are automatically arranged in accordance with
valid positions of the pallet racks. Hence, in each pallet rack, storage locations and
their access points on aisles are determined by the described procedure in Figure 5.5.
A sample design is given in Figure 5.6.
Graph-based network representation: We use the warehouse representation to
construct a graph representing the whole warehouse as a network (Figure 5.6). The
nodes of the network include all of the potential P&D points, all intersections of the
aisles, and an access node for each of the storage locations. P&D points are placed on
the center lines of the side cross aisles. The network is constructed with non-negative
edge lengths that represent the distances between the connected nodes. An access
node for a storage location is placed on the center line of the appropriate picking
aisle and to provide access to the center of the corresponding storage locations. The
edge length for two connected neighbor access nodes, representing storage locations,
in the same rack is one pallet (unit) length. Two access nodes on opposite racks,
representing opposite storage locations, are connected and the edge length is zero,
because they are actually served from the same coordinate.
Evaluator: In this module, we calculate the distance between a P&D point
and a node by computing the shortest paths with Dijkstra?s one-to-many algorithm.
Dijkstra?s algorithm searches the graph to nd the path from the source node (P&D)
62
Warehouse
Representation
Define warehouse size and the
aisle width. Locate P&D points.
Specify the number of cross aisles
and their start and end points.
Specify angles of picking
aisles in each region.
Determine regions.
Determine reference points to
construct the first pallet location
in each region.
Construct the first pallet location
in the first rack in each region.
Construct the first pallet locations
in other possible racks in parallel
to the first pallet location of the
preceeding rack.
Construct other pallet locations
in each rack according to its first
pallet location.
Figure 5.5: The procedure to represent a discrete space warehouse design for given
set of parameters.
W
a
H
Figure 5.6: Network representation of a small, example warehouse. (Each storage
location is represented by an access node in a real network.)
63
to the target node (storage location) with the lowest cost (distance). The worst case
running time for the algorithm on a graph with n nodes and m edges is O(n2)
(Schrijver, 2005).
The expected travel distance to pick an item in a warehouse with k P&D points,
n total storage locations and the shortest distance between ith P&D point and jth
storage location (dij) is
E[C] =
kX
i=1
nX
j=1
dij pi
n =
1
kn
kX
i=1
nX
j=1
dij;
where pi = 1=k is the probability of choosing P&D point, because we assume each
P&D has the same probability to be utilized.
Proposition 5.1. E[C] is the same as two-way expected travel distance if the re-
turning P&D point is selected randomly with equal probability.
Proof. Let I be a set of k P&D points. pi is the probability of choosing the ith P&D
point as a source node. p(rji) is the probability of choosing the returning P&D point
r when the source ith P&D point is known. The expected travel distance to pick an
item in this system is
E[RC] =
kX
i=1
kX
r=1
nX
j=1
1
n
d
ij +drj
2
pip(rji);
where pi = 1=k and p(rji) = 1=k, because returning P&D point might be the same
as the source node. Hence, we can write
E[RC] = 12nkk
nX
j=1
kX
i=1
kX
r=1
dij +drj
!
= 12nk2
nX
j=1
kX
i=1
kdij +
kX
r=1
drj
!!
= 12nk2
nX
j=1
kX
i=1
kdij +
kX
i=1
dij
!!
;
64
where
kP
i=1
dij =
kP
r=1
drj due to the same probability of visiting P&D points. Finally,
E[RC] = 12nk2
nX
j=1
k
kX
i=1
dij +
kX
i=1
kX
i=1
dij
!
= 12nk2
nX
j=1
k
kX
i=1
dij +k
kX
i=1
dij
!
= 2k2nk2
kX
i=1
nX
j=1
dij = 1kn
kX
i=1
nX
j=1
dij;
and is equal to E[C].
Therefore, in our model we only calculate one-way expected travel distance to
pick an item from each P&D point.
Optimizer: We use Particle Swarm Optimization algorithm to minimize our
objective function to nd optimal designs. We discuss the details in the next section.
5.5 Optimization Methodology: Particle Swarm Optimization (PSO)
Because start and end points of cross aisles can be on any side of the warehouse,
there are 12 two cross aisle cases without considering where the P&D points are
located (see in Appendix B.1). Considering possible angles of picking aisles in each
region increases total cases to approximately 192. Even though each case can be
solved, when di erent start and end points of cross aisles and di erent locations of
P&D points are considered, the problem becomes intractable. Additionally, simply
evaluating the cost of a given design requires solving multiple one-to-many shortest
path problems from multiple P&D points, we can not derive a closed form distance
expressions as an objective function need to be minimized. Therefore, we choose a
meta-heuristic solution procedure to search for the optimal values of variables that
65
minimizes the expected travel distance. Speci cally, we use an implementation of
Particle Swarm Optimization (PSO).
PSO, which was rst introduced to optimize continuous nonlinear functions by
Kennedy and Eberhard (1995), is one of the latest evolutionary algorithms inspired
by nature. Its development was based on observations of social interaction and
communication involved in bird ocking and sh schooling. In PSO, each member is
called a particle and each particle searches the multi-dimensional function space with
a speci c velocity. Two cognitive aspects of this initial metaphor, individual learning
and learning from a social group, refer to local and global search, respectively (Banks
et al., 2008). By individual learning, each particle can memorize its best previous
position, called personal best, and move towards it in its restricted neighborhood.
Then, the particles share all the information about their personal best points that
they have received so far. Hence, to accomplish global search, each particle also
moves towards the best particle, called global best, that has the best point among
all particles in the whole swarm. By using personal and global bests, each particle
adjusts direction and the magnitude of its velocity for movement in the space. Hence,
the whole population of particles moves toward the global best as a ock of birds or
school of sh. As with other meta-heuristics, PSO is also designed to nd a unique,
possibly optimum solution.
Advantages of a basic PSO algorithm include its simple structure, ease of imple-
mentation, speed in solving nonlinear, non-di erentiable multi-model problems, and
robustness (Tasgetiren et al., 2007). Additionally, its ability to handle continuous
variables is another advantage for our problem.
5.5.1 Formulation of the problem
We follow three steps to formulate our problem and to search the solution space
quickly. The rst step is \encoding," which in our case is a simple vector of real
numbers representing a warehouse. It can be easily translated back into a warehouse
66
design. Such an encoding allows rapid search of the solution space. The elements of
this vector are:
? A linear cross aisle is represented with its start (S) and end (E) points, which
de ne the angle, in a given suitable coordinate system. Hence, a set of cross
aisles can be represented as a list of such pairs.
? Picking aisles in any resulting region can be represented simply by their angle
0 in radians.
To simplify the encoding, start and end points of a cross aisle are represented by
real numbers in a single dimensional coordinate system. The origin is at the upper-
left corner and is de ned as 0 and 4 in order to make a closed loop for the perimeter
a rectangular warehouse. Lower-left, lower-right and upper-right corners are de ned
as 1, 2 and 3, respectively (see also in Figure 5.7). Hence, if the appropriate point of
the cross aisle, S or E, is located on the left side2[0;1), on the bottom side2[1;2),
on the right 2[2;3) and on the top 2[3;4]. When evaluating the cost of a design,
we convert the encoding of the cross aisle to an x;y point in the coordinate system.
Additionally, P&D points are pre-located at their given positions in the coordinate
system, which are along the perimeter of the warehouse rectangle.
To narrow the search space, some inappropriate cases, such as having the start
and end points of a cross aisle on the same side of the warehouse, and duplication
(switching the start and end) are avoided. Hence, for the one cross aisle model,
there are mainly 6 cases representing the possible orientations of the cross aisle
(Figure 5.7). Because cases 3, 4 and 6 are symmetric cases of case 1, we only
consider cases 1, 2 and 5 as subproblems. In these subproblems, S 2 [0;1) and
E2(1;2], S2[0;1) and E2[2;3], S2[1;2] and E2[3;4], respectively.
For the two cross aisle model, there are 34 cases (see in Appendix B.1). Twelve
of them are de ned as main cases and others are symmetric. We divide these 12
main cases into 3 subproblems as described in Figure 5.8 to narrow the search space
67
S
E
E
E
0
1 2
34
1
3
2
S
E
E
45 S
E
O
6
Figure 5.7: Possible arrangements of one cross aisle. (Numbers on the cross aisles
represent cases in the one cross aisle model.)
0
1 2
34
S2
S1
E1, E2
E2, E1
E2
E1
Subproblem 1
S1 S2
E1, E2
E2
E1
E1
E2
Subproblem 2
S1 S2
E1
E2
Subproblem 3
Figure 5.8: Possible directions of cross aisles
and control the movement of the cross aisles. In the two cross aisle model, S1 and
E1 are the start and end points of the rst cross aisle, as well as S2 and E2 of the
second cross aisle. Because of the assumption of non-intersecting cross aisles, we
de ne upper and lower limits for start and end points of cross aisles (see Table 5.1).
Additionally, because our model assumes at most two cross aisles and we assume
non-intersecting cross aisles, there are at most three regions (Figure 5.9). Angles
R, L and C (if present) represent the angles of picking aisles in the right, left
and central regions. For an example, the encoding for a two cross aisle model is
f L; C; R;S1;E1;S2;E2g.
S1 S2 E1 E2
Subproblem 1 (0,1) (0, S1) (1, E2) (1,4)
Subproblem 2 (3,4) (3, S1) (0, E2) (0,3)
Subproblem 3 (0,1) (2, 3) (1, 2) (3,4)
Table 5.1: Upper and lower limits of start and end points of cross aisles in the two
cross aisle model.
68
R
L
(a) One cross aisle design
R
L
C
(b) Two cross aisle design
Figure 5.9: Possible region de nitions and angles of aisles in these region.
The second step is \evaluation," in which we evaluate the performance of a
design represented by a speci c encoding (a vector of design parameters) on expected
travel distance of a pick or stow. For this, we use the graph-based network model
of the warehouse discussed in the previous section, and our objective function is to
minimize the expected travel distance E[C].
The third step is to \search" encodings to nd the lowest possible E[C] for each
de ned subproblem in the one and two cross aisle models. For this task, we use the
PSO algorithm. Finally, we select the aisle design that has the lowest E[C] among
solutions of the subproblems with respect to the one and two cross aisle models.
5.5.2 PSO Algorithm
In the simple PSO algorithm, each particle represents a solution and moves
toward its previous best position and the global best position found in the popula-
tion so far. After initializing the parameters and generating the initial population
randomly, each particle is evaluated by the tness function. After evaluation, each
particle is updated with its position, velocity and tness value. If there is an im-
provement in its tness value, it updates its personal best. Also, the best particle in
the population is used to update the global best. Next, the velocity of the particle
is updated by using its previous velocity, personal best and the global best to move
the particle to a better place in the search space. In doing these steps repeatedly,
the algorithm searches the space until it is terminated by a stopping criterion.
69
The structure of our PSO algorithm is basically the same as the modi ed PSO
by Shi and Eberhart (1998a,b). Hence, the basic elements of our algorithm are
particles, population, particle velocity, personal best, global best, inertia weights,
coe cients and maximum velocity.
Population and Subproblem: F is the set of s subproblems, F =fI1;I2;:::;Isg.
Is is also the set of i particles at iteration t, Its =fXt1s;Xt2s;:::;Xtisg.
Particles: Xtis denotes the ith particle in the sth subproblem at iteration t. It
is represented by d dimensions: Xtis =fxtis1;xtis2;:::;xtisdg, where xtisd is the position
or the value of ith particle in the sth subproblem for the dth dimension. Dimensions
can be thought of as model variables or parameters.
Velocity of particles: Vtis is the set of d velocities of particle i in the sth subprob-
lem at iteration t, Vtis = fvtis1;vtis2;:::;vtisdg. Each dimension of each particle moves
in the search space with a distance vtisd at each iteration.
Personal best: Pis is the best previous position, which gives the best tness
value, of the ith particle in the sth subproblem, and Pis = fpis1;pis2;:::;pisdg where
pisd is the best value of dimension d of the ith particle in the sth subproblem so far.
Global best: Gs = fgs1;gs2;:::;gsdg is the best particle among all the particles
in the sth subproblem, where gsd is the best value of dimension d in Gs.
Inertia weights: Shi and Eberhart (1998a,b) introduced an inertia weight to the
algorithm. It is denoted as w and is used to balance global and local searches. It
can be a positive constant or a function of time or iteration. A larger w favors the
global search, while a smaller w favors the local.
Coe cients and maximum velocity: Coe cients c1 and c2 are the weights for
\cognitive" and \social" parts in the velocity update equation given in (5.1). To
control the explosion of velocities and provide stability, there are two other mecha-
nisms: maximum velocity Vmax and a constriction coe cient (K). For the quality of
the search, Shi and Eberhart (1998a) showed the e ect of Vmax that determines the
maximum change one particle can undergo in its positional coordinates during an
70
iteration. Clerc and Kennedy (2002) showed that the following value of K provides
rapid convergence:
K = 2j2 p 2 4 j;
= c1 +c2 > 4:
Also, r1 and r2 are uniformly distributed random numbers [0,1] that in uence
the movement toward personal or global best. Thus, the particles are updated based
on the equations,
vtisd = K wt 1vt 1isd +c1r1(pisd xt 1isd ) +c2r2(gsd xt 1isd ) (5.1)
xtisd = vtisdxt 1isd: (5.2)
Implementation Details
In accordance with the one and two cross aisle models, we have 3 subproblems
for each model (s = 3), and each subproblem is searched by 7 particles. Note
that there is no interaction or communication among particles in these di erent
subproblems. Picking aisles can take any angle between the lower bound of 0? and
the upper bound of 180?. Because each subproblem is de ned based on the cases
of cross aisles, start and end points of cross aisles in each subproblem can take any
real numbers between their lower and upper bounds. In order to keep the variables
in their boundary, we need to adjust the velocity of particles based on their bounds
in addition to Vmax. Therefore, the applied velocity of the dth dimension for the ith
particle in the sth subproblem (misd) is used to update the positions of the particle in
our algorithm. Generally, misd is calculated based on the issues shown in Figure 5.10
and 5.11, and described as the following
71
mtisd =
8
>>>
>>>
>>>>
>>>
>>>>
><
>>>
>>>
>>>>
>>>
>>>>
>:
(Ud Ld) (xtisd Ud); if Issue 1 or 5 or 6 occurs
(Ud xtisd); if Issue 2 occurs
(Ud Ld) + (Ld xtisd); if Issue 3 or 4 or 8 occurs
(xtisd Ld); if Issue 7 occurs
Vmax; otherwise if vtisd < Vmax
Vmax; otherwise if Vmax