Description
Order picking has been considered as the most critical operation in warehousing.
International Journal of Production Research,
Vol. 43, No. 17, 1 September 2005, 3561–3581
Travel distance estimation and storage zone optimization in
a 2-block class-based storage strategy warehouse
T. LE-DUC* and R.(M.)B.M. DE KOSTER
RSM Erasmus University, The Netherlands
(Received November 2004)
Order picking has been considered as the most critical operation in warehousing.
Recent trends in logistics demand faster but more reliable order picking
systems. The e?ciency of an order picking process greatly depends on the storage
policy used, i.e. where products are located within the warehouse. In this paper,
we deal with the most popular storage policy that is class-based (or ABC) storage
strategy. Particularly, we investigate the problem of determining the optimal
storage boundaries (zones) of classes in each aisle for manually operated
warehouses.
We ?rst propose a probabilistic model that enables us to estimate the
average travel distance of a picking tour. We found that the di?erences between
results obtained from simulation and the model were slight. Using the average
travel distance as the objective function, we present a mathematical formulation
for the storage zone optimization problem. However, the exact approach
can handle only small size warehouse instances. To circumvent this obstacle,
we propose a heuristic for the problem. Numerical examples we conducted
show that the heuristic performs very well in all the cases.
Keywords: Order picking; Class-based storage strategy; Travel distance
estimation; Warehouse design
1. Introduction
Order picking can be described as the process of retrieving a number of items
from their storage locations to ?ll a number of independent customer orders.
Though it seems to be a simple operation, it is a laborious process and a major
cost factor for warehouses in both production and distribution environments.
It has been estimated that the cost of order picking may contribute up to 55% of
all operating costs in a typical warehouse (see, for example, Tompkins et al. 2003).
Furthermore, new developments and trends in the global economy have had a sub-
stantial impact on the order picking process for many warehouses; the demand
pattern (customer order characteristics) has changed from few but large orders
to many but small orders, which have to be processed within very tight time win-
dows. Therefore, simultaneously reducing the cost and increasing the speed of order
picking becomes more and more critical.
*Corresponding author. Email: [email protected]
International Journal of Production Research
ISSN 0020–7543 print/ISSN 1366–588X online # 2005 Taylor & Francis Group Ltd
http://www.tandf.co.uk/journals
DOI: 10.1080/00207540500142894
The performance and e?ciency of the order picking operation depend mainly
on the following factors (see also Petersen 1999):
1. The demand pattern.
2. The con?guration (layout) of the warehouse.
3. The storage strategy: how to allocate items within the warehouse
(e.g. randomly assigning items to storage locations or assigning items
based on their order frequencies, picking volume or COI (cube-per-order)
index, etc.).
4. The batching method: how to group orders and divide orders among
order pickers.
5. The routing and sorting method: how to determine the sequence of the
items to be picked and how to consolidate the picked items.
Except for the ?rst factor, the others are usually controllable and have been
investigated by many researchers recently. The routing method is the ?rst issue
that has received considerable attention in the warehousing literature. Some promi-
nent papers on the subject are Ratli? and Rosenthal (1983), Goetschalckx and
Ratli? (1988), Hall (1993), de Koster and van der Poort (1998) and Roodbergen
and de Koster (2001a,b). Theory covering the layout design and the inter-
action between routing and layout can be found in, for example, Jarvis and
McDowell (1991) and Roodbergen (2001). Batching issues are mentioned in
Gibson and Sharp (1992), Rosenwein (1994), Pan and Liu (1995), Chew and Tang
(1999), de Koster et al. (1999), Gademan et al. (2001) and Le-Duc and de Koster
(2003). It is rather obvious that with a given demand pattern, a routing and a
batching policy, a dedicated storage strategy results in a shorter total travel distance
than the random storage strategy (where incoming products are located randomly
over the warehouse). Literature on dedicated storage policies can be found
in, for example, Hausman et al. (1976), Caron et al. (1998) and Petersen and
Schmenner (1999).
In this paper we focus on picker-to-parts, narrow-aisle, manually operated
order picking systems, one of the most common systems in practice. The employed
storage policy is the class-based storage strategy, meaning that the items are divided
into classes (for example A, B, C, etc.) based on their pick frequencies. The storage
locations are divided into zones and each class is assigned to a zone such that
the fastest moving (i.e. most frequently ordered) classes are closest to the depot.
Within a pick frequency, no further distinction on pick frequency between products
is made. This storage policy was already mentioned by Hausman et al. (1976). In our
experience, it is widely used in practice because it is convenient to implement
and maintain; it can easily handle assortment changes or changes in pick frequency.
In addition, using a class-based storage strategy often leads to a substantial reduc-
tion in order pick travel distance as compared to random storage (see Hausman et al.
1976, Rosenblatt and Eynan 1989, Eynan and Rosenblatt 1994 and Larson et al.
1997). The average travel distance of a picking tour is crucial as it is linearly
related to the travel time, which is most often used as the objective in warehouse
optimization problems. Therefore, the primary objective of the research is to pro-
vide an analytical model for estimating the average travel distance of a picking
tour for this type of warehouses. This estimate will then be used for storage
zone optimization.
3562 T. Le-Duc and R.(M.)B.M. de Koster
Two main types of warehouse operation can be distinguished: picker-
to-parts (usually manual picking) and parts-to-picker (automated). In the automated
system, a dedicated storage and retrieval machine can move vertically and horizon-
tally along the rack, retrieving and putting away unit loads. In contrast, in picker-
to-parts systems an order picker usually travels along the aisles to pick multiple
items at multiple locations in the storage racks. Extensive literature exists on
travel distance estimation in both warehouse types, for example, Bozer and
White (1984), Goetschalckx and Ratli? (1988), Eynan and Rosenblatt (1993),
Hall (1993), Sarker and Babu (1995), Caron et al. (1998), Chew and Tang (1999)
and Roodbergen (2001).
Our research is distinct from previous research on the subject. Most recently,
Roodbergen (2001) proposes formulas for estimating the average travel distance
in both single-block and multi-block conventional warehouses under the random
storage strategy (incoming products are located randomly over the warehouse)
and the traversal routing strategy. His formulations perform better than previously
existing formulas. The limitation of these formulations is that they cannot be applied
to non-random (i.e. ABC, COI-based) storage strategy warehouses. Caron et al.
(1998) discuss the COI-based storage strategy and propose travel time models for
estimating the average travel distance of a picking tour when either the traversal
(S-shape) or the return routing heuristic are used. The COI-based strategy assigns
products with a low ratio of the required storage space to the order frequency to the
locations nearest to the depot. This storage strategy di?ers from the class-based
storage strategy, because it allocates products on an individual basis, while
the ABC storage strategy assigns products to storage locations in groups. In practice,
such a COI-based strategy can only be applied to very stable assortments with limited
changes in order frequency and limited changes in the stored volume. This situation
is, however, more and more uncommon in practice. Chew and Tang (1999) consider
the travel distance estimation problem with a general storage assignment strategy.
Their research di?ers from ours in two respects. Firstly, they study a di?erent type of
layout leading to di?erent travel time estimates. Secondly, in their paper, a product
class can only be assigned to storage locations on a whole-aisle basis. It means
that products from two di?erent classes cannot be stored in the same aisle. In our
study, their type of assignment is a special case; in other words, in our study a
partial-aisle assignment is allowed.
Furthermore, besides travel distance estimation, we also consider the storage
zone optimization problem, which is the problem of determining how much space
should be used for a certain product class in each aisle such that the average travel
distance of a picking tour is minimized. A ?rst motivation to consider this problem
arises from a recent case study of Dekker et al. (2004), where, for a multi-aisle
warehouse, 30% travel distance improvement was obtained after a few iterations
of adjusting the storage zone boundaries. A second motivation stems from the
literature on warehouse design. Though there exist some articles (for example,
Hausman et al. 1976, Graves et al. 1977 and Eynan and Rosenblatt 1993, 1994)
indicating how to zone single aisle unit-pick warehouses, no hard rules can be found
in literature about how to make ABC divisions for multi-aisle and multi-pick-per-
route situations. In practice, manual picking, multi-aisle and multi-pick-per-route
warehouses are the large majority of all warehouses. Therefore, a solution to this
problem can certainly be used in many warehouse design and control situations.
3563 Distance estimation and storage zone optimization in a warehouse
Early studies by Hausman et al. (1976) and Graves et al. (1977) suggest that the
A-zone should be very small. However, their studies concern aisle-bound automated
storage and retrieval machines where the machine has to return to the depot after
every pickup. Thus the machine is moving constantly from and to the depot, favour-
ing a highly skewed placement of items. In Dekker et al. (2004), multi-aisle and
multi-pick-per-route layouts with a larger A-zone in which the order picker can
spend some time without having to return to the depot or move to the next zone
may do better.
This paper is organized as follows. In the next section, we ?rst derive an
approximation formula for the average travel distance within an aisle with the
class-based storage strategy. Then, we apply the formula to estimate the average
travel distance of a picking tour for a multi-aisle layout. In section 3 we propose
a formulation for the storage zone optimization problem and then a heuristic pro-
cedure for solving the problem. Finally, in section 4, we draw some conclusions
and discuss a potential direction for further research.
The following system and operational assumptions are used throughout the
paper:
1. The warehouse consists of multiple identical rectangular racks (see ?gure 1).
Each rack can be used to store more than one product type.
2. The order picker can reach all items in the rack regardless of the rack’s height
and the vertical travel time within the storage aisle is negligible (this is typical
for conventional shelf-storage warehouses).
3. Further on in the paper, we de?ne the aisle’s storage space as the
aisle’s length. In reality, if the picker could reach four levels without vertical
transport (for example), the available storage space would be four times the
aisle’s length.
4. Items in the same class have the same order frequency. The order frequency
of each item-class is de?ned as the number of times that an item from
that class is required in some time period (a planning period); it is known
and constant through the planning period (see also Hausman et al. 1976).
5. We consider pick-by-order situations (no order batching effects).
The following notations are commonly used in the paper (see ?gure 1), local
notations are de?ned elsewhere:
a Total number of aisles (storage-aisles or pick-aisles).
l
ij
Partial length of aisle j used for storing of class i.
L
a
w
b
w
r
w
ij
l
Pick line
P
i
c
k
a
i
s
l
e
Depot
Storage aisle
Figure 1. Warehouse layout and notations.
3564 T. Le-Duc and R.(M.)B.M. de Koster
q Number of picks (or order-lines) in a picking tour (that is the
pick-list size).
c Number of (product) classes.
L Length of an aisle.
w
a
Width of the cross-aisle.
w
b
Centre-to-centre distance between two consecutive aisles.
w
r
Width of the (storage) rack.
O
i
Order frequency of class i.
s
i
Fraction of the total storage space that we use for class i.
p
ij
Probability that an item of class i located in aisle j is ordered (we assume
that this is proportional to the pick frequency of class i).
TD
CA
Total travel distance within the cross-aisle (called ‘within-aisle’ travel
distance).
TD
WA
Total travel distance within the aisles (called ‘within-aisle’ travel
distance).
2. Average travel distance estimation
2.1 Single aisle model
We consider a single aisle (aisle j, this implies
c
i¼1
p
ij
¼ 1) with a con?guration
given in ?gure 2. Zone 1, zone 2, . . . and zone c are reserved for items of class
1, 2, . . . and c respectively. We assume that within each zone pick item locations
are uniformly distributed. By conditioning on the farthest location of the requested
items, the expected time from the starting point (see ?gure 2) to the farthest
pick location to pick up q
j
picks can be computed as follows:
D
j
ðq
j
, cÞ ¼
c
i¼1
P
ij
Eðtravel timejfarthest pick in zone iÞ ¼
c
i¼1
P
ij
d
i
: ð1Þ
Zone 1
Zone 2
Zone c
P
i
c
k
a
i
s
l
e
j
Starting point
2 j
l
Figure 2. Single storage-aisle con?guration.
3565 Distance estimation and storage zone optimization in a warehouse
From (1), we can see that in order to determine D
j
(q
j
, c) (the expected travel distance
from the starting point to the farthest pick location) we have to determine P
ij
(the probability that the farthest pick is in zone i) and d
ij
(the corresponding expected
one-way travel distance). We consider the following situations:
. the farthest pick is in zone 1,
. the farthest pick is in zone 2 and
. the farthest pick is in zone i(i ¼3, . . . , c).
2.1.1 Farthest pick is in zone 1. If the farthest pick is in the zone 1, this means that
all picks are in zone 1 and no pick is in the zones from 2 to c:
P
1j
¼ p
q
j
1j
ð2Þ
d
1j
¼ Eðtravel distancejall picks in zone 1Þ ¼
l
1j
q
j
q
j
þ 1
ð3Þ
Equation (3) is based on the well-known property that the expectation of the
maximum of q
j
continuous uniformly distributed [0, 1] variables equals q
j
/(q
j
þ1).
Recall that p
ij
ð
c
i¼1
p
ij
¼ 1Þ is the probability that an item of class i located in aisle j
is ordered.
2.1.2 Further pick is in zone 2. The farthest pick in zone 2 is equivalent to at least
one pick in zone 2 and no pick in the zones from 3 to c (or all picks in zone 1 and
zone 2 but not all picks in zone 1):
P
2j
¼ ðp
1j
þ p
2j
Þ
q
j
À ðp
1j
Þ
q
j
: ð4Þ
d
2j
¼ l
1j
þ l
2j
E
N
2
N
2
þ 1
_ _
: ð5Þ
Where N
2
is the number of picks in zone 2. It is rather di?cult to compute d
2j
based
on (5). Therefore, we estimate d
2j
as follows. First, we calculate E(N
2
), the expected
number of picks in zone 2:
E N
2
ð Þ ¼
q
j
n¼1
nPðn picks in zone 2jall picks in zones 1 and 2, and not all picks in zone 1Þ
¼
q
j
n¼1
n
Pðn picks in zone 2, all picks in zones 1 and 2, and not all picks in zone 1Þ
Pðall picks in zones 1 and 2, and not all picks in zone 1Þ
¼
q
j
n¼1
n
Pðn picks in zone 2 and ðq
j
À nÞ picks in zone 1Þ
P
2j
¼
q
j
n¼1
n
q
j
n
_ _
ððp
2j
Þ=ðp
1j
þ p
2j
ÞÞ
_ _
n
ððp
1j
Þ=ðp
1j
þ p
2j
ÞÞ
_ _
q
j
Àn
ðp
1j
þ p
2j
Þ
q
j
À p
q
j
1j
_ _
¼
ðq
j
p
2j
Þ=ðp
1j
þ p
2j
Þ
ðp
1j
þ p
2j
Þ
q
j
À p
q
j
1j
:
3566 T. Le-Duc and R.(M.)B.M. de Koster
The last step is based on the property of Binomial distribution. Then, d
2j
can be
estimated as follows:
d
2j
% l
1j
þ l
2j
EðN
2
Þ
EðN
2
Þ þ 1
¼ l
1j
þ
l
2j
ðq
j
p
2j
Þ=ðp
1j
þ p
2j
Þ
_ _
= ðp
1j
þ p
2j
Þ
q
j
À p
q
j
1j
_ _
ðq
j
p
2j
Þ=ðp
1j
þ p
2j
Þ
_ _
= ðp
1j
þ p
2j
Þ
q
j
À p
q
j
1j
_ _
þ 1
¼ l
1j
þ
ðl
2j
q
j
p
2j
=p
1j
þ p
2j
Þ
ðq
j
p
2j
Þ=ðp
1j
þ p
2j
Þ þ ðp
1j
þ p
2j
Þ
q
j
À p
q
j
1j
¼ l
1j
þ
l
2j
q
j
p
2j
q
j
p
2j
þ ðp
1j
þ p
2j
Þ ðp
1j
þ p
2j
Þ
q
j
À p
q
j
1j
_ _ ð6Þ
2.1.3 Farthest pick is in zone i(i ¼3, . . . , c). If the farthest pick is in zone
i(i ¼3, . . . , c) then we can apply the same procedure as in two previous situations,
we have:
P
ij
i!3
¼ p
1j
þ p
2j
þ Á Á Á þ p
ij
_ _
q
j
À p
1j
þ p
2j
þ Á Á Á þ p
iÀ1, j
_ _
q
j
¼
i
k¼1
p
kj
_ _
q
j
À
iÀ1
k¼1
p
kj
_ _
q
j
ð7Þ
d
ij
i!3
%
iÀ1
k¼1
l
ij
þ
l
ij
q
j
p
ij
q
j
p
ij
þ p
ij
, q
j
_ _
i
k¼1
p
kj
ð8Þ
where we call ð
k
, Þ ¼ ð
i
k¼1
k
Þ
À ð
iÀ1
k¼1
k
Þ
:
Finally, substituting (2), (3), (4), (6), (7) and (8) into (1), we obtain:
D
j
ðq
j
, cÞ % p
q
j
1j
l
1j
q
j
q
j
þ 1
þ
c
i¼2
p
kj
, q
j
_ _
iÀ1
k¼1
l
kj
þ
l
ij
q
j
p
ij
q
j
p
ij
þ p
kj
, q
j
_ _
i
k¼1
p
kj
_ _ _ _
: ð9Þ
2.1.4 Simulation test. To approximate the error of the probabilistic model we pre-
sented above, we built a simulation model in Microsoft Excel using VBA (Visual
Basic for Applications). In the test, we considered the case that there are only three
classes. The ‘three classes’ (namely A, B and C) storage strategy is the most popular
one in practice.
3567 Distance estimation and storage zone optimization in a warehouse
In the case of three classes, it is easy to verify that:
Dðg, 3Þ % p
g
A
l
A
g
g þ 1
þ p
A
þ p
B
ð Þ
g
À p
A
ð Þ
g
_ _
:
 l
a
þ
l
B
gp
B
gp
B
þ p
A
þ p
B
ð Þ ðp
A
þ p
B
Þ
g
À p
g
A
_ _
_ _
þ 1 À p
A
þ p
B
ð Þ
g
_ _
l
A
þ l
B
þ
l
C
gp
C
gp
C
þ 1 À p
A
þ p
B
ð Þ
g
_ _
, ð10Þ
where g is the number of picks. p
A
, p
B
, p
C
and l
A
, l
B
, l
C
are the order frequencies
and storage length of class A, B and C correspondingly.
We considered three di?erent class-based assignments (ABC curves), namely:
skewed, random and medium. In the skewed assignment frequently ordered items
occupy only a very small portion of the total storage space. The A-class occupies
20% of the rack, but is responsible for 80% of the items. The random assignment
means that no distinction between item classes in the terms of order frequency
and required space can be made; they are randomly located within the warehouse.
Finally, the medium assignment is in between these two patterns. The percentages of
assigned space and order frequencies of classes are listed on table 1. The e?ective
pick-list size varies from 4 to 40 items per picking tour.
In the simulations, each pick list consists of (exactly) q picks. Every pick is
?rst assigned to storage class based on its order frequency class. The position of
each pick is randomly drawn. The number of replications for each scenario (a com-
bination of a storage assignment and a pick-list size) was 10 000. Figure 3 shows
the experimental results, where the length of the aisle was normalized to 1. The
di?erences are generally less than 5%. It con?rms that the probabilistic model pro-
vides a good approximation for the travel distance in a single aisle. When the pick-
list size is very large, the di?erence is very small. It is because the order picker has to
travel almost the entire aisle to pick up a large number of items; the average travel
distances found by both methods are close to this maximum travel distance.
Furthermore, the results from the approximation are always higher than the corre-
sponding simulation results. The reason is that we over-estimate the conditional
expected travel distance d
ij
.
From ?gure 3, we can also see that the random assignment always results in
the longest average travel distance compared to other assignments. The gap is large
when the pick-list size (q) is small, and becomes smaller when q increases. It is very
small when q is very large. This ?nding is in line with results in previous research
Table 1. Storage assignments (order frequency/storage space).
Assignment A-class B-class C-class
Skewed 80/20 15/30 5/50
Medium 50/30 30/30 20/40
Random 33.33/33.33 33.33/33.33 33.33/33.33
3568 T. Le-Duc and R.(M.)B.M. de Koster
on single aisle class-based assignment (see, for example, Hausman et al. 1976
and Graves et al. 1977). In the worst case, the di?erence between the approximation
and the simulation results for the random, medium and skewed assignment are
2.47%, 3.69% and 4.39% respectively. The picking time is more variable for the
skewed and medium assignment because of the fact that we estimate the travel
distance based on a random assignment in each zone (i.e. items are located
randomly in each zone). Thus, the more we deviate from random storage the
larger the approximation error is.
2.2 Multi-aisle model
2.2.1 Average travel distance estimation. In this section, we apply the formula
derived in the previous section to a warehouse with one cross-aisle (right in the
middle of the warehouse) and multiple aisles. Figure 1 shows the layout for a ware-
house with four aisles. This layout stems from Caron et al. (1998) and is fairly
common in practice. The order picking process in this type of warehouse can
be described as follows. Starting from the depot, the picker enters the nearest aisle
that contains picks (called requested aisle). Then the picker travels in the aisle
(goes as far as the farthest pick location), picks up the requested items, and returns
to the middle of the cross-aisle. From that point, the picker moves to the next
requested aisle which is nearest to the current position. After visiting the farthest
requested aisle, he returns to the starting point (depot). One may realize that the
routing method used here is so-called the return heuristic. In literature, there exist
many other routing methods (see, for example, Ratli? and Rosenthal 1983 and
De Koster and van der Poort 1998). However, only the return heuristic is relevant
for this type of layout. It is noted that it does not matter whether the order picker
Figure 3. Single-aisle model—the di?erence between approximation and simulation
results, L¼1.
3569 Distance estimation and storage zone optimization in a warehouse
completely serves one side of the warehouse ?rst and then goes to the other side
or simultaneously serves both sides, because in both cases we have exactly the same
total travel distance.
We can see that the travel distance of a picking tour consists of two components:
‘within-aisle’ and ‘cross-aisle’ travel distance. In the following, we will step by
step estimate these quantities.
We have
p
ij
¼ O
i
l
ij
a
j¼1
l
ij
8ði ¼ 1, . . . , c, j ¼ 1, . . . , aÞ:
Recall that p
ij
(i ¼1, . . . , c, j ¼1, . . . , a), is the probability that an item belonging to
class i located in aisle j is ordered, l
ij
!0 is the length in aisle j used for storing class i,
and O
i
>0 is the order frequency of class i. We assume that l
ij
and O
i
are given.
Furthermore, the number of picks requested from a class is proportional to the order
frequency of the class. Clearly, if one item is ordered then the probability that aisle j
is visited is
c
i¼1
p
ij
. Thus, if q items are required then the probability that the aisle j
is visited is:
m
j
¼ 1 À 1 À
c
i¼1
p
ij
_ _
q
:
The average travel distance from the centre line of the cross-aisle to the farthest
pick in aisle j (given that the aisle j is visited) is:
k
j
¼ w
a
=2 þ D
j
ðq
j
, cÞ:
Where q
j
is the conditionally expected number of items to be picked from aisle j:
q
j
¼
expected number of picks in aisle j
probability that aisle j is visited
¼
q
c
i¼1
p
ij
m
j
:
D
j
(q
j
, c) is the average travel distance from the starting point to the farthest pick
in the aisle j to pick up q
j
items. Applying formula (9), we have:
D
j
ðq
j
, cÞ % ðp
0
1j
Þq
j
l
1j
q
j
q
j
þ 1
þ
c
i¼2
ðp
0
kj
, q
j
Þ
iÀ1
k¼1
l
kj
þ
l
ij
q
j
p
0
ij
q
j
p
0
ij
þðp
0
ij
, q
j
Þ
i
k¼1
p
0
kj
_ _ _ _
where p
0
ij
¼ p
ij
=
c
i¼1
p
ij
8j ¼ 1, . . . , a ð Þ. It is easy to verify that
c
i¼1
p
0
ij
¼ 1
8j ¼ 1, . . . , a ð Þ.
The average ‘within-aisle’ travel distance of a tour can be now computed as
follows:
TD
WA
% 2
a
j¼1
½ expected travel distance if aisle j is visited ð Þ
 probability that aisle j is visited ð Þ?
3570 T. Le-Duc and R.(M.)B.M. de Koster
2
a
j¼1
k
j
m
j
¼ 2
a
j¼1
w
a
=2 þ D
j
ðq
j
, cÞ
_ _
1 À 1 À
c
i¼1
p
ij
_ _
q
_ _ _ _
¼ 2
a
j¼1
w
a
=2 þ p
0
1j
_ _
q
j
l
1j
q
j
q
j
þ 1
þ
c
i¼2
p
0
kj
, q
j
_ _
iÀ1
k¼1
l
kj
þ
l
ij
q
j
p
0
ij
ðq
j
p
0
ij
þð p
0
kj
, q
j
Þ
i
k¼1
p
0
kj
_ _ _ _ _ _
_
¸
¸
¸
¸
_
¸
¸
¸
¸
_
_
¸
¸
¸
¸
_
¸
¸
¸
¸
_
_
¸
¸
¸
¸
_
¸
¸
¸
¸
_
 1 À 1 À
c
i¼1
p
ij
_ _
q
_ _
_
¸
¸
¸
¸
_
¸
¸
¸
¸
_
: ð11Þ
Given that q picks are required, let n
j
( j ¼1, . . . , a/2) be the probability that at
least one of aisles j and (a Àj þ1) is visited. Due to the symmetrical property of
the layout, the probability that the aisle j and aisle (a Àj þ1) is visited are equal.
Therefore, n
j
( j ¼1, . . . , a/2) can be determined as follows:
n
j
¼ 1 À 1 À m
j
_ _
1 À m
aÀjþ1
_ _
¼ 1 À 1 À m
j
_ _
2
¼ 1 À 1 À
c
i¼1
p
ij
_ _
2q
:
In order to estimate the cross-aisle travel distance, we have to determine the
farthest visited pick-line (a pick-line j ( j ¼1, . . . , a/2) is de?ned as the line that crosses
two symmetrical storage aisles j and a Àj þ1, see ?gure 1). The procedure is similar
to estimating the farthest visited zone within an aisle. The cross-aisle travel
distance can be now estimated by:
TD
CA
¼2
a=2
j¼1
2j À 1 ð Þ w
b
=2 ð Þðprobability that j is the farthest pick-lineÞ
_ _
¼
a=2
j¼1
2j À 1 ð Þw
b
n
0
j
, q
_ _ _ _
ð12Þ
where n
0
j
¼ n
j
=
a=2
j¼1
n
j
8j ¼ 1, . . . , a=2 ð Þ and ðn
0
j
, qÞ ¼ ð
j
i¼1
n
0
i
Þ
q
À ð
jÀ1
i¼1
n
0
i
Þ
q
. It is
noted that w
b
/2 is the distance that an order picker has to travel along the cross-aisle
in order to reach the central line of the follow-up aisle.
Summing up TD
CA
and TD
WA
together we obtain a formula for estimating the
average travel distance of a picking tour TD.
2.2.2 Simulation test. Also in this case, we used simulation to examine the perfor-
mance of the proposed formula. In the experiment, we considered a warehouse
with six aisles and assumed that items are grouped into three classes and assigned
to storage locations by either the skewed, medium assignment as mentioned in
table 1. The e?ective pick-list size varies from four to 40 items per picking tour.
The aisle’s length is normalized to 1. Other input parameters can be found in ?gure 4.
The way the simulations were established is the same as for the single-aisle
case. For each simulation run we drew q picks (listed in the ?rst column), which
were ?rst assigned to classes based on the order frequencies of classes. Then, items
3571 Distance estimation and storage zone optimization in a warehouse
of class i (i ¼1, . . . , c) were assigned to aisle j ( j ¼1, . . . , a) based on l
ij
(note that
within each zone items were randomly stored). In the comparison, we used
10 000 replications for each scenario (a combination of a pick-list size and a
storage assignment). Figure 4 shows the results obtained from the probabilistic
model and simulations. In accordance with our expectation, the random assignment
always provides the longest average travel distance. The average travel distance is
an increasing concave function of the pick-list size. We also considered two other
warehouses, 10 and 6 aisles, respectively. The results that we obtained from
these two warehouses are very similar. Regarding to the maximum error of the
approximation: it slightly increases when the number of aisles increases (7.29%,
7.40% and 7.95% for the six-aisle, 10-aisle and 16-aisle warehouse, respectively).
3. Storage zone optimization
In the previous section, we have proposed a formula for estimating the average
travel distance of a picking tour. That is to say, for a given layout (L, a, c, w
a
, w
b
),
a pick frequency (O
i
), a storage assignment scheme (l
ij
) and a pick-list size q, we can
estimate the average travel distance of a picking tour (TD). In this section, we make
use of the formula to address the storage zone optimization problem, if the total zone
sizes (s
i
) are given.
3.1 Model formulation
The problem of determining the optimal storage space used for a certain class in
each aisle may arise in many situations. For example, when the warehouse is ?rst put
into service or when the assortment or the order pattern changes. More speci?cally,
we de?ne the problem as follows. For a given picking area (the length and width
of the layout are known), the number, length and width of aisles, the width of the
rack and cross-aisle, the class-based storage assignment scheme (pick frequencies
Figure 4. Multi-aisle model—the di?erence between approximation and simulation results
for the six-aisle warehouse with L¼1, w
a
¼0.107, w
b
¼0.179.
3572 T. Le-Duc and R.(M.)B.M. de Koster
of classes, and fraction of total storage space needed for each class), our objective
is to determine the optimal storage space (i.e. storage zone boundaries) for each
class in each aisle. We propose the following mathematical formulation for the
problem:
Min TD
WA
l
ij
_ _
þ TD
CA
l
ij
_ _
:
Subject to
c
i¼1
l
ij
¼ L 8j ¼ 1, . . . , a
a
j¼1
l
ij
¼ s
i
La 8i ¼ 1, . . . , c
p
ij
¼ l
ij
O
i
= s
i
La ð Þ 8 i ¼ 1, . . . , c, j ¼ 1, . . . , a ð Þ
l
ij
¼ l
i, aÀjþ1
8ði ¼ 1, . . . , c, j ¼ 1, . . . , a=2Þ
l
ij
! 0 8 i ¼ 1, . . . , c, j ¼ 1, . . . , a ð Þ
In the objective function, we minimize the average travel distance of a picking tour
to pick up q picks. It consists of two components: the within-aisle and cross-aisle
travel distance. The within-aisle travel distance is calculated by using formula (11).
The cross-aisle travel distance is determined by formula (12). In our formulation we
consider these distances as functions of l
ij
. In total, we have ?ve sets of constraints.
The ?rst set concerns the aisle’s length conservation. The second set concerns the
conservation of the total storage space for each class. The percentage of the total
storage space for a certain class is mainly determined by the physical size of items in
the class and the storage assignment scheme that we used. The third set shows the
relationship between p
ij
and l
ij
. The fourth set ensures the symmetrical property of
the layout. And the last set of constraints de?nes the non-negative property of
decision variables l
ij
’s.
We perceive that it could happen in practice that not the exact dimensions
but only the total ?oor area of the warehouse is ?xed. In this situation, besides
l
ij
’s, the aisle’s length L is also a decision variable. Our model is still applicable
in this case, as we can repeatedly use the model for varying values of L and
choose the solution that ?ts the constraints best.
In the above formulation, we have ?ve sets of linear constraints. The ?rst two sets
are similar to those in the classical transportation problem, which is known to be
solvable in polynomial time. However, we have a nonlinear objective function.
The computational time for this objective function is signi?cant when the pick-list
size is very large. Therefore, solving the problem up to optimality is time consuming.
The total solution space of the problem can be very large as it exponentially increases
with the number of storage aisles and product classes. To get a rough idea regarding
the computational time, we considered a warehouse with three product classes and
only six (storage) aisles, each divided into 100 space slots. The computational time to
?nd the optimal layout achieved by total enumeration of the state space was about
20 minutes (on a Pentium IV 2.4 GHz CPU computer) when the batch size was
40 order-lines per picking tour. From this computational experience we can con-
clude that for large warehouses, it is hard to solve the problem to optimality.
To circumvent this obstacle, we propose the following heuristic.
3573 Distance estimation and storage zone optimization in a warehouse
3.2 A proposed heuristic
We use the following terminologies. An identical-aisle layout is a layout in which
all aisles are identical (thus the storage space for a certain class is the same in all
aisles). Class i and j are called proximity classes if |i Àj| ¼1. Our idea is that we
?rst start with a zoning scheme and then, step by step, exchange storage spaces
between classes to get closer to the optimal solution. Clearly, the starting solution
plays a role here. We know that the idea behind the class-based storage strategy is
to locate fast moving classes as close as possible to the depot, by doing so we may
reduce the average travel distance of a picking tour. In a same manner, starting
from the identical-aisle layout, we exchange space slots of fast moving classes in
far-from-depot aisles with space slots of slower moving classes in the closer-to-depot
aisles. When exchanging space slots between aisles, the average travel distance of a
picking tour changes. Hence, in order to determine the optimal volume to be
exchanged we have to evaluate the average travel distance of a picking tour by
using the approximation formula that we have proposed. We limit ourselves to
consider only exchanges of single slots between proximity classes. As the layout is
symmetrical, we need to consider only one half of the warehouse.
procedure ZoningOpt
initialise /*start with the identical-aisle layout*/
for i from a/2 downto 2 do
for k from 1 to i À1 do
for j from 1 to c À1 do
if LegalExchange and ÁTD<0 then /*exchanging space slots
l
ji
¼l
ji
À1; l
jk
¼l
jk
þ1; between class j in aisle i
l
j À1, i
¼l
j À1, i
þ1; l
j À1, k
¼l
j À1, k
À1 and class j À1 in aisle k(i>k)*/
end if;
end do;
end do;
end do;
end sub;
where LegalExchange means that all l
ij
’s must be non-negative. It is noted that as
we start from a feasible solution and just swap storage classes between aisles, the
other conditions are automatically satis?ed. ÁTD is the di?erence between the aver-
age travel distance of a picking tour after the exchange and the current best
average travel distance. This di?erence can be calculated by using the formulas
that we mentioned above with appropriate values of the l
ij
’s.
To illustrate the method, suppose that we have a half layout with three aisles
(numbered from the depot as aisles 1 to 3) and three classes (A, B and C). Starting
from the farthest aisle (aisle 3), we ?rst do the exchange between aisle 3 and aisle 1.
It means that we ?rst swap, one by one, space slots of class A in aisle 3 for B in aisle 1.
Then we swap B in aisle 3 for C in aisle 1. Successively, we do the exchange between
aisle 3 and aisle 2. Finally, we consider aisles 2 and 1.
The running time of the algorithm depends on the number of aisles, the number
of classes, the number of space slots per aisle and the time needed to compute ÁTD
(which can be negligible). It is easy to verify that the complexity of the algorithm
is O(a
2
cs), where a is the number of aisles, c is the number of classes and s is the
3574 T. Le-Duc and R.(M.)B.M. de Koster
number of space slots per aisle (assuming that all aisles are divided into an equal
number of space slots). The heuristic we have proposed is a type of 2-opt exchange
technique, which belongs to neighbourhood-search-heuristic family (literature on
local search can be seen in, for example, Aarts and Lenstra 1997). These types of
heuristics are widely used for facility design problems (Tompkins et al. 2003).
3.3 Numerical results and discussions
To evaluate the performance of the heuristic and to determine the optimal zone
sizes in di?erent warehouses, we carried out various numerical experiments. In the
experiments, we considered the skewed and medium assignment for ?ve layouts
(1, 2, 3, 4 and 5 with 4, 6, 8, 12 and 24 aisles respectively) and a varying pick-list
size. Details about the parameters of the layouts are shown in table 2 and ?gure 5,
where the shape ratio () is de?ned as the ratio between the warehouse’s width,
Table 2. Comparison between optimal average travel distance and travel distance obtained
from heuristic and identical aisle layout.
Pick-list
size (q) Optimum Heuristic Identical
Percent
di?erence
heuristic-
optimum
Percent
di?erence
identical-
optimum
Layout 1: Four aisles, L¼100, w
a
¼10, w
b
¼15, s ¼100 and ¼0.3
Medium
assignment
1 114.52 114.52 115.00 0 0.41
2 196.48 196.63 197.77 0.08 0.65
12 578.23 578.23 578.23 0 0
Skewed
assignment
1 72.49 72.50 74.12 0 2.19
2 119.19 120.63 125.49 1.19 5.02
12 330.66 330.66 330.67 0 0
Layout 2: Six aisles, L¼100, w
a
¼10, w
b
¼15, s ¼100 and ¼0.45
Medium
assignment
1 128.57 128.58 130.00 0 1.10
2 220.63 221.22 221.25 0.27 0.28
12 729.06 729.06 729.06 0 0
Skewed
assignment
1 84.14 84.15 89.12 0 5.58
2 140.09 140.92 142.67 0.59 1.81
12 416.55 416.56 416.56 0 0
Layout 3: Eight aisles, L¼100, w
a
¼10, w
b
¼15, s ¼20 and ¼0.6
Medium
assignment
1 142.19 142.24 149.84 0.03 5.10
2 242.18 242.53 246.79 0.14 1.87
12 833.34 833.34 833.35 0 0
Skewed
assignment
1 94.39 94.50 104.75 0.12 9.90
2 157.89 158.34 164.91 0.28 4.26
12 482.02 482.02 482.03 0 0
Optimum, optimal average travel distances found by total enumeration.
Heuristic: average travel distances found by the heuristic.
Identical: average travel distances from the identical-aisle layout.
Percent di?erence heuristic–optimum: the di?erences (in percentage) between the heuristic and the
optimal results.
Percent di?erence identical–optimum: the di?erences (in percentage) between the solutions from the
identical-aisle layouts and the optimal results.
3575 Distance estimation and storage zone optimization in a warehouse
aw
b
/2, and the aisle’s length, L. The optimal average travel distance for layouts 1, 2
and 3 are found by total enumeration of the state space. Because the number of aisles
is large, we could not ?nd optimal results for layout 4 and 5. These layouts together
with layout 3 are used to see the change of the optimal shape of storage zone when
the pick-list size, assignment policy and shape ratio change. From the experiment
results, we can discuss the following aspects.
Figure 5. ‘Optimal’ storage zones for layout 2, 4 and 5 (only left-parts of the warehouses
are shown).
3576 T. Le-Duc and R.(M.)B.M. de Koster
3.3.1 Quality of the heuristic. Table 2 shows the di?erences between travel dis-
tances obtained from the optimum found by the total enumeration of the stata
space, the heuristic solution and the identical-aisle layout. The gaps between the
heuristic and the corresponding optimal results appear to be very small. In the
worst case, the heuristic result is only about 1.2% o? from the optimal result.
For large pick-list size the heuristic provides the optimal solution (see the discussion
in the robustness section). In all cases, the running time was less than 5 seconds.
3.3.2 Shape of the optimal storage zones. Figure 5 shows the ‘optimal’ zone sizes
for layout 2 ( ¼0.45), layout 4 ( ¼0.9) and layout 5 ( ¼1.8). We can see that the
optimal number of space slots for each classes in each aisle changes when the pick-
list size, storage assignment and shape ratio change. The optimal zoning scheme is
summarized in ?gure 6. Layout type I (identical-aisle warehouse) appears to be
the best for su?ciently large pick-list sizes, or small shape-ratio (thus not deep)
warehouses, while layout type IV is only good for large shape-ratio (deep) ware-
houses with rather small picks per route. It is surprising that layout type I is optimal
for large pick-list sizes. When we consider the continuous-storage space case, the
optimal storage layout depends on the depot position (see ?gure 7, based on
Tompkins et al. 2003). However, with the presence of the cross-aisle, the depot
position does not in?uence the optimal storage layout when the pick-list size
Depot
Layout type I
II I I
III II I
Medium assignment
Small
<1
Large
1-2
S
h
a
p
e
r
a
t
i
o
Pick-list size
Small
<12
Medium
12-24
Large
>=24
III II I
IV III I
Skewed assignment
Small
<1
Large
1-2
Pick-list size
S
h
a
p
e
r
a
t
i
o
B,C B,C B,C B,C
Layout type II Layout type III Layout type IV
Small
<12
Medium
12-24
Large
>=24
A A A
A
Figure 6. Shape of the optimal storage zone when pick-list size, storage assignment and
shape ratio change.
Depot
A C
r
o
s
s
a
i
s
l
e
Continuous storage space
Storage space with aisles
(sufficiently large pick-list sizes)
B,C
Figure 7. Optimal storage zoning in continuous storage space and in space with aisles for
su?ciently large pick-list sizes.
3577 Distance estimation and storage zone optimization in a warehouse
is su?ciently large, leading to the optimality of the identical-aisle zoning scheme.
The reason is that for large pick-list sizes it is likely that we have to visit all
storage aisles and, therefore, any position of the depot on the cross-aisle results in
the same average travel distance of a picking tour.
3.3.3 Robustness of the identical-aisle layout. From table 2, we can also see that
the di?erences between results from the identical-aisle layouts and the correspond-
ing optimal layouts are small for small pick-list sizes (less that 10%) and the gaps
decrease rapidly when the pick-list size grows (less than 0.01% when pick list-
size is larger than or equal to 12). To study this e?ect further, we considered
layout 1 (four-aisle warehouse). For each possible value of the number of space
slots used for the A-class in the aisle closest to the depot (l
11
), we found the corre-
sponding optimal layout. Figures 8 and 9 show the experimental results for the
skewed and medium assignment. As we can see, when the pick-list size is small
(q ¼2), the average travel distance of a picking route is a convex function of l
11
.
However, this curve becomes very ?at when the pick-list size is rather large (q ¼12).
It means that when q is large, multiple optimums (or near optimums) exist. As a
result, the optimal average travel distance, the best travel distance found by the
heuristic and from the identical-aisle layout are very close. This fact also explains
why the heuristic performs very well for large pick-list sizes (as our heuristic starts
from the identical-aisle layout).
From a practical point of view, this result is very interesting: instead of adjusting
the optimal zone borders for a single pick-list size, we now can select the identical-
aisle layout as a good approximation for all pick-list sizes. No doubt, this
approximation is better for the medium assignment than for the skewed assignment.
Figure 8. Optimal average travel distance for layout 1 with two picks per route.
3578 T. Le-Duc and R.(M.)B.M. de Koster
4. Concluding remarks
We have presented a probabilistic model for estimating the average travel distance
of a picking tour in a 2-block warehouse. Simulation tests con?rmed the high accu-
racy level of the formula. We make use of the model for the problem of ?nding the
optimal zoning scheme with respect to minimizing the average travel distance.
To solve this problem, we ?rst consider an exact approach. However, the algorithm
is time consuming; it cannot handle large warehouse instances (regarding the number
of aisles, classes and space slots). Hence, we propose a 2-opt exchange heuristic
to solve the problem. This heuristic exchanges proximity classes between aisles,
from far-to-depot aisles to closer-to-depot aisles. The method is rather simple,
but of a very good quality and fast. It can therefore be applied to many practical
warehouse design or improvement situations.
From the experiments, we found that for a given warehouse, the optimal storage
zones may change when the pick-list size and the storage assignment change.
For large pick-list sizes, the identical-aisle layout is the optimum. When the pick-
list size is small, the warehouse shape ratio is a decisive factor: the identical aisle may
not be the optimal layout if the shape ratio is large. However, for all investigated
cases, the identical-aisle layouts provide very good results that di?er hardly from the
optimal travel distance. This result is particularly important for practice, where pick-
list sizes may vary over time and where storage zone sizes may vary as well. On the
basis of our results, it would be advisable for such warehouses to simply create
an identical-aisle zoning scheme.
In the paper, we considered a simple layout and for this layout only the return
heuristic is relevant. In practice, more complex layouts (thus other routing methods)
may be used. The most e?cient routing heuristic known in literature is the combined
heuristic, where the return and traversal strategy are combined (Roodbergen and
de Koster 2001a). We think that is an interesting direction for our further research.
A second straightforward extension is to develop a model which iteratively uses our
Figure 9. Optimal average travel distance layout 1 with 12 picks per route.
3579 Distance estimation and storage zone optimization in a warehouse
model to determine the ‘global’ optimal storage space for each product class
and zoning scheme (for a given pick frequency).
References
Aarts, E.H.L. and Lenstra, J.K., Local Search in Combinatorial Optimisation, 1997
(Wiley: Chichester).
Bozer, Y.A. and White, J.A., Travel-time models for automated storage/retrieval systems.
IIE Trans., 1984, 16, 329–338.
Coron, F., Marchet, G. and Perego, A., Routing policies and COI-based storage policies
in picker-to-part systems. Int. J. Prod. Res, 1998, 36(3), 713–732.
Chew, E.P. and Tang, L.C., Travel time analysis for general item location assignment in
a rectangular warehouse. Euro. J. Op. Res., 1999, 112, 582–597.
De Koster, R. and van der Poort, E.S., Routing orderpickers in a warehouse: a comparison
between optimal and heuristic solutions. IIE Trans., 1998, 30, 469–480.
De Koster R., van der Poort, E.S. and Wolters, M., E?cient orderbatching methods in
warehouse. Int. J. Prod. Res., 1999, 37(7), 1479–1504.
Dekker, R., de Koster, R., van Kalleveen, H. and Roodbergen, K.J., Improving order picking
response time at Ankor’s warehouse. Interfaces, 2004, 34(4), 303–313.
Eynan, A. and Rosenblatt, M.J., An interleaving policy in automated storage/retrieval
systems. Int. J. Prod. Res., 1993, 31(1), 1–18.
Eynan, A. and Rosenblatt, M.J., Establishing zones in single-command class-based
rectangular AS/RS. IIE Trans., 1994, 26, 38–46.
Gademann, A.J.R.M., van den Berg, J.P. and van der Ho?, H.H., An order batching
algorithm for wave picking in a parallel-aisle warehouse. IIE Trans., 2001, 33,
385–398.
Gibson, D.R. and Sharp, G.P., Order batching procedures. Euro. J. Op. Res., 1992, 58(1),
57–67.
Goetschalckx, M. and Ratli?, D.H., Order picking in an aisle. IIE Trans., 1988, 20,
531–562.
Graves, S.C., Hausman, W.H. and Schwarz, L.B., Storage-retrieval interleaving in automatic
warehousing systems. Manage. Sci., 1977, 23(9), 935–945.
Hall, R.W., Distance approximation for routing manual pickers in a warehouse. IIE Trans.,
1993, 25, 77–87.
Hausman, W.H., Schwarz, L.B. and Graves, S.C., Optimal storage assignment in automatic
warehousing systems. Manage. Sci., 1976, 22(6), 629–638.
Jarvis, J.M. and McDowell, E.D., Optimal product layout in an order picking warehouse.
IIE Trans., 1991, 23(1), 93–102.
Larson, T.N., March, H. and Kusiak, A., A heuristic approach to warehouse layout with class
based storage. IIE Transactions, 1997, 29(4), 337–348.
Le-Duc, T. and de Koster, R., An approximation for determining the optimal order-
batch size for order pickers in single aisle warehouses. In Progress in Material
Handling Research, edited by M. Meller, M.K. Ogle, A.P. Brett, G.D. Taylor
and J. Usher, pp. 267–286, 2002 (The Material Handling Institute of America:
Charlotte, NC).
Pan, C.H. and Liu, S.Y., A comparative study of order batching algorithms. Omega Int. J.
Manage. Sci., 1995, 23(6), 691–700.
Petersen, C.G., The impact of routing and storage policies on warehouse e?ciency. Int. J. Op.
& Prod. Manage., 1999, 19(10), 1053–1064.
Petersen, C.G. and Schmenner, R.W., An evaluation of routing and volume-based storage
policies in an order picking operation. Dec. Sci., 1999, 30(2), 481–501.
Ratli?, H.D. and Rosenthal, A.S., Order picking in a rectangular warehouse: a solvable case of
the travelling salesman problem. Op. Res., 1983, 31(3), 507–521.
Roodbergen, K.J., Layout and Routing Methods for Warehouses, 2001 (Erasmus Research
Institute of Management: Erasmus University Rotterdam, The Netherlands).
3580 T. Le-Duc and R.(M.)B.M. de Koster
Roodbergen, K.J. and de Koster, R., Routing order-pickers in a warehouse with a middle
aisle. Euro. J. Op. Research, 2001a, 133(1), 32–43.
Roodbergen, K.J. and de Koster, R., Routing methods for warehouses with multiple cross
aisles. Int. J. Prod. Res., 2001b, 39(9), 1865–1883.
Rosenblatt, M.J. and Eynan, A., Deriving the optimal boundaries for class-based automatic
storage/retrieval systems. Manage. Sci., 1989, 35(12), 1519–1524.
Rosenwein, M.B., An application of cluster analysis to the problem of locating items within
a warehouse. IIE Trans., 1994, 26(1), 101–103.
Sarker, B.R. and Babu, P.S., Travel time models in automated storage/retrieval systems:
a critical review. Int. J. Prod. Econ., 1995, 40, 173–184.
Tompkins, J.A., White, J.A., Bozer, Y.A., Frazelle, E.H. and Tanchoco, J.M.A., Facilities
Planning, 2003 (John Wiley & Sons: NJ).
3581 Distance estimation and storage zone optimization in a warehouse
doc_861781954.pdf
Order picking has been considered as the most critical operation in warehousing.
International Journal of Production Research,
Vol. 43, No. 17, 1 September 2005, 3561–3581
Travel distance estimation and storage zone optimization in
a 2-block class-based storage strategy warehouse
T. LE-DUC* and R.(M.)B.M. DE KOSTER
RSM Erasmus University, The Netherlands
(Received November 2004)
Order picking has been considered as the most critical operation in warehousing.
Recent trends in logistics demand faster but more reliable order picking
systems. The e?ciency of an order picking process greatly depends on the storage
policy used, i.e. where products are located within the warehouse. In this paper,
we deal with the most popular storage policy that is class-based (or ABC) storage
strategy. Particularly, we investigate the problem of determining the optimal
storage boundaries (zones) of classes in each aisle for manually operated
warehouses.
We ?rst propose a probabilistic model that enables us to estimate the
average travel distance of a picking tour. We found that the di?erences between
results obtained from simulation and the model were slight. Using the average
travel distance as the objective function, we present a mathematical formulation
for the storage zone optimization problem. However, the exact approach
can handle only small size warehouse instances. To circumvent this obstacle,
we propose a heuristic for the problem. Numerical examples we conducted
show that the heuristic performs very well in all the cases.
Keywords: Order picking; Class-based storage strategy; Travel distance
estimation; Warehouse design
1. Introduction
Order picking can be described as the process of retrieving a number of items
from their storage locations to ?ll a number of independent customer orders.
Though it seems to be a simple operation, it is a laborious process and a major
cost factor for warehouses in both production and distribution environments.
It has been estimated that the cost of order picking may contribute up to 55% of
all operating costs in a typical warehouse (see, for example, Tompkins et al. 2003).
Furthermore, new developments and trends in the global economy have had a sub-
stantial impact on the order picking process for many warehouses; the demand
pattern (customer order characteristics) has changed from few but large orders
to many but small orders, which have to be processed within very tight time win-
dows. Therefore, simultaneously reducing the cost and increasing the speed of order
picking becomes more and more critical.
*Corresponding author. Email: [email protected]
International Journal of Production Research
ISSN 0020–7543 print/ISSN 1366–588X online # 2005 Taylor & Francis Group Ltd
http://www.tandf.co.uk/journals
DOI: 10.1080/00207540500142894
The performance and e?ciency of the order picking operation depend mainly
on the following factors (see also Petersen 1999):
1. The demand pattern.
2. The con?guration (layout) of the warehouse.
3. The storage strategy: how to allocate items within the warehouse
(e.g. randomly assigning items to storage locations or assigning items
based on their order frequencies, picking volume or COI (cube-per-order)
index, etc.).
4. The batching method: how to group orders and divide orders among
order pickers.
5. The routing and sorting method: how to determine the sequence of the
items to be picked and how to consolidate the picked items.
Except for the ?rst factor, the others are usually controllable and have been
investigated by many researchers recently. The routing method is the ?rst issue
that has received considerable attention in the warehousing literature. Some promi-
nent papers on the subject are Ratli? and Rosenthal (1983), Goetschalckx and
Ratli? (1988), Hall (1993), de Koster and van der Poort (1998) and Roodbergen
and de Koster (2001a,b). Theory covering the layout design and the inter-
action between routing and layout can be found in, for example, Jarvis and
McDowell (1991) and Roodbergen (2001). Batching issues are mentioned in
Gibson and Sharp (1992), Rosenwein (1994), Pan and Liu (1995), Chew and Tang
(1999), de Koster et al. (1999), Gademan et al. (2001) and Le-Duc and de Koster
(2003). It is rather obvious that with a given demand pattern, a routing and a
batching policy, a dedicated storage strategy results in a shorter total travel distance
than the random storage strategy (where incoming products are located randomly
over the warehouse). Literature on dedicated storage policies can be found
in, for example, Hausman et al. (1976), Caron et al. (1998) and Petersen and
Schmenner (1999).
In this paper we focus on picker-to-parts, narrow-aisle, manually operated
order picking systems, one of the most common systems in practice. The employed
storage policy is the class-based storage strategy, meaning that the items are divided
into classes (for example A, B, C, etc.) based on their pick frequencies. The storage
locations are divided into zones and each class is assigned to a zone such that
the fastest moving (i.e. most frequently ordered) classes are closest to the depot.
Within a pick frequency, no further distinction on pick frequency between products
is made. This storage policy was already mentioned by Hausman et al. (1976). In our
experience, it is widely used in practice because it is convenient to implement
and maintain; it can easily handle assortment changes or changes in pick frequency.
In addition, using a class-based storage strategy often leads to a substantial reduc-
tion in order pick travel distance as compared to random storage (see Hausman et al.
1976, Rosenblatt and Eynan 1989, Eynan and Rosenblatt 1994 and Larson et al.
1997). The average travel distance of a picking tour is crucial as it is linearly
related to the travel time, which is most often used as the objective in warehouse
optimization problems. Therefore, the primary objective of the research is to pro-
vide an analytical model for estimating the average travel distance of a picking
tour for this type of warehouses. This estimate will then be used for storage
zone optimization.
3562 T. Le-Duc and R.(M.)B.M. de Koster
Two main types of warehouse operation can be distinguished: picker-
to-parts (usually manual picking) and parts-to-picker (automated). In the automated
system, a dedicated storage and retrieval machine can move vertically and horizon-
tally along the rack, retrieving and putting away unit loads. In contrast, in picker-
to-parts systems an order picker usually travels along the aisles to pick multiple
items at multiple locations in the storage racks. Extensive literature exists on
travel distance estimation in both warehouse types, for example, Bozer and
White (1984), Goetschalckx and Ratli? (1988), Eynan and Rosenblatt (1993),
Hall (1993), Sarker and Babu (1995), Caron et al. (1998), Chew and Tang (1999)
and Roodbergen (2001).
Our research is distinct from previous research on the subject. Most recently,
Roodbergen (2001) proposes formulas for estimating the average travel distance
in both single-block and multi-block conventional warehouses under the random
storage strategy (incoming products are located randomly over the warehouse)
and the traversal routing strategy. His formulations perform better than previously
existing formulas. The limitation of these formulations is that they cannot be applied
to non-random (i.e. ABC, COI-based) storage strategy warehouses. Caron et al.
(1998) discuss the COI-based storage strategy and propose travel time models for
estimating the average travel distance of a picking tour when either the traversal
(S-shape) or the return routing heuristic are used. The COI-based strategy assigns
products with a low ratio of the required storage space to the order frequency to the
locations nearest to the depot. This storage strategy di?ers from the class-based
storage strategy, because it allocates products on an individual basis, while
the ABC storage strategy assigns products to storage locations in groups. In practice,
such a COI-based strategy can only be applied to very stable assortments with limited
changes in order frequency and limited changes in the stored volume. This situation
is, however, more and more uncommon in practice. Chew and Tang (1999) consider
the travel distance estimation problem with a general storage assignment strategy.
Their research di?ers from ours in two respects. Firstly, they study a di?erent type of
layout leading to di?erent travel time estimates. Secondly, in their paper, a product
class can only be assigned to storage locations on a whole-aisle basis. It means
that products from two di?erent classes cannot be stored in the same aisle. In our
study, their type of assignment is a special case; in other words, in our study a
partial-aisle assignment is allowed.
Furthermore, besides travel distance estimation, we also consider the storage
zone optimization problem, which is the problem of determining how much space
should be used for a certain product class in each aisle such that the average travel
distance of a picking tour is minimized. A ?rst motivation to consider this problem
arises from a recent case study of Dekker et al. (2004), where, for a multi-aisle
warehouse, 30% travel distance improvement was obtained after a few iterations
of adjusting the storage zone boundaries. A second motivation stems from the
literature on warehouse design. Though there exist some articles (for example,
Hausman et al. 1976, Graves et al. 1977 and Eynan and Rosenblatt 1993, 1994)
indicating how to zone single aisle unit-pick warehouses, no hard rules can be found
in literature about how to make ABC divisions for multi-aisle and multi-pick-per-
route situations. In practice, manual picking, multi-aisle and multi-pick-per-route
warehouses are the large majority of all warehouses. Therefore, a solution to this
problem can certainly be used in many warehouse design and control situations.
3563 Distance estimation and storage zone optimization in a warehouse
Early studies by Hausman et al. (1976) and Graves et al. (1977) suggest that the
A-zone should be very small. However, their studies concern aisle-bound automated
storage and retrieval machines where the machine has to return to the depot after
every pickup. Thus the machine is moving constantly from and to the depot, favour-
ing a highly skewed placement of items. In Dekker et al. (2004), multi-aisle and
multi-pick-per-route layouts with a larger A-zone in which the order picker can
spend some time without having to return to the depot or move to the next zone
may do better.
This paper is organized as follows. In the next section, we ?rst derive an
approximation formula for the average travel distance within an aisle with the
class-based storage strategy. Then, we apply the formula to estimate the average
travel distance of a picking tour for a multi-aisle layout. In section 3 we propose
a formulation for the storage zone optimization problem and then a heuristic pro-
cedure for solving the problem. Finally, in section 4, we draw some conclusions
and discuss a potential direction for further research.
The following system and operational assumptions are used throughout the
paper:
1. The warehouse consists of multiple identical rectangular racks (see ?gure 1).
Each rack can be used to store more than one product type.
2. The order picker can reach all items in the rack regardless of the rack’s height
and the vertical travel time within the storage aisle is negligible (this is typical
for conventional shelf-storage warehouses).
3. Further on in the paper, we de?ne the aisle’s storage space as the
aisle’s length. In reality, if the picker could reach four levels without vertical
transport (for example), the available storage space would be four times the
aisle’s length.
4. Items in the same class have the same order frequency. The order frequency
of each item-class is de?ned as the number of times that an item from
that class is required in some time period (a planning period); it is known
and constant through the planning period (see also Hausman et al. 1976).
5. We consider pick-by-order situations (no order batching effects).
The following notations are commonly used in the paper (see ?gure 1), local
notations are de?ned elsewhere:
a Total number of aisles (storage-aisles or pick-aisles).
l
ij
Partial length of aisle j used for storing of class i.
L
a
w
b
w
r
w
ij
l
Pick line
P
i
c
k
a
i
s
l
e
Depot
Storage aisle
Figure 1. Warehouse layout and notations.
3564 T. Le-Duc and R.(M.)B.M. de Koster
q Number of picks (or order-lines) in a picking tour (that is the
pick-list size).
c Number of (product) classes.
L Length of an aisle.
w
a
Width of the cross-aisle.
w
b
Centre-to-centre distance between two consecutive aisles.
w
r
Width of the (storage) rack.
O
i
Order frequency of class i.
s
i
Fraction of the total storage space that we use for class i.
p
ij
Probability that an item of class i located in aisle j is ordered (we assume
that this is proportional to the pick frequency of class i).
TD
CA
Total travel distance within the cross-aisle (called ‘within-aisle’ travel
distance).
TD
WA
Total travel distance within the aisles (called ‘within-aisle’ travel
distance).
2. Average travel distance estimation
2.1 Single aisle model
We consider a single aisle (aisle j, this implies
c
i¼1
p
ij
¼ 1) with a con?guration
given in ?gure 2. Zone 1, zone 2, . . . and zone c are reserved for items of class
1, 2, . . . and c respectively. We assume that within each zone pick item locations
are uniformly distributed. By conditioning on the farthest location of the requested
items, the expected time from the starting point (see ?gure 2) to the farthest
pick location to pick up q
j
picks can be computed as follows:
D
j
ðq
j
, cÞ ¼
c
i¼1
P
ij
Eðtravel timejfarthest pick in zone iÞ ¼
c
i¼1
P
ij
d
i
: ð1Þ
Zone 1
Zone 2
Zone c
P
i
c
k
a
i
s
l
e
j
Starting point
2 j
l
Figure 2. Single storage-aisle con?guration.
3565 Distance estimation and storage zone optimization in a warehouse
From (1), we can see that in order to determine D
j
(q
j
, c) (the expected travel distance
from the starting point to the farthest pick location) we have to determine P
ij
(the probability that the farthest pick is in zone i) and d
ij
(the corresponding expected
one-way travel distance). We consider the following situations:
. the farthest pick is in zone 1,
. the farthest pick is in zone 2 and
. the farthest pick is in zone i(i ¼3, . . . , c).
2.1.1 Farthest pick is in zone 1. If the farthest pick is in the zone 1, this means that
all picks are in zone 1 and no pick is in the zones from 2 to c:
P
1j
¼ p
q
j
1j
ð2Þ
d
1j
¼ Eðtravel distancejall picks in zone 1Þ ¼
l
1j
q
j
q
j
þ 1
ð3Þ
Equation (3) is based on the well-known property that the expectation of the
maximum of q
j
continuous uniformly distributed [0, 1] variables equals q
j
/(q
j
þ1).
Recall that p
ij
ð
c
i¼1
p
ij
¼ 1Þ is the probability that an item of class i located in aisle j
is ordered.
2.1.2 Further pick is in zone 2. The farthest pick in zone 2 is equivalent to at least
one pick in zone 2 and no pick in the zones from 3 to c (or all picks in zone 1 and
zone 2 but not all picks in zone 1):
P
2j
¼ ðp
1j
þ p
2j
Þ
q
j
À ðp
1j
Þ
q
j
: ð4Þ
d
2j
¼ l
1j
þ l
2j
E
N
2
N
2
þ 1
_ _
: ð5Þ
Where N
2
is the number of picks in zone 2. It is rather di?cult to compute d
2j
based
on (5). Therefore, we estimate d
2j
as follows. First, we calculate E(N
2
), the expected
number of picks in zone 2:
E N
2
ð Þ ¼
q
j
n¼1
nPðn picks in zone 2jall picks in zones 1 and 2, and not all picks in zone 1Þ
¼
q
j
n¼1
n
Pðn picks in zone 2, all picks in zones 1 and 2, and not all picks in zone 1Þ
Pðall picks in zones 1 and 2, and not all picks in zone 1Þ
¼
q
j
n¼1
n
Pðn picks in zone 2 and ðq
j
À nÞ picks in zone 1Þ
P
2j
¼
q
j
n¼1
n
q
j
n
_ _
ððp
2j
Þ=ðp
1j
þ p
2j
ÞÞ
_ _
n
ððp
1j
Þ=ðp
1j
þ p
2j
ÞÞ
_ _
q
j
Àn
ðp
1j
þ p
2j
Þ
q
j
À p
q
j
1j
_ _
¼
ðq
j
p
2j
Þ=ðp
1j
þ p
2j
Þ
ðp
1j
þ p
2j
Þ
q
j
À p
q
j
1j
:
3566 T. Le-Duc and R.(M.)B.M. de Koster
The last step is based on the property of Binomial distribution. Then, d
2j
can be
estimated as follows:
d
2j
% l
1j
þ l
2j
EðN
2
Þ
EðN
2
Þ þ 1
¼ l
1j
þ
l
2j
ðq
j
p
2j
Þ=ðp
1j
þ p
2j
Þ
_ _
= ðp
1j
þ p
2j
Þ
q
j
À p
q
j
1j
_ _
ðq
j
p
2j
Þ=ðp
1j
þ p
2j
Þ
_ _
= ðp
1j
þ p
2j
Þ
q
j
À p
q
j
1j
_ _
þ 1
¼ l
1j
þ
ðl
2j
q
j
p
2j
=p
1j
þ p
2j
Þ
ðq
j
p
2j
Þ=ðp
1j
þ p
2j
Þ þ ðp
1j
þ p
2j
Þ
q
j
À p
q
j
1j
¼ l
1j
þ
l
2j
q
j
p
2j
q
j
p
2j
þ ðp
1j
þ p
2j
Þ ðp
1j
þ p
2j
Þ
q
j
À p
q
j
1j
_ _ ð6Þ
2.1.3 Farthest pick is in zone i(i ¼3, . . . , c). If the farthest pick is in zone
i(i ¼3, . . . , c) then we can apply the same procedure as in two previous situations,
we have:
P
ij
i!3
¼ p
1j
þ p
2j
þ Á Á Á þ p
ij
_ _
q
j
À p
1j
þ p
2j
þ Á Á Á þ p
iÀ1, j
_ _
q
j
¼
i
k¼1
p
kj
_ _
q
j
À
iÀ1
k¼1
p
kj
_ _
q
j
ð7Þ
d
ij
i!3
%
iÀ1
k¼1
l
ij
þ
l
ij
q
j
p
ij
q
j
p
ij
þ p
ij
, q
j
_ _
i
k¼1
p
kj
ð8Þ
where we call ð
k
, Þ ¼ ð
i
k¼1
k
Þ
À ð
iÀ1
k¼1
k
Þ
:
Finally, substituting (2), (3), (4), (6), (7) and (8) into (1), we obtain:
D
j
ðq
j
, cÞ % p
q
j
1j
l
1j
q
j
q
j
þ 1
þ
c
i¼2
p
kj
, q
j
_ _
iÀ1
k¼1
l
kj
þ
l
ij
q
j
p
ij
q
j
p
ij
þ p
kj
, q
j
_ _
i
k¼1
p
kj
_ _ _ _
: ð9Þ
2.1.4 Simulation test. To approximate the error of the probabilistic model we pre-
sented above, we built a simulation model in Microsoft Excel using VBA (Visual
Basic for Applications). In the test, we considered the case that there are only three
classes. The ‘three classes’ (namely A, B and C) storage strategy is the most popular
one in practice.
3567 Distance estimation and storage zone optimization in a warehouse
In the case of three classes, it is easy to verify that:
Dðg, 3Þ % p
g
A
l
A
g
g þ 1
þ p
A
þ p
B
ð Þ
g
À p
A
ð Þ
g
_ _
:
 l
a
þ
l
B
gp
B
gp
B
þ p
A
þ p
B
ð Þ ðp
A
þ p
B
Þ
g
À p
g
A
_ _
_ _
þ 1 À p
A
þ p
B
ð Þ
g
_ _
l
A
þ l
B
þ
l
C
gp
C
gp
C
þ 1 À p
A
þ p
B
ð Þ
g
_ _
, ð10Þ
where g is the number of picks. p
A
, p
B
, p
C
and l
A
, l
B
, l
C
are the order frequencies
and storage length of class A, B and C correspondingly.
We considered three di?erent class-based assignments (ABC curves), namely:
skewed, random and medium. In the skewed assignment frequently ordered items
occupy only a very small portion of the total storage space. The A-class occupies
20% of the rack, but is responsible for 80% of the items. The random assignment
means that no distinction between item classes in the terms of order frequency
and required space can be made; they are randomly located within the warehouse.
Finally, the medium assignment is in between these two patterns. The percentages of
assigned space and order frequencies of classes are listed on table 1. The e?ective
pick-list size varies from 4 to 40 items per picking tour.
In the simulations, each pick list consists of (exactly) q picks. Every pick is
?rst assigned to storage class based on its order frequency class. The position of
each pick is randomly drawn. The number of replications for each scenario (a com-
bination of a storage assignment and a pick-list size) was 10 000. Figure 3 shows
the experimental results, where the length of the aisle was normalized to 1. The
di?erences are generally less than 5%. It con?rms that the probabilistic model pro-
vides a good approximation for the travel distance in a single aisle. When the pick-
list size is very large, the di?erence is very small. It is because the order picker has to
travel almost the entire aisle to pick up a large number of items; the average travel
distances found by both methods are close to this maximum travel distance.
Furthermore, the results from the approximation are always higher than the corre-
sponding simulation results. The reason is that we over-estimate the conditional
expected travel distance d
ij
.
From ?gure 3, we can also see that the random assignment always results in
the longest average travel distance compared to other assignments. The gap is large
when the pick-list size (q) is small, and becomes smaller when q increases. It is very
small when q is very large. This ?nding is in line with results in previous research
Table 1. Storage assignments (order frequency/storage space).
Assignment A-class B-class C-class
Skewed 80/20 15/30 5/50
Medium 50/30 30/30 20/40
Random 33.33/33.33 33.33/33.33 33.33/33.33
3568 T. Le-Duc and R.(M.)B.M. de Koster
on single aisle class-based assignment (see, for example, Hausman et al. 1976
and Graves et al. 1977). In the worst case, the di?erence between the approximation
and the simulation results for the random, medium and skewed assignment are
2.47%, 3.69% and 4.39% respectively. The picking time is more variable for the
skewed and medium assignment because of the fact that we estimate the travel
distance based on a random assignment in each zone (i.e. items are located
randomly in each zone). Thus, the more we deviate from random storage the
larger the approximation error is.
2.2 Multi-aisle model
2.2.1 Average travel distance estimation. In this section, we apply the formula
derived in the previous section to a warehouse with one cross-aisle (right in the
middle of the warehouse) and multiple aisles. Figure 1 shows the layout for a ware-
house with four aisles. This layout stems from Caron et al. (1998) and is fairly
common in practice. The order picking process in this type of warehouse can
be described as follows. Starting from the depot, the picker enters the nearest aisle
that contains picks (called requested aisle). Then the picker travels in the aisle
(goes as far as the farthest pick location), picks up the requested items, and returns
to the middle of the cross-aisle. From that point, the picker moves to the next
requested aisle which is nearest to the current position. After visiting the farthest
requested aisle, he returns to the starting point (depot). One may realize that the
routing method used here is so-called the return heuristic. In literature, there exist
many other routing methods (see, for example, Ratli? and Rosenthal 1983 and
De Koster and van der Poort 1998). However, only the return heuristic is relevant
for this type of layout. It is noted that it does not matter whether the order picker
Figure 3. Single-aisle model—the di?erence between approximation and simulation
results, L¼1.
3569 Distance estimation and storage zone optimization in a warehouse
completely serves one side of the warehouse ?rst and then goes to the other side
or simultaneously serves both sides, because in both cases we have exactly the same
total travel distance.
We can see that the travel distance of a picking tour consists of two components:
‘within-aisle’ and ‘cross-aisle’ travel distance. In the following, we will step by
step estimate these quantities.
We have
p
ij
¼ O
i
l
ij
a
j¼1
l
ij
8ði ¼ 1, . . . , c, j ¼ 1, . . . , aÞ:
Recall that p
ij
(i ¼1, . . . , c, j ¼1, . . . , a), is the probability that an item belonging to
class i located in aisle j is ordered, l
ij
!0 is the length in aisle j used for storing class i,
and O
i
>0 is the order frequency of class i. We assume that l
ij
and O
i
are given.
Furthermore, the number of picks requested from a class is proportional to the order
frequency of the class. Clearly, if one item is ordered then the probability that aisle j
is visited is
c
i¼1
p
ij
. Thus, if q items are required then the probability that the aisle j
is visited is:
m
j
¼ 1 À 1 À
c
i¼1
p
ij
_ _
q
:
The average travel distance from the centre line of the cross-aisle to the farthest
pick in aisle j (given that the aisle j is visited) is:
k
j
¼ w
a
=2 þ D
j
ðq
j
, cÞ:
Where q
j
is the conditionally expected number of items to be picked from aisle j:
q
j
¼
expected number of picks in aisle j
probability that aisle j is visited
¼
q
c
i¼1
p
ij
m
j
:
D
j
(q
j
, c) is the average travel distance from the starting point to the farthest pick
in the aisle j to pick up q
j
items. Applying formula (9), we have:
D
j
ðq
j
, cÞ % ðp
0
1j
Þq
j
l
1j
q
j
q
j
þ 1
þ
c
i¼2
ðp
0
kj
, q
j
Þ
iÀ1
k¼1
l
kj
þ
l
ij
q
j
p
0
ij
q
j
p
0
ij
þðp
0
ij
, q
j
Þ
i
k¼1
p
0
kj
_ _ _ _
where p
0
ij
¼ p
ij
=
c
i¼1
p
ij
8j ¼ 1, . . . , a ð Þ. It is easy to verify that
c
i¼1
p
0
ij
¼ 1
8j ¼ 1, . . . , a ð Þ.
The average ‘within-aisle’ travel distance of a tour can be now computed as
follows:
TD
WA
% 2
a
j¼1
½ expected travel distance if aisle j is visited ð Þ
 probability that aisle j is visited ð Þ?
3570 T. Le-Duc and R.(M.)B.M. de Koster
2
a
j¼1
k
j
m
j
¼ 2
a
j¼1
w
a
=2 þ D
j
ðq
j
, cÞ
_ _
1 À 1 À
c
i¼1
p
ij
_ _
q
_ _ _ _
¼ 2
a
j¼1
w
a
=2 þ p
0
1j
_ _
q
j
l
1j
q
j
q
j
þ 1
þ
c
i¼2
p
0
kj
, q
j
_ _
iÀ1
k¼1
l
kj
þ
l
ij
q
j
p
0
ij
ðq
j
p
0
ij
þð p
0
kj
, q
j
Þ
i
k¼1
p
0
kj
_ _ _ _ _ _
_
¸
¸
¸
¸
_
¸
¸
¸
¸
_
_
¸
¸
¸
¸
_
¸
¸
¸
¸
_
_
¸
¸
¸
¸
_
¸
¸
¸
¸
_
 1 À 1 À
c
i¼1
p
ij
_ _
q
_ _
_
¸
¸
¸
¸
_
¸
¸
¸
¸
_
: ð11Þ
Given that q picks are required, let n
j
( j ¼1, . . . , a/2) be the probability that at
least one of aisles j and (a Àj þ1) is visited. Due to the symmetrical property of
the layout, the probability that the aisle j and aisle (a Àj þ1) is visited are equal.
Therefore, n
j
( j ¼1, . . . , a/2) can be determined as follows:
n
j
¼ 1 À 1 À m
j
_ _
1 À m
aÀjþ1
_ _
¼ 1 À 1 À m
j
_ _
2
¼ 1 À 1 À
c
i¼1
p
ij
_ _
2q
:
In order to estimate the cross-aisle travel distance, we have to determine the
farthest visited pick-line (a pick-line j ( j ¼1, . . . , a/2) is de?ned as the line that crosses
two symmetrical storage aisles j and a Àj þ1, see ?gure 1). The procedure is similar
to estimating the farthest visited zone within an aisle. The cross-aisle travel
distance can be now estimated by:
TD
CA
¼2
a=2
j¼1
2j À 1 ð Þ w
b
=2 ð Þðprobability that j is the farthest pick-lineÞ
_ _
¼
a=2
j¼1
2j À 1 ð Þw
b
n
0
j
, q
_ _ _ _
ð12Þ
where n
0
j
¼ n
j
=
a=2
j¼1
n
j
8j ¼ 1, . . . , a=2 ð Þ and ðn
0
j
, qÞ ¼ ð
j
i¼1
n
0
i
Þ
q
À ð
jÀ1
i¼1
n
0
i
Þ
q
. It is
noted that w
b
/2 is the distance that an order picker has to travel along the cross-aisle
in order to reach the central line of the follow-up aisle.
Summing up TD
CA
and TD
WA
together we obtain a formula for estimating the
average travel distance of a picking tour TD.
2.2.2 Simulation test. Also in this case, we used simulation to examine the perfor-
mance of the proposed formula. In the experiment, we considered a warehouse
with six aisles and assumed that items are grouped into three classes and assigned
to storage locations by either the skewed, medium assignment as mentioned in
table 1. The e?ective pick-list size varies from four to 40 items per picking tour.
The aisle’s length is normalized to 1. Other input parameters can be found in ?gure 4.
The way the simulations were established is the same as for the single-aisle
case. For each simulation run we drew q picks (listed in the ?rst column), which
were ?rst assigned to classes based on the order frequencies of classes. Then, items
3571 Distance estimation and storage zone optimization in a warehouse
of class i (i ¼1, . . . , c) were assigned to aisle j ( j ¼1, . . . , a) based on l
ij
(note that
within each zone items were randomly stored). In the comparison, we used
10 000 replications for each scenario (a combination of a pick-list size and a
storage assignment). Figure 4 shows the results obtained from the probabilistic
model and simulations. In accordance with our expectation, the random assignment
always provides the longest average travel distance. The average travel distance is
an increasing concave function of the pick-list size. We also considered two other
warehouses, 10 and 6 aisles, respectively. The results that we obtained from
these two warehouses are very similar. Regarding to the maximum error of the
approximation: it slightly increases when the number of aisles increases (7.29%,
7.40% and 7.95% for the six-aisle, 10-aisle and 16-aisle warehouse, respectively).
3. Storage zone optimization
In the previous section, we have proposed a formula for estimating the average
travel distance of a picking tour. That is to say, for a given layout (L, a, c, w
a
, w
b
),
a pick frequency (O
i
), a storage assignment scheme (l
ij
) and a pick-list size q, we can
estimate the average travel distance of a picking tour (TD). In this section, we make
use of the formula to address the storage zone optimization problem, if the total zone
sizes (s
i
) are given.
3.1 Model formulation
The problem of determining the optimal storage space used for a certain class in
each aisle may arise in many situations. For example, when the warehouse is ?rst put
into service or when the assortment or the order pattern changes. More speci?cally,
we de?ne the problem as follows. For a given picking area (the length and width
of the layout are known), the number, length and width of aisles, the width of the
rack and cross-aisle, the class-based storage assignment scheme (pick frequencies
Figure 4. Multi-aisle model—the di?erence between approximation and simulation results
for the six-aisle warehouse with L¼1, w
a
¼0.107, w
b
¼0.179.
3572 T. Le-Duc and R.(M.)B.M. de Koster
of classes, and fraction of total storage space needed for each class), our objective
is to determine the optimal storage space (i.e. storage zone boundaries) for each
class in each aisle. We propose the following mathematical formulation for the
problem:
Min TD
WA
l
ij
_ _
þ TD
CA
l
ij
_ _
:
Subject to
c
i¼1
l
ij
¼ L 8j ¼ 1, . . . , a
a
j¼1
l
ij
¼ s
i
La 8i ¼ 1, . . . , c
p
ij
¼ l
ij
O
i
= s
i
La ð Þ 8 i ¼ 1, . . . , c, j ¼ 1, . . . , a ð Þ
l
ij
¼ l
i, aÀjþ1
8ði ¼ 1, . . . , c, j ¼ 1, . . . , a=2Þ
l
ij
! 0 8 i ¼ 1, . . . , c, j ¼ 1, . . . , a ð Þ
In the objective function, we minimize the average travel distance of a picking tour
to pick up q picks. It consists of two components: the within-aisle and cross-aisle
travel distance. The within-aisle travel distance is calculated by using formula (11).
The cross-aisle travel distance is determined by formula (12). In our formulation we
consider these distances as functions of l
ij
. In total, we have ?ve sets of constraints.
The ?rst set concerns the aisle’s length conservation. The second set concerns the
conservation of the total storage space for each class. The percentage of the total
storage space for a certain class is mainly determined by the physical size of items in
the class and the storage assignment scheme that we used. The third set shows the
relationship between p
ij
and l
ij
. The fourth set ensures the symmetrical property of
the layout. And the last set of constraints de?nes the non-negative property of
decision variables l
ij
’s.
We perceive that it could happen in practice that not the exact dimensions
but only the total ?oor area of the warehouse is ?xed. In this situation, besides
l
ij
’s, the aisle’s length L is also a decision variable. Our model is still applicable
in this case, as we can repeatedly use the model for varying values of L and
choose the solution that ?ts the constraints best.
In the above formulation, we have ?ve sets of linear constraints. The ?rst two sets
are similar to those in the classical transportation problem, which is known to be
solvable in polynomial time. However, we have a nonlinear objective function.
The computational time for this objective function is signi?cant when the pick-list
size is very large. Therefore, solving the problem up to optimality is time consuming.
The total solution space of the problem can be very large as it exponentially increases
with the number of storage aisles and product classes. To get a rough idea regarding
the computational time, we considered a warehouse with three product classes and
only six (storage) aisles, each divided into 100 space slots. The computational time to
?nd the optimal layout achieved by total enumeration of the state space was about
20 minutes (on a Pentium IV 2.4 GHz CPU computer) when the batch size was
40 order-lines per picking tour. From this computational experience we can con-
clude that for large warehouses, it is hard to solve the problem to optimality.
To circumvent this obstacle, we propose the following heuristic.
3573 Distance estimation and storage zone optimization in a warehouse
3.2 A proposed heuristic
We use the following terminologies. An identical-aisle layout is a layout in which
all aisles are identical (thus the storage space for a certain class is the same in all
aisles). Class i and j are called proximity classes if |i Àj| ¼1. Our idea is that we
?rst start with a zoning scheme and then, step by step, exchange storage spaces
between classes to get closer to the optimal solution. Clearly, the starting solution
plays a role here. We know that the idea behind the class-based storage strategy is
to locate fast moving classes as close as possible to the depot, by doing so we may
reduce the average travel distance of a picking tour. In a same manner, starting
from the identical-aisle layout, we exchange space slots of fast moving classes in
far-from-depot aisles with space slots of slower moving classes in the closer-to-depot
aisles. When exchanging space slots between aisles, the average travel distance of a
picking tour changes. Hence, in order to determine the optimal volume to be
exchanged we have to evaluate the average travel distance of a picking tour by
using the approximation formula that we have proposed. We limit ourselves to
consider only exchanges of single slots between proximity classes. As the layout is
symmetrical, we need to consider only one half of the warehouse.
procedure ZoningOpt
initialise /*start with the identical-aisle layout*/
for i from a/2 downto 2 do
for k from 1 to i À1 do
for j from 1 to c À1 do
if LegalExchange and ÁTD<0 then /*exchanging space slots
l
ji
¼l
ji
À1; l
jk
¼l
jk
þ1; between class j in aisle i
l
j À1, i
¼l
j À1, i
þ1; l
j À1, k
¼l
j À1, k
À1 and class j À1 in aisle k(i>k)*/
end if;
end do;
end do;
end do;
end sub;
where LegalExchange means that all l
ij
’s must be non-negative. It is noted that as
we start from a feasible solution and just swap storage classes between aisles, the
other conditions are automatically satis?ed. ÁTD is the di?erence between the aver-
age travel distance of a picking tour after the exchange and the current best
average travel distance. This di?erence can be calculated by using the formulas
that we mentioned above with appropriate values of the l
ij
’s.
To illustrate the method, suppose that we have a half layout with three aisles
(numbered from the depot as aisles 1 to 3) and three classes (A, B and C). Starting
from the farthest aisle (aisle 3), we ?rst do the exchange between aisle 3 and aisle 1.
It means that we ?rst swap, one by one, space slots of class A in aisle 3 for B in aisle 1.
Then we swap B in aisle 3 for C in aisle 1. Successively, we do the exchange between
aisle 3 and aisle 2. Finally, we consider aisles 2 and 1.
The running time of the algorithm depends on the number of aisles, the number
of classes, the number of space slots per aisle and the time needed to compute ÁTD
(which can be negligible). It is easy to verify that the complexity of the algorithm
is O(a
2
cs), where a is the number of aisles, c is the number of classes and s is the
3574 T. Le-Duc and R.(M.)B.M. de Koster
number of space slots per aisle (assuming that all aisles are divided into an equal
number of space slots). The heuristic we have proposed is a type of 2-opt exchange
technique, which belongs to neighbourhood-search-heuristic family (literature on
local search can be seen in, for example, Aarts and Lenstra 1997). These types of
heuristics are widely used for facility design problems (Tompkins et al. 2003).
3.3 Numerical results and discussions
To evaluate the performance of the heuristic and to determine the optimal zone
sizes in di?erent warehouses, we carried out various numerical experiments. In the
experiments, we considered the skewed and medium assignment for ?ve layouts
(1, 2, 3, 4 and 5 with 4, 6, 8, 12 and 24 aisles respectively) and a varying pick-list
size. Details about the parameters of the layouts are shown in table 2 and ?gure 5,
where the shape ratio () is de?ned as the ratio between the warehouse’s width,
Table 2. Comparison between optimal average travel distance and travel distance obtained
from heuristic and identical aisle layout.
Pick-list
size (q) Optimum Heuristic Identical
Percent
di?erence
heuristic-
optimum
Percent
di?erence
identical-
optimum
Layout 1: Four aisles, L¼100, w
a
¼10, w
b
¼15, s ¼100 and ¼0.3
Medium
assignment
1 114.52 114.52 115.00 0 0.41
2 196.48 196.63 197.77 0.08 0.65
12 578.23 578.23 578.23 0 0
Skewed
assignment
1 72.49 72.50 74.12 0 2.19
2 119.19 120.63 125.49 1.19 5.02
12 330.66 330.66 330.67 0 0
Layout 2: Six aisles, L¼100, w
a
¼10, w
b
¼15, s ¼100 and ¼0.45
Medium
assignment
1 128.57 128.58 130.00 0 1.10
2 220.63 221.22 221.25 0.27 0.28
12 729.06 729.06 729.06 0 0
Skewed
assignment
1 84.14 84.15 89.12 0 5.58
2 140.09 140.92 142.67 0.59 1.81
12 416.55 416.56 416.56 0 0
Layout 3: Eight aisles, L¼100, w
a
¼10, w
b
¼15, s ¼20 and ¼0.6
Medium
assignment
1 142.19 142.24 149.84 0.03 5.10
2 242.18 242.53 246.79 0.14 1.87
12 833.34 833.34 833.35 0 0
Skewed
assignment
1 94.39 94.50 104.75 0.12 9.90
2 157.89 158.34 164.91 0.28 4.26
12 482.02 482.02 482.03 0 0
Optimum, optimal average travel distances found by total enumeration.
Heuristic: average travel distances found by the heuristic.
Identical: average travel distances from the identical-aisle layout.
Percent di?erence heuristic–optimum: the di?erences (in percentage) between the heuristic and the
optimal results.
Percent di?erence identical–optimum: the di?erences (in percentage) between the solutions from the
identical-aisle layouts and the optimal results.
3575 Distance estimation and storage zone optimization in a warehouse
aw
b
/2, and the aisle’s length, L. The optimal average travel distance for layouts 1, 2
and 3 are found by total enumeration of the state space. Because the number of aisles
is large, we could not ?nd optimal results for layout 4 and 5. These layouts together
with layout 3 are used to see the change of the optimal shape of storage zone when
the pick-list size, assignment policy and shape ratio change. From the experiment
results, we can discuss the following aspects.
Figure 5. ‘Optimal’ storage zones for layout 2, 4 and 5 (only left-parts of the warehouses
are shown).
3576 T. Le-Duc and R.(M.)B.M. de Koster
3.3.1 Quality of the heuristic. Table 2 shows the di?erences between travel dis-
tances obtained from the optimum found by the total enumeration of the stata
space, the heuristic solution and the identical-aisle layout. The gaps between the
heuristic and the corresponding optimal results appear to be very small. In the
worst case, the heuristic result is only about 1.2% o? from the optimal result.
For large pick-list size the heuristic provides the optimal solution (see the discussion
in the robustness section). In all cases, the running time was less than 5 seconds.
3.3.2 Shape of the optimal storage zones. Figure 5 shows the ‘optimal’ zone sizes
for layout 2 ( ¼0.45), layout 4 ( ¼0.9) and layout 5 ( ¼1.8). We can see that the
optimal number of space slots for each classes in each aisle changes when the pick-
list size, storage assignment and shape ratio change. The optimal zoning scheme is
summarized in ?gure 6. Layout type I (identical-aisle warehouse) appears to be
the best for su?ciently large pick-list sizes, or small shape-ratio (thus not deep)
warehouses, while layout type IV is only good for large shape-ratio (deep) ware-
houses with rather small picks per route. It is surprising that layout type I is optimal
for large pick-list sizes. When we consider the continuous-storage space case, the
optimal storage layout depends on the depot position (see ?gure 7, based on
Tompkins et al. 2003). However, with the presence of the cross-aisle, the depot
position does not in?uence the optimal storage layout when the pick-list size
Depot
Layout type I
II I I
III II I
Medium assignment
Small
<1
Large
1-2
S
h
a
p
e
r
a
t
i
o
Pick-list size
Small
<12
Medium
12-24
Large
>=24
III II I
IV III I
Skewed assignment
Small
<1
Large
1-2
Pick-list size
S
h
a
p
e
r
a
t
i
o
B,C B,C B,C B,C
Layout type II Layout type III Layout type IV
Small
<12
Medium
12-24
Large
>=24
A A A
A
Figure 6. Shape of the optimal storage zone when pick-list size, storage assignment and
shape ratio change.
Depot
A C
r
o
s
s
a
i
s
l
e
Continuous storage space
Storage space with aisles
(sufficiently large pick-list sizes)
B,C
Figure 7. Optimal storage zoning in continuous storage space and in space with aisles for
su?ciently large pick-list sizes.
3577 Distance estimation and storage zone optimization in a warehouse
is su?ciently large, leading to the optimality of the identical-aisle zoning scheme.
The reason is that for large pick-list sizes it is likely that we have to visit all
storage aisles and, therefore, any position of the depot on the cross-aisle results in
the same average travel distance of a picking tour.
3.3.3 Robustness of the identical-aisle layout. From table 2, we can also see that
the di?erences between results from the identical-aisle layouts and the correspond-
ing optimal layouts are small for small pick-list sizes (less that 10%) and the gaps
decrease rapidly when the pick-list size grows (less than 0.01% when pick list-
size is larger than or equal to 12). To study this e?ect further, we considered
layout 1 (four-aisle warehouse). For each possible value of the number of space
slots used for the A-class in the aisle closest to the depot (l
11
), we found the corre-
sponding optimal layout. Figures 8 and 9 show the experimental results for the
skewed and medium assignment. As we can see, when the pick-list size is small
(q ¼2), the average travel distance of a picking route is a convex function of l
11
.
However, this curve becomes very ?at when the pick-list size is rather large (q ¼12).
It means that when q is large, multiple optimums (or near optimums) exist. As a
result, the optimal average travel distance, the best travel distance found by the
heuristic and from the identical-aisle layout are very close. This fact also explains
why the heuristic performs very well for large pick-list sizes (as our heuristic starts
from the identical-aisle layout).
From a practical point of view, this result is very interesting: instead of adjusting
the optimal zone borders for a single pick-list size, we now can select the identical-
aisle layout as a good approximation for all pick-list sizes. No doubt, this
approximation is better for the medium assignment than for the skewed assignment.
Figure 8. Optimal average travel distance for layout 1 with two picks per route.
3578 T. Le-Duc and R.(M.)B.M. de Koster
4. Concluding remarks
We have presented a probabilistic model for estimating the average travel distance
of a picking tour in a 2-block warehouse. Simulation tests con?rmed the high accu-
racy level of the formula. We make use of the model for the problem of ?nding the
optimal zoning scheme with respect to minimizing the average travel distance.
To solve this problem, we ?rst consider an exact approach. However, the algorithm
is time consuming; it cannot handle large warehouse instances (regarding the number
of aisles, classes and space slots). Hence, we propose a 2-opt exchange heuristic
to solve the problem. This heuristic exchanges proximity classes between aisles,
from far-to-depot aisles to closer-to-depot aisles. The method is rather simple,
but of a very good quality and fast. It can therefore be applied to many practical
warehouse design or improvement situations.
From the experiments, we found that for a given warehouse, the optimal storage
zones may change when the pick-list size and the storage assignment change.
For large pick-list sizes, the identical-aisle layout is the optimum. When the pick-
list size is small, the warehouse shape ratio is a decisive factor: the identical aisle may
not be the optimal layout if the shape ratio is large. However, for all investigated
cases, the identical-aisle layouts provide very good results that di?er hardly from the
optimal travel distance. This result is particularly important for practice, where pick-
list sizes may vary over time and where storage zone sizes may vary as well. On the
basis of our results, it would be advisable for such warehouses to simply create
an identical-aisle zoning scheme.
In the paper, we considered a simple layout and for this layout only the return
heuristic is relevant. In practice, more complex layouts (thus other routing methods)
may be used. The most e?cient routing heuristic known in literature is the combined
heuristic, where the return and traversal strategy are combined (Roodbergen and
de Koster 2001a). We think that is an interesting direction for our further research.
A second straightforward extension is to develop a model which iteratively uses our
Figure 9. Optimal average travel distance layout 1 with 12 picks per route.
3579 Distance estimation and storage zone optimization in a warehouse
model to determine the ‘global’ optimal storage space for each product class
and zoning scheme (for a given pick frequency).
References
Aarts, E.H.L. and Lenstra, J.K., Local Search in Combinatorial Optimisation, 1997
(Wiley: Chichester).
Bozer, Y.A. and White, J.A., Travel-time models for automated storage/retrieval systems.
IIE Trans., 1984, 16, 329–338.
Coron, F., Marchet, G. and Perego, A., Routing policies and COI-based storage policies
in picker-to-part systems. Int. J. Prod. Res, 1998, 36(3), 713–732.
Chew, E.P. and Tang, L.C., Travel time analysis for general item location assignment in
a rectangular warehouse. Euro. J. Op. Res., 1999, 112, 582–597.
De Koster, R. and van der Poort, E.S., Routing orderpickers in a warehouse: a comparison
between optimal and heuristic solutions. IIE Trans., 1998, 30, 469–480.
De Koster R., van der Poort, E.S. and Wolters, M., E?cient orderbatching methods in
warehouse. Int. J. Prod. Res., 1999, 37(7), 1479–1504.
Dekker, R., de Koster, R., van Kalleveen, H. and Roodbergen, K.J., Improving order picking
response time at Ankor’s warehouse. Interfaces, 2004, 34(4), 303–313.
Eynan, A. and Rosenblatt, M.J., An interleaving policy in automated storage/retrieval
systems. Int. J. Prod. Res., 1993, 31(1), 1–18.
Eynan, A. and Rosenblatt, M.J., Establishing zones in single-command class-based
rectangular AS/RS. IIE Trans., 1994, 26, 38–46.
Gademann, A.J.R.M., van den Berg, J.P. and van der Ho?, H.H., An order batching
algorithm for wave picking in a parallel-aisle warehouse. IIE Trans., 2001, 33,
385–398.
Gibson, D.R. and Sharp, G.P., Order batching procedures. Euro. J. Op. Res., 1992, 58(1),
57–67.
Goetschalckx, M. and Ratli?, D.H., Order picking in an aisle. IIE Trans., 1988, 20,
531–562.
Graves, S.C., Hausman, W.H. and Schwarz, L.B., Storage-retrieval interleaving in automatic
warehousing systems. Manage. Sci., 1977, 23(9), 935–945.
Hall, R.W., Distance approximation for routing manual pickers in a warehouse. IIE Trans.,
1993, 25, 77–87.
Hausman, W.H., Schwarz, L.B. and Graves, S.C., Optimal storage assignment in automatic
warehousing systems. Manage. Sci., 1976, 22(6), 629–638.
Jarvis, J.M. and McDowell, E.D., Optimal product layout in an order picking warehouse.
IIE Trans., 1991, 23(1), 93–102.
Larson, T.N., March, H. and Kusiak, A., A heuristic approach to warehouse layout with class
based storage. IIE Transactions, 1997, 29(4), 337–348.
Le-Duc, T. and de Koster, R., An approximation for determining the optimal order-
batch size for order pickers in single aisle warehouses. In Progress in Material
Handling Research, edited by M. Meller, M.K. Ogle, A.P. Brett, G.D. Taylor
and J. Usher, pp. 267–286, 2002 (The Material Handling Institute of America:
Charlotte, NC).
Pan, C.H. and Liu, S.Y., A comparative study of order batching algorithms. Omega Int. J.
Manage. Sci., 1995, 23(6), 691–700.
Petersen, C.G., The impact of routing and storage policies on warehouse e?ciency. Int. J. Op.
& Prod. Manage., 1999, 19(10), 1053–1064.
Petersen, C.G. and Schmenner, R.W., An evaluation of routing and volume-based storage
policies in an order picking operation. Dec. Sci., 1999, 30(2), 481–501.
Ratli?, H.D. and Rosenthal, A.S., Order picking in a rectangular warehouse: a solvable case of
the travelling salesman problem. Op. Res., 1983, 31(3), 507–521.
Roodbergen, K.J., Layout and Routing Methods for Warehouses, 2001 (Erasmus Research
Institute of Management: Erasmus University Rotterdam, The Netherlands).
3580 T. Le-Duc and R.(M.)B.M. de Koster
Roodbergen, K.J. and de Koster, R., Routing order-pickers in a warehouse with a middle
aisle. Euro. J. Op. Research, 2001a, 133(1), 32–43.
Roodbergen, K.J. and de Koster, R., Routing methods for warehouses with multiple cross
aisles. Int. J. Prod. Res., 2001b, 39(9), 1865–1883.
Rosenblatt, M.J. and Eynan, A., Deriving the optimal boundaries for class-based automatic
storage/retrieval systems. Manage. Sci., 1989, 35(12), 1519–1524.
Rosenwein, M.B., An application of cluster analysis to the problem of locating items within
a warehouse. IIE Trans., 1994, 26(1), 101–103.
Sarker, B.R. and Babu, P.S., Travel time models in automated storage/retrieval systems:
a critical review. Int. J. Prod. Econ., 1995, 40, 173–184.
Tompkins, J.A., White, J.A., Bozer, Y.A., Frazelle, E.H. and Tanchoco, J.M.A., Facilities
Planning, 2003 (John Wiley & Sons: NJ).
3581 Distance estimation and storage zone optimization in a warehouse
doc_861781954.pdf