<< стр. 8(всего 15)СОДЕРЖАНИЕ >>

60

t

Figure 5.13 Inventory level of sparkling mineral water in the Potan Up problem.

Determining length, width and height of a storage zone
In this section a methodology for determining length, width and height of a storage
zone (see Figure 5.14) is described. The same methodology can be easily extended to
other types of storage zone. As explained in the introductory section, the maximum

TLFeBOOK
DESIGNING AND OPERATING A WAREHOUSE 169

Ly

Lx

Figure 5.14 A traditional storage zone.

height of the racks/stacks/drawers is determined by the storage technology. Therefore,
the sizing decision amounts to calculating the length and the width. Let m be the
required number of stocking positions; О±x and О±y the occupation of a unit load (e.g.
a pallet or a cartoon) along the directions x and y, respectively; wx and wy , the width
of the side aisles and of the central aisle, respectively; nz the number of stocking
zones along the z-direction allowed by the storage technology; v the average speed
of a picker. The decision variables are nx , the number of storage locations along the
x-direction, and ny , the number of storage locations along the y-direction.
The extension Lx of the stocking zone along the direction x is given by the following
relation,
Lx = (О±x + 2 wx )nx ,
1

where, for the sake of simplicity, nx is assumed to be an even number. Similarly, the
extension Ly is
Ly = О±y ny + wy .
Therefore, under the hypothesis that a handling operation consists of storing or the
retrieving a single load, and all stocking points have the same probability of being
accessed, the average distance covered by a picker is: 2(Lx /2 + Ly /4) = Lx + Ly /2.
Hence, the problem of sizing the storage zone can be formulated as follows.
Minimize
О±y ny + wy
nx
(О±x + 2 wx ) +
1
(5.3)
v 2v
subject to

nx ny nz m (5.4)
nx , ny 0, integer, (5.5)

TLFeBOOK
170 DESIGNING AND OPERATING A WAREHOUSE

where the objective function (5.3) is the average travel time of a picker, while inequal-
ity (5.4) states that the number of stocking positions is at least equal to m.
Problem (5.3)вЂ“(5.5) can be easily solved by relaxing the integrality constraints on
the variables nx and ny . Then, inequality (5.4) will be satisп¬Ѓed as an equality:
m
nx = . (5.6)
ny nz
Therefore, nx can be removed from the relaxed problem in the following way.
Minimize
О±y ny + wy
m
(О±x + 2 wx ) +
1
(5.7)
ny nz v 2v
subject to
ny 0.
Since the objective function (5.7) is convex, the minimizer ny can be found through
the following relation:
О± y ny + w y
m
d
(О±x + 2 wx ) + = 0.
1
d(ny ) ny nz v 2v ny =ny

Hence,
2m(О±x + 2 wx )
1
ny = . (5.8)
О±y nz
Finally, replacing ny in Equation (5.6) by the ny value given by Equation 5.8, nx is
determined:
mО±y
nx = . (5.9)
2nz (О±x + 2 wx )
1

ВЇВЇ
Consequently, a feasible solution (nx , ny ) is

nx = nx
ВЇ and ny = ny .
ВЇ

Alternatively, a better solution could be found by setting nx = nx (or ny = ny ),
ВЇ ВЇ
provided that Equation (5.4) is satisп¬Ѓed.

Wagner Bros is going to build a new warehouse near Sidney (Australia) in order
to supply its sales points in New South Wales. On the basis of a preliminary analysis
of the problem, it has been decided that the facility will accommodate at least 780
90 Г— 90 cm2 pallets. The goods will be stored onto racks and transported by means of
traditional trolleys. Each rack has four shelves, each of which can store a single pallet.
Each pallet occupies a 1.05 Г— 1.05 m2 area. Racks are arranged as in Figure 5.14,
where side aisles are 3.5 m wide, while the central aisle is 4 m wide. The average

TLFeBOOK
DESIGNING AND OPERATING A WAREHOUSE 171

Reserve zone Forward zone

Figure 5.15 Warehouse with a reserve/forward storage system.

speed of a trolley is 5 km/h. Using Equations (5.8) and (5.9), variables nx and ny are
determined:
780 Г— 1.05
nx = = 6.05,
2 Г— 4 Г— (1.05 + 3.5
2)

2 Г— 780 Г— (1.05 + 3.5
2)
ny = = 32.25.
1.05 Г— 4
Assuming nx = 6 and ny = 33, the total number of storage locations turns out to be
ВЇ ВЇ
792, while Lx = [1.05 + (3.5/2)] Г— 6 = 16.8 m and Ly = 1.05 Г— 33 + 4 = 38.65 m.

Sizing a forward area
In a reserve/forward storage system (see Figure 5.15), the main decision is to deter-
mine how much space must be assigned to each product in the forward area. In
principle, once this decision has been made, the problem of determining the length,
width and height of the pick-up zone should be solved. However, since each picking
route in the forward area usually collects small quantities of several items, at every
trip a large portion of the total length of the aisles is usually covered (see Figure 5.15).
Hence, the dimensions of the pick-up zone are not critical and can be selected quite
arbitrarily.
If the number of items stored in the forward area increases, replenishments are less
frequent. However, at the same time the extension of the forward area increases and,
consequently, the average picking time also goes up.
Let (see Figure 5.16) n be the number of products, o the average number of orders
per time period; d the average number of orders in a batch; oj , j = 1, . . . , n, the
average number of orders containing product j ; uj , j = 1, . . . , n, the average number
of items of product j in an order; v the average speed of a picker in the forward area;
h the cost of a picker per time period; k the area and equipment cost per unit of lane

TLFeBOOK
172 DESIGNING AND OPERATING A WAREHOUSE

mj
wj

Figure 5.16 Storage locations assigned to an item j, j = 1, . . . , n.

length and per time period; fj , j = 1, . . . , n, the п¬Ѓxed cost of a replenishment of
product j ; gj , j = 1, . . . , n, the variable cost for replenishing a unit of product j ;
wj , j = 1, . . . , n, the length of a portion of aisle occupied by an item of product j ;
mj , j = 1, . . . , n, the number of items of product j that can be stored in an aisle
position. The decision variables are the number of aisle positions sj , j = 1, . . . , n,
assigned to each product j .
The contribution of product j, j = 1, . . . , n, to the cost of picking items from the
reserve area is
(o/d)wj sj
c1j (sj ) = h , (5.10)
v
where o/d represents the average number of batches picked up per time period (i.e. the
average number of times a picker passes in front of a position per time period); wj sj
is the total length of the portion of aisle assigned to the product j , [(o/d)wj sj ]/v
represents the average time spent during a time period by the picker because of
product j .
The contribution of product j, j = 1, . . . , n, to the average cost per time period
of replenishing the forward area is
uj oj
c2j (sj ) = fj + gj uj oj ,
mj sj

where uj oj represents the average demand per time period of product j , while mj sj
is the number of storage locations assigned to product j , and (uj oj )/(mj sj ) is the
average number of resupplies of product j per time period.
The portion of the space and equipment costs due to product j, j = 1, . . . , n, is

c3j (sj ) = kwj sj .

TLFeBOOK
DESIGNING AND OPERATING A WAREHOUSE 173

Moreover, let sj and sj , j = 1, . . . , n, be lower and upper bounds on the
min max

number of positions of product j , respectively. The problem of sizing the forward
area can be modelled as follows.
Minimize
n
[c1j (sj ) + c2j (sj ) + c3j (sj )] (5.11)
j =1
subject to
j = 1, . . . , n,
min max
sj sj sj , (5.12)
j = 1, . . . , n,
sj 0, integer, (5.13)
where the objective function (5.11) is the sum of the costs due to the various prod-
ucts, while constraints (5.12) impose lower and upper bounds on the number of aisle
positions assigned to each item j, j = 1, . . . , n.
Problem (5.11)вЂ“(5.13) can be decomposed into n subproblems, one for each product
j, j = 1, . . . , n, and solved by exploiting the convexity of the objective function.
Step 1. Determine the value sj , j = 1, . . . , n, that minimizes the total cost cj (sj ) =
c1j (sj ) + c2j (sj ) + c3j (sj ) due to product j :
dcj (sj )
= 0, j = 1, . . . , n,
dsj sj =sj

fj uj oj
sj = j = 1, . . . , n.
,
mj [howj /dv + kwj ]

Set sj = sj , if cj ( sj ) < cj ( sj ), otherwise s = sj , j = 1, . . . , n.
ВЇ
в€—
Step 2. Compute the optimal solution sj , j = 1, . . . , n, as follows:
пЈ±
пЈґsj , if sj < sj ,
ВЇ
min min
пЈґ
пЈІ
в€—
sj = sj , j = 1, . . . , n.
ВЇ ВЇ
min max
if sj sj sj ,
пЈґ
пЈґ max
пЈіs , if s > s max ,
ВЇ j
j j

The total length of the aisles wtot can then be obtained by the following relation:
n
в€—
=
tot
w wj sj . (5.14)
j =1

An estimate of the number of pickers can be computed by dividing the total work-
load per time period [(o/d)w tot ]/v by the duration of a work shift. This approach
underestimates the number of pickers since it assumes that the orders are uniformly
distributed in time in such a way that pickers are never idle. A more realistic estimate
can be heuristically obtained by reducing v by an appropriate вЂ˜utilization coefп¬ЃcientвЂ™
empirically estimated, or by using an appropriate simulation model.

TLFeBOOK
174 DESIGNING AND OPERATING A WAREHOUSE

Table 5.2 Characteristics of the products at stock in the Wellen warehouse.

fj gj
wj
Item (euros per (euros per
oj uj mj
(j ) supply) unit of items) (m)

1 40 4 5 0.2 0.75 12
2 60 2 5 0.2 1.00 8
3 35 5 5 0.2 0.75 12
4 45 3 5 0.2 1.00 8
5 95 2 5 0.2 1.00 8
6 65 4 5 0.2 0.75 12
7 45 2 5 0.2 0.75 12
8 50 4 5 0.2 1.00 8
9 65 3 5 0.2 1.00 8
10 45 5 5 0.2 0.75 12

Wellen is a Belgian п¬Ѓrm manufacturing and distributing mechanical parts for numer-
ical control machines. Its warehouse located in Herstal consists of a wide reserve zone
(where the goods are stocked as stacks), and of a forward zone. At present 10 prod-
ucts are stored (see Table 5.2). Then, o = 400 orders per day, d = 3 orders per lot,
v = 12 000 m per day, h = в‚¬75 per day, while the area and equipment cost per unit of
aisle length k is assumed to be negligible. The minimum and the maximum number of
positions for the various products are reported in Table 5.3. The number of positions
в€—
sj , j = 1, . . . , 10, to be assigned to the different products in the forward zone can
be obtained through the two-stage procedure previously described. The results are
reported in Table 5.4. Consequently, the total length w tot of the aisles of the forward
zone is equal to 98.5 m (see Equation (5.14)), while the workload is around 1.09
working days, so that at least two pickers are required.

5.3 Tactical Decisions
The main tactical decision consists of allocating products to space. In this section, the
problem is modelled as a structured LP problem, namely, the classical transportation
problem.

5.3.1 Product allocation
The allocation of products within a warehouse is based on the principle that fast-
moving products must be placed closer to the I/O ports in order to minimize the overall
handling time. In the sequel, the case of a dedicated storage policy is examined. The

TLFeBOOK
DESIGNING AND OPERATING A WAREHOUSE 175

Table 5.3 Minimum and maximum number of aisle positions in the Wellen warehouse.

min max
sj sj
Item (j )

1 9 14
2 5 12
3 13 15
4 8 10
5 7 20
6 9 11
7 10 13
8 8 15
9 11 16
10 14 19

Table 5.4 Number of aisle positions in the forward zone of the Wellen warehouse.

в€—
sj sj cj ( sj ) sj c j ( sj ) sj sj
Item (j )

1 10.33 10 44.92 11 44.94 10 10
2 9.49 9 39.83 10 39.83 9 9
3 10.80 10 48.54 11 48.50 11 13
4 10.06 10 43.77 11 43.84 10 10
5 11.94 11 57.96 12 57.90 12 12
6 13.17 13 68.46 14 68.49 13 11
7 7.75 7 27.73 8 27.69 8 10
8 12.25 12 60.42 13 60.45 12 12
9 12.09 12 59.16 13 59.21 12 12
10 12.25 12 60.31 13 60.34 12 14

allocation problem amounts to assigning each of the md storage locations available to
a product. Let n be the number of products; mj , j = 1, . . . , n, the number of storage
locations required for product j (in a dedicated storage policy, relation n=1 mj j
md holds); R the number of I/O ports of the warehouse; pj r , j = 1, . . . , n, r =
1, . . . , R, the average number of handling operations on product j through I/O port
r per time period; trk , r = 1, . . . , R, k = 1, . . . , md , the travel time from I/O port r
and storage location k.
Under the hypothesis that all storage locations have an identical utilization rate,
it is possible to compute the cost cj k , j = 1, . . . , n, k = 1, . . . , md , of assigning
storage location k to product j ,
R
pj r
cj k = trk , (5.15)
mj
r=1

TLFeBOOK
176 DESIGNING AND OPERATING A WAREHOUSE
I/O port 2

30 40

25 35

26 36

21 31
10 20

5 15

6 16

1 11
I/O port 1

Figure 5.17 Warehouse of the Malabar company.

where pj r /mj represents the average number of handling operations per time period
on product j between I/O port r and anyone of the storage locations assigned to the
product. Consequently, (pj r /mj )trk is the average travel time due to storage location
k if it is assigned to product j .
Let xj k , j = 1, . . . , n, k = 1, . . . , md , be a binary decision variable, equal to 1 if
storage location k is assigned to product j , 0 otherwise. The problem of seeking the
optimal product allocation to the storage locations can then be modelled as follows.
Minimize
md
n
cj k xj k (5.16)
j =1 k=1

subject to
md
xj k = mj , j = 1, . . . , n, (5.17)
k=1
n
k = 1, . . . , md ,
xj k 1, (5.18)
j =1
xj k в€€ {0, 1}, j = 1, . . . , n, k = 1, . . . , md , (5.19)

where constraints (5.17) state that all the items at stock must be allocated, while
constraints (5.18) impose that each storage location k, k = 1, . . . , md , can be assigned
to at most one product.
It is worth noting that because of the particular structure of constraints (5.17) and
(5.18), relations (5.19) can be replaced with the simpler nonnegativity conditions,

j = 1, . . . , n, k = 1, . . . , md ,
xj k 0, (5.20)

TLFeBOOK
DESIGNING AND OPERATING A WAREHOUSE 177

Table 5.5 Features of the products of the Malabar company.

Number of storages and retrievals
per day in the Malabar warehouse
Storage
Item locations I/O port 1 I/O port 2

1 12 25 18
2 6 16 26
3 8 14 30
4 4 24 22
5 8 22 22

Table 5.6 Distance (in metres) between storage
locations and I/O port 1 in the Malabar warehouse.

Storage Storage Storage Storage
location Distance location Distance location Distance location Distance

1 2 11 2 21 14 31 14
2 4 12 4 22 16 32 16
3 6 13 6 23 18 33 18
4 8 14 8 24 20 34 20
5 10 15 10 25 22 35 22
6 3 16 3 26 15 36 15
7 5 17 5 27 17 37 17
8 7 18 7 28 19 38 19
9 9 19 9 29 21 39 21
10 11 20 11 30 23 40 23

Table 5.7 Distance (in metres) between storage
locations and I/O port 2 in the Malabar warehouse.

Storage Storage Storage Storage
location Distance location Distance location Distance location Distance

1 22 11 22 21 10 31 10
2 20 12 20 22 8 32 8
3 18 13 18 23 6 33 6
4 16 14 16 24 4 34 4
5 14 15 14 25 2 35 2
6 23 16 23 26 11 36 11
7 21 17 21 27 9 37 9
8 19 18 19 28 7 38 7
9 17 19 17 29 5 39 5
10 15 20 15 30 3 40 3

TLFeBOOK
178 DESIGNING AND OPERATING A WAREHOUSE

Cost coefп¬Ѓcients cj k , j = 1, . . . 5, k = 1, . . . , 20, in the Malabar problem.
Table 5.8

Assignment cost

Storage Product Product Product Product Product
j =1 j =2 j =3 j =4 j =5
location k

1 37.17 100.67 86.00 133.00 66.00
2 38.33 97.33 82.00 134.00 66.00
3 39.50 94.00 78.00 135.00 66.00
4 40.67 90.67 74.00 136.00 66.00
5 41.83 87.33 70.00 137.00 66.00
6 40.75 107.67 91.50 144.50 71.50
7 41.92 104.33 87.50 145.50 71.50
8 43.08 101.00 83.50 146.50 71.50
9 44.25 97.67 79.50 147.50 71.50
10 45.42 94.33 75.50 148.50 71.50

11 37.17 100.67 86.00 133.00 66.00
12 38.33 97.33 82.00 134.00 66.00
13 39.50 94.00 78.00 135.00 66.00
14 40.67 90.67 74.00 136.00 66.00
15 41.83 87.33 70.00 137.00 66.00
16 40.75 107.67 91.50 144.50 71.50
17 41.92 104.33 87.50 145.50 71.50
18 43.08 101.00 83.50 146.50 71.50
19 44.25 97.67 79.50 147.50 71.50
20 45.42 94.33 75.50 148.50 71.50

since it is known a priori that there exists an optimal solution of problem (5.16)вЂ“
(5.18), (5.20) in which the variables take 0/1 values.

Malabar Ltd is an Indian company having a warehouse with two I/O ports and
40 storage locations, arranged in four racks (see Figure 5.17). The characteristics of
the products at stock are reported in Table 5.5, while the distances between the two
I/O ports and the storage locations are indicated in Tables 5.6 and 5.7. The optimal
product allocation can found through model (5.16)вЂ“(5.18), (5.20), in which n = 5,
md = 40, while mj , j = 1, . . . , 5 are calculated on the basis of the second column
of Table 5.5. Cost coefп¬Ѓcients cj k , j = 1, . . . , 5, k = 1, . . . , 40, are indicated in
Tables 5.8 and 5.9 and calculated using Equation (5.15), where it is assumed that
travel time trk from I/O port r = 1, 2, to storage location k, k = 1, . . . , 40, is
directly proportional to the corresponding distance. The optimal solution is reported
in Table 5.10. It is worth noting that two storage locations (locations 26 and 27) are
not used since the positions available are 40, while 5 =1 mj = 38.
j

TLFeBOOK
DESIGNING AND OPERATING A WAREHOUSE 179

Table 5.9 Cost coefп¬Ѓcients cj k , j = 1, . . . 5, k = 21, . . . , 40, in the Malabar problem.

Assignment cost

Storage Product Product Product Product Product
j =1 j =2 j =3 j =4 j =5
location k

21 44.17 80.67 62.00 139.00 66.00
22 45.33 77.33 58.00 140.00 66.00
23 46.50 74.00 54.00 141.00 66.00
24 47.67 70.67 50.00 142.00 66.00
25 48.83 67.33 46.00 143.00 66.00
26 47.75 87.67 67.50 150.50 71.50
27 48.92 84.33 63.50 151.50 71.50
28 50.08 81.00 59.50 152.50 71.50
29 51.25 77.67 55.50 153.50 71.50
30 52.42 74.33 51.50 154.50 71.50

31 44.17 80.67 62.00 139.00 66.00
32 45.33 77.33 58.00 140.00 66.00
33 46.50 74.00 54.00 141.00 66.00
34 47.67 70.67 50.00 142.00 66.00
35 48.83 67.33 46.00 143.00 66.00
36 47.75 87.67 67.50 150.50 71.50
37 48.92 84.33 63.50 151.50 71.50
38 50.08 81.00 59.50 152.50 71.50
39 51.25 77.67 55.50 153.50 71.50
40 52.42 74.33 51.50 154.50 71.50

Table 5.10 Optimal allocation of products in the Malabar warehouse.

Storage Storage Storage Storage
location Product location Product location Product location Product

1 1 11 1 21 5 31 5
2 4 12 4 22 2 32 2
3 4 13 4 23 2 33 2
4 5 14 5 24 2 34 2
5 5 15 5 25 3 35 3
6 1 16 1 26 вЂ” 36 5
7 1 17 1 27 вЂ” 37 5
8 1 18 1 28 3 38 3
9 1 19 1 29 3 39 3
10 1 20 1 30 3 40 3

TLFeBOOK
180 DESIGNING AND OPERATING A WAREHOUSE

If the warehouse has a single I/O port (R = 1), the problem solving method-
ology can be simpliп¬Ѓed. In fact, under this hypothesis, cost coefп¬Ѓcients cj k , j =
1, . . . , n, k = 1, . . . , md , take the following form,
pj 1
cj k = t1k = aj bk ,
mj
where aj = pj 1 /mj and bk = t1k depend only on product j and on storage location
k, respectively. Then, the optimal product allocation can be determined by using the
following procedure.
Step 1. Construct a vector О± of n=1 mj components, in which there are mj copies of
j
each aj , j = 1, . . . , n. Sort the vector О± by nonincreasing values of its components.
Deп¬Ѓne ПѓО± (i) in such a way that ПѓО± (i) = j if О±i = aj , i = 1, . . . , n mr .r=1
Step 2. Let b be the vector of md components corresponding to values bk , k =
1, . . . , md . Sort the vector b by nondecreasing values of its components. Let ОІ be the
vector of n=1 mj components, corresponding to the п¬Ѓrst n=1 mj components
j j
of the sorted vector b. Deп¬Ѓne ПѓОІ (i) in such a way that ПѓОІ (i) = k if ОІi = bk , i =
1, . . . , n mr .
r=1
Step 3. Determine the optimal solution of problem (5.16)вЂ“(5.18), (5.20) as
n
в€—
= 1, i = 1, . . . ,
xПѓО± (i),ПѓОІ (i) mj
j =1
в€—
and xj k = 0, for all the remaining components.
This procedure is based on the fact that the minimization of the scalar product of
two vectors О± and ОІ is achieved by ordering О± by nonincreasing values and ОІ by
nondecreasing values.

If the warehouse of Malabar company (see the previous problem) has a single I/O
port (corresponding to port 1 in Figure 5.17), the coefп¬Ѓcients aj , j = 1, . . . , 5, are
those reported in Table 5.11. For the sake of simplicity, travel times are assumed to
be equal to distances (see Table 5.6). Values of О±i , ПѓО± (i), ОІi , ПѓОІ (i), i = 1, . . . , 38,
are reported in Table 5.12. The optimal solution is reported in Table 5.13. It is worth
noting that no item is allocated to the storage locations farthest from the I/O port
(locations 30 and 40).

5.4 Operational Decisions
Operational decisions comprise storage and retrieval planning as well as order assem-
bly. Because of the randomness of the orders, these decisions have to be made in real-
time. They may include one or more of the following activities depending on which

TLFeBOOK
DESIGNING AND OPERATING A WAREHOUSE 181

Table 5.11 Characteristics of products in the Malabar problem.

Product Storage Number of storages and
aj
(j ) locations retrievals per day

1 12 43 3.58
2 6 42 7.00
3 8 44 5.50
4 4 46 11.50
5 8 44 5.50

Table 5.12 Values of О±i , ПѓО± (i), ОІi , ПѓОІ (i), for i = 1, . . . , 38, in the Malabar problem.

i О±i ПѓО± (i) ОІi ПѓОІ (i) i О±i ПѓО± (i) ОІi ПѓОІ (i)

1 11.50 4 2 1 20 5.50 5 11 20
2 11.50 4 2 11 21 5.50 5 14 21
3 11.50 4 3 6 22 5.50 5 14 31
4 11.50 4 3 16 23 5.50 5 15 26
5 7.00 2 4 2 24 5.50 5 15 36
6 7.00 2 4 12 25 5.50 5 16 22
7 7.00 2 5 7 26 5.50 5 16 32
8 7.00 2 5 17 27 3.58 1 17 27
9 7.00 2 6 3 28 3.58 1 17 37
10 7.00 2 6 13 29 3.58 1 18 23
11 5.50 3 7 8 30 3.58 1 18 33
12 5.50 3 7 18 31 3.58 1 19 28
13 5.50 3 8 4 32 3.58 1 19 38
14 5.50 3 8 14 33 3.58 1 20 24
15 5.50 3 9 9 34 3.58 1 20 34
16 5.50 3 9 19 35 3.58 1 21 29
17 5.50 3 10 5 36 3.58 1 21 39
18 5.50 3 10 15 37 3.58 1 22 25
19 5.50 5 11 10 38 3.58 1 22 35

technologies and policies are used: the formation of batches (see Section 5.4.1), picker
routing (see Section 5.4.2), S/R machine scheduling (see Problem 5.4) and vehicle

5.4.1 Batch formation
If batch picking is used, customer orders are combined into batches. Batches can be
formed in a number of ways depending on whether the warehouse is zoned or not.
In what follows a simple two-stage procedure for the single-zone case is presented.

TLFeBOOK
182 DESIGNING AND OPERATING A WAREHOUSE

Table 5.13 Optimal product allocation to storage locations in the Malabar problem.

Storage Storage Storage Storage
location Product location Product location Product location Product

1 4 11 4 21 5 31 5
2 2 12 2 22 5 32 5
3 2 13 2 23 1 33 1
4 3 14 3 24 1 34 1
5 3 15 3 25 1 35 1
6 4 16 4 26 5 36 5
7 2 17 2 27 1 37 1
8 3 18 3 28 1 38 1
9 3 19 3 29 1 39 1
10 5 20 5 30 вЂ” 40 вЂ”

In the п¬Ѓrst stage, the optimal batch size d в€— is estimated in an attempt to balance the
picking and sorting efforts. Then in Step 2 batches are created according to a вЂ˜п¬Ѓrst
come п¬Ѓrst servedвЂ™ (FCFS) policy by aggregating d в€— consecutive orders.

Batch sizing. Batches are sized in an attempt to minimize the total workload, which
is the sum of the total picking and sorting times. In what follows, this approach is
illustrated for the conп¬Ѓguration in Figure 5.18, in which goods are retrieved by one
or more pickers and then transported to the shipping zone by a belt conveyor.
Let o be the average number of orders per time period, u the average number of
items in an order, t1 the time needed to make a path including all storage locations,
t2 the traversal time on foot of the shipping zone, where orders are assembled. The
decision variable is the average number of orders in a lot d.
Under the hypothesis that the items are uniformly distributed and that each batch
is made up of many items, the time spent for picking a batch is approximately t1 . As
o/d is the average number of pickings per time period, the time devoted to picking
operations is ot1 /d per time period. On the other hand, the time spent for sorting the
items in the shipping zone is О±uot2 d, where О± в€€ (0, 1) is a parameter to be deп¬Ѓned
either empirically or through a simulation model. In order to determine the optimal
d value, the following model has to be solved.
Minimize
ot1
+ О±uot2 d (5.21)
d
subject to
d 0, integer, (5.22)

where the objective function (5.21) is the workload per time period. The optimal solu-
tion of problem (5.21)вЂ“(5.22) can be obtained by means of the following procedure.

TLFeBOOK
DESIGNING AND OPERATING A WAREHOUSE 183

Shipping zone

Figure 5.18 Batch picking in a warehouse equipped with a belt conveyor.

Step 1. Determine the minimum point d of function c(d) = ot1 /d + О±uot2 d, by
imposing that the п¬Ѓrst derivative of c(d) becomes zero:

t1
d= .
О±ut2

Step 2. Let d в€— = d if c( d ) < c( d ), otherwise d в€— = d .
Hence, d в€— increases as the size of the storage zone increases, and decreases as the
average number of items in an order increases.

Clavier distributes French ties in Brazil. Its warehouse located in Manaus has a
layout similar to the one represented in Figure 5.18, with 15 aisles, each one of which
is 25 m long and 3.5 m wide. The area occupied by a pallet is 1.05 Г— 1.05 m2 . The
vehicles used for picking goods move at about 3.8 km/h, while the time to traverse
the shipping zone on foot is about 1.5 min. The average number of orders handled in
a day is 300, and the average number of items in an order is 10. The parameter О± has
been empirically set equal to 0.1. Hence,
1.05 + 25 Г— 30 + 3.5 Г— 15 + 1.05 Г— 28
t1 = Г— 60 = 13.15 min.
3800
and
13.15
d= = 2.96.
0.1 Г— 10 Г— 1.5
Finally, since c( d ) > c( d ), the batch size is d в€— = 3.

TLFeBOOK
184 DESIGNING AND OPERATING A WAREHOUSE

Figure 5.19 Routing of a picker in a storage zone with side aisles having a single entrance
(the dark-coloured storage locations are the ones where a retrieval has to be performed).

5.4.2 Order picker routing
In W/RPSs, where pickers travel on foot or by motorized trolley and may visit multi-
ple aisles, order picker routing is a major issue. Picker routing is part of a large class
of combinatorial optimization problems known as vehicle routing problems (VRPs),
which will be examined extensively in Chapter 7 in the context of distribution man-
agement. In this section a single picker problem, known as road travelling salesman
problem (RTSP), is illustrated. The RTSP is a slight variant of the classical travelling
salesman problem (TSP) (see Section 7.3) and consists of determining a least-cost
tour including a subset of vertices of a graph. The RTSP is NP-hard, but, in the case
of warehouses, it is often solvable in polynomial time due to the particular charac-
teristics of the travel network. If each aisle has a single entrance, the least duration
route is obtained by п¬Ѓrst visiting all the required storage locations placed in the upper
side aisles and then the required storage locations situated in the lower side aisles
(see Figure 5.19). On the other hand, if the side aisles have some interruptions (i.e.
if there is more than one cross aisle), the problem can be solved to optimality by
using the Ratliff and Rosenthal dynamic programming algorithm, whose worst-case
computational complexity is a linear function of the number of side aisles. However,
if there are several cross aisles, the number of states and transitions increases rapidly
and the use of the dynamic programming procedure becomes impractical. Therefore,
in what follows, two simple heuristics are illustrated. The reader interested in the
Ratliff and Rosenthal algorithm is referred to the list at the end of the chapter.

S-shape heuristic. Any aisle containing at least one item to be retrieved is traversed
entirely. Aisles where there are no items to be picked are skipped.

TLFeBOOK
DESIGNING AND OPERATING A WAREHOUSE 185

Figure 5.20 Routing of a picker in a storage zone with side aisles having two entrances (the
dark-coloured storage locations are the ones where a retrieval has to be performed).

Largest gap heuristic. In this context, a gap is the distance between any two adja-
cent items to be retrieved in an aisle, or the distance between the last item to be
retrieved in an aisle and the closest cross aisle. The picker goes to the front of the
side aisle, closest to the I/O port, including at least one item to be retrieved. Then the
picker traverses the aisle entirely, while the remaining side aisles are entered and left
once or twice, both times from the same side, depending on the largest gap of the
aisle.

Golden Fruit is an Honduran company manufacturing fruit juice. Last 17 Septem-
ber, a picker routing problem had to be solved at 10:30 a.m. in the warehouse located
in Puerto Lempira (see Figure 5.20). Travel times were assumed to be proportional
to distances. The routes provided by the S-shape and largest gap heuristics are shown
in Figures 5.21 and 5.22, respectively, and the least-cost route is illustrated in Fig-
ure 5.23.

5.4.3 Packing problems
Packing problems arise in warehouses when preparing the outgoing shipments. De-
pending on the characteristics of the products and on the transportation mode, items
or cartoons have to be mounted onto a pallet or inserted in a container, pallets have to
be loaded onto trucks, or containers have to be put on a ship or on a plane. All these
problems share a common mathematical structure as in both cases some вЂ˜objectsвЂ™
(named items in the following) have to packed into a set of bins. The objective is to
minimize the cost associated with using the bins, or simply to minimize the number

TLFeBOOK
186 DESIGNING AND OPERATING A WAREHOUSE

Figure 5.21 Picker route provided by the S-shape heuristic in the Golden Fruit warehouse.

Figure 5.22 Picker route provided by the largest gap heuristic in
the Golden Fruit warehouse.

of required bins. Constraints on the stability of the load are sometimes imposed. From
a mathematical point of view, packing problems are mostly NP-hard, so that in most
decision support systems heuristics are used.

Classiп¬Ѓcation. In some packing problems, not all physical characteristics of the
items have to be considered when packing. For instance, when loading high-density
goods onto a truck, items can be characterized just by their weight, without any
concern for their length, width and height. As a result, packing problems can be
classiп¬Ѓed according to the number of parameters needed to characterize an item.
вЂў One-dimensional packing problems often arise when dealing with high-density
items, in which case weight is binding.

TLFeBOOK
DESIGNING AND OPERATING A WAREHOUSE 187

Figure 5.23 Least cost picker route in the Golden Fruit warehouse.

items having the same height.
вЂў Three-dimensional packing problems occur when dealing with low-density
items, in which case volume is binding.
In the following, it is assumed, for the sake of simplicity, that items are rectangles
in two-dimensional problems, and that their sides must be parallel or perpendicular
to the sides of the bins in which they are loaded. Similarly, in three-dimensional
problems, the items are assumed to be parallelepipeds and their surfaces are parallel or
perpendicular to the surfaces of the bins in which they are loaded. These assumptions
are satisп¬Ѓed in most settings.
Packing problems are usually classiп¬Ѓed as off-line and on-line problems, depending
on whether the items to be loaded are all available or not when packing starts. In
the п¬Ѓrst case, item characteristics can be preprocessed (e.g. items can be sorted by
nondecreasing weights) in order to improve heuristic performance. A heuristic using
such preprocessing is said to be off-line, otherwise it is called on-line. Clearly, an
on-line heuristic can be used for solving an off-line problem, but an off-line heuristic
cannot be used for solving an on-line problem.

One-dimensional packing problems
The simplest one-dimensional packing problem is known as bin packing (1-BP) prob-
lem. It amounts to determining the least number of identical capacitated bins in which
a given set of weighted items can be accommodated. Let m be the number of items
to be loaded; n the number of available bins (or an upper bound on the number of
bins in an optimal solution); pi , i = 1, . . . , m, the weight of item i; qj the capacity
of bin j, j = 1, . . . , n. The problem can be modelled by means of binary variables
xij , i = 1, . . . , m, j = 1, . . . , n, each of them equal to 1 if item i is assigned to bin

TLFeBOOK
188 DESIGNING AND OPERATING A WAREHOUSE

j or 0 otherwise, and binary variables yj , j = 1, . . . , n, equal to 1 if bin j is used, 0
otherwise. The 1-BP problem can then be modelled as follows.

Minimize
n
yj (5.23)
j =1

subject to
n
xij = 1, i = 1, . . . , m, (5.24)
j =1
m
j = 1, . . . , n,
pi xij qyj , (5.25)
i=1
xij в€€ {0, 1}, i = 1, . . . , m, j = 1, . . . , n,
yj в€€ {0, 1}, j = 1, . . . , n.

The objective function (5.23) is the number of bins used. Constraints (5.24) state
that each item is allocated to exactly one bin. Constraints (5.25) guarantee that bin
capacities are not exceeded.
A lower bound z(I ) on the number of bins in any 1-BP feasible solution can be
easily obtained as
z(I ) = (p1 + p2 + В· В· В· + pm )/q . (5.26)

The lower bound (5.26) can be very poor if the average number of items per bin
is low (see Problem 5.8 for an improved lower bound). Such lower bounds can be
used in a branch-and-bound framework or to evaluate the performance of heuristic
methods. In the remainder of this section, four heuristics are illustrated. The п¬Ѓrst two
procedures (the п¬Ѓrst п¬Ѓt (FF) and the best п¬Ѓt (BF) algorithms) are on-line heuristics
while the others are off-line heuristics.

FF algorithm.

Step 0. Let S be the list of items, V the list of available bins and T the list of bins
already used. Initially, T is empty.

Step 1. Extract an item i from the top of list S and insert it into the п¬Ѓrst bin j в€€ T
having a residual capacity greater than or equal to pi . If no such bin exists, extract
from the top of list V a new bin k and put it at the bottom of T ; insert item i into
bin k.

Step 2. If S = в€…, STOP, all bins have been loaded. Then T is the list of bins used,
while V provides the list of bins unused. If S = в€…, go back to step 1.

TLFeBOOK
DESIGNING AND OPERATING A WAREHOUSE 189

BF algorithm.
Step 0. Let S be the list of items to be packed, V the list of available bins and T the
list of bins already used. Initially, T is empty.
Step 1. Extract an item i from the top of list S and insert it into the bin j в€€ T whose
residual capacity is greater than or equal to pi , and closer to pi . If no such bin
exists, extract a new bin k from the top of V and put it at the bottom of T ; insert
item i into bin k.
Step 2. If S = в€…, STOP, all the items have been loaded, T represents the list of the
bins used, while V is the list of bins unused. If S = в€…, go back to step 1.
The two procedures can both be implemented so that the computational complexity
is equal to O(m log m).
It is useful to characterize the performance ratios of such heuristics. Recall that the
performance ratio R H of a heuristic H is deп¬Ѓned as
zH (I )
R = sup в€—
H
,
z (I )
I

where I is a generic instance of the problem, zH (I ) is objective function value of the
solution provided by heuristic H for instance I , while zв€— (I ) represents the optimal
solution value for the same instance.
This means that
вЂў zH (I )/zв€— (I ) R H , в€ЂI ;
вЂў there are some instances I such that zH /zв€— (I ) is arbitrarily close to R H .
Unfortunately, the worst-case performance ratios of the FF and BF heuristics are not
known, but it has been proved that
R FF R BF
7 7
4.
and
4

The FF and BF algorithms can be easily transformed into off-line heuristics, by
preliminary sorting the items by nonincreasing weights, yielding the п¬Ѓrst п¬Ѓt decreasing
(FFD) and the best п¬Ѓt decreasing (BFD) algorithms. Their complexity is still equal to
O(m log m), while their performance ratios are
R FFD = R FBFD = 2 .
3

It can be proved that this is the minimum worst-case performance ratio that a
polynomial 1-BP heuristic can have.

Al Bahar is an Egyptian trucking company located in Alexandria which must plan
the shipment of 17 parcels, whose characteristics are reported in Table 5.14. For these
shipments the company can use a single van whose capacity is 600 kg. Applying the

TLFeBOOK
190 DESIGNING AND OPERATING A WAREHOUSE

Table 5.14 Weight of the parcels (in kilograms) in the Al Bahar problem.

Number of parcels Weight

4 252
3 228
3 180
3 140
4 120

Table 5.15 Sorted list of the parcels in the Al Bahar problem
(parcel weights are expressed in kilograms).

Parcel Weight Parcel Weight

1 252 10 180
2 252 11 140
3 252 12 140
4 252 13 140
5 228 14 120
6 228 15 120
7 228 16 120
8 180 17 120
9 180

BFD heuristic, the parcels are sorted by nonincreasing weights (see Table 5.15) and
the solution reported in Table 5.16 is obtained. The number of trips is six. The lower
bound on the number of trips given by Equation (5.26) is 3132/600 = 6. Hence,
the BFD heuristic solution is optimal.

Two-dimensional packing problems
The simplest two-dimensional packing problem (referred to as the 2-BP problem in
the following) consists of determining the least number of identical rectangular bins
in which a given set of rectangular items can be accommodated. It is also assumed
that no item rotation is allowed. Let L and W be the length and the width of a bin,
respectively, and let li and wi , i = 1, . . . , m, be the length and the width of item i.
A lower bound z(I ) on the number of bins in any feasible solution is
z(I ) = (l1 w1 + l2 w2 + В· В· В· + lm wm )/LW .
Most heuristics for the 2-BP problem are based on the idea of forming layers of
items inside the bins. Each layer has a width W , and a length equal to that of its

TLFeBOOK
DESIGNING AND OPERATING A WAREHOUSE 191

Table 5.16 Parcel-to-trip allocation in the optimal solution of the Al Bahar problem
(parcel weights are expressed in kilograms).

Parcel Weight Trip Parcel Weight Trip

1 252 1 10 180 5
2 252 1 11 140 3
3 252 2 12 140 5
4 252 2 13 140 5
5 228 3 14 120 5
6 228 3 15 120 6
7 228 4 16 120 6
8 180 4 17 120 6
9 180 4

Layer 2

Layer 1

L

W

Figure 5.24 Layers of items inside a bin.

longest item. All the items of a layer are located on its bottom, which corresponds to
the level of the longest item of the previous layer (see Figure 5.24).
Here we illustrate two off-line heuristics, named п¬Ѓnite п¬Ѓrst п¬Ѓt (FFF) and п¬Ѓnite best
п¬Ѓt (FBF) heuristics.

FFF algorithm.
Step 0. Let S be the list of items, sorted by nonincreasing lengths, V the list of bins
and T the list of bins used. Initially, T is empty.
Step 1. Extract an item i from the top of S and insert it into the leftmost position
of the п¬Ѓrst layer (which can accommodate it) of the п¬Ѓrst bin j в€€ T . If no such
layer exists, create a new one in the п¬Ѓrst bin of T (which can accommodate it) and
introduce item i in the leftmost position of the layer. If there is no bin of T which

TLFeBOOK
192 DESIGNING AND OPERATING A WAREHOUSE

can accommodate the layer, extract from the top of V a new bin k and put it at the
bottom of T , load item i into the leftmost position at the bottom of bin k.
Step 2. If S = в€…, STOP, all the item have been loaded. Then, T represents the list of
bins used, while V provides the list of the unused bins. If S = в€…, go back to step 1.

FBF algorithm.
Step 0. Let S be the list of items, sorted by nonincreasing lengths, V the list of bins
and T the list of bins used. Initially, T is empty.
Step 1. Extract an item i from the top of S and insert it into the leftmost position
of the layer of a bin j в€€ T whose residual width is greater than or equal to, and
closer to, item width. If no such layer exists, create a new one in the bin of T whose
residual length is greater than or equal to, and closer to, the length of item i. Then,
introduce item i in the leftmost position of the layer. If there is no bin of T which
can accommodate the layer, extract from the top of V a new bin k and put it at the
bottom of T , load item i into the leftmost position at the bottom of bin k.
Step 2. If S = в€…, STOP, all the item have been loaded. Then, T represents the list of
bins used, while V provides the list of the unused bins. If S = в€…, go back to step 1.
Such layer heuristics have a low computational complexity, since the effort for
selecting the layer where an item has to be inserted is quite small. However, they can
turn out to be inefп¬Ѓcient if the average number of items per bin is relatively small. In
such a case, the following bottom left (BL) algorithm usually provides better solutions.

BL algorithm.
Step 0. Let S be the list of items, sorted by nonincreasing lengths, V the list of bins
and T the list of bins used. Initially, T is empty.
Step 1. Extract an item i from the top of list S and insert it into the leftmost position
at the bottom of the п¬Ѓrst bin j в€€ T able to accommodate it. If no such bin exists,
extract a new bin k from the top of V , and put it at the bottom of T ; load item i
into the leftmost position at the bottom of bin k.
Step 2. If S = в€…, STOP, all the items have been loaded, T represents the list of bins
used, while V provides the list of bins unused. If S = в€…, go back to step 1.

Kumi is a South Korean company manufacturing customized ofп¬Ѓce furniture in
Pusan. Outgoing products for overseas customers are usually loaded into containers
ISO 40, whose characteristics are reported in Table 5.17. Once packaged, parcels are
2 or 1 m high. They are mounted on wooden pallets so that they cannot be rotated at
loading time. The list of parcels shipped last 14 May is reported in Table 5.18. Parcels
that are 1 m high are coupled in order to form six pairs of (1 Г— 1) m2 parcels and п¬Ѓve

TLFeBOOK
DESIGNING AND OPERATING A WAREHOUSE 193

Table 5.17 Characteristics of ISO 40 container.

Length Width Height Capacity Capacity
(m3 )
(m) (m) (m) (kg)

12.069 2.373 2.405 68.800 26.630

Table 5.18 Parcels shipped by Kumi company.

Length Width Height
Quantity (m) (m) (m)

6 1.50 1.50 2.00
5 1.20 1.70 2.00
13 1.00 1.00 1.00
11 0.80 0.50 1.00

2 2

W

L

2 2 2
2 2 2
W

2 2 2 2

L

Figure 5.25 Parcels allocated to the two containers shipped by Kumi company
(2 indicates two overlapped parcels).

pairs of (0.8 Г— 0.5) m2 parcels. Then, each such a pair is considered as a single item.
Applying the FBF algorithm, the solution reported in Figure 5.25 is obtained.

Three-dimensional packing problems
The simplest three-dimensional packing problem (referred to as the 3-BP problem in
the following) consists of determining the least number of identical parallelepipedic

TLFeBOOK
194 DESIGNING AND OPERATING A WAREHOUSE

Table 5.19 Parcels loaded at McMillan company.

Length Width Height Volume Weight
(m3 )
Type Quantity (m) (m) (m) (kg)

1 2 2.50 0.75 1.30 2.4375 75.00
2 4 2.10 1.00 0.95 1.9950 68.00
3 7 2.00 0.65 1.40 1.8200 65.50
4 4 2.70 0.70 0.95 1.7900 63.00
5 3 1.40 1.50 0.80 1.6800 61.50

bins in which a given set of parallelepipedic items can be accommodated. It is also
assumed that no item rotation is allowed. Let L, W and H be the length, width and
height of a bin, respectively, and let li , wi and hi , i = 1, . . . , m, be the length, width
and height of item i.
A lower bound z(I ) on the number of bins is

z(I ) = l1 w1 h1 + l2 w2 h2 + В· В· В· + lm wm hm )/LW H . (5.27)

The simplest heuristics for 3-BP problems insert items sequentially into layers
parallel to some bin surfaces (e.g. to W Г— H surfaces). In the following a heuristics
based on this principle is illustrated.

3-BP-L algorithm.
Step 0. Let S be the list of items.
Step 1. Solve the 2-BP problem associated with m items characterized by wi , hi , i =
1, . . . , m, and bins characterized by W and H . Let k be the number of bidimensional
bins used (referred to as sections in the following). The length of each section is
equal to the length of the largest item loaded into it.
Step 2. Solve the 1-BP problem associated with the k sections, each of which has a
weight equal to its length, while bins have a capacity equal to L.
If the items are all available when bin loading starts, it can be useful to sort list S
by nonincreasing values of the volume. However, unlike one-dimensional problems,
more complex procedures are usually needed to improve solution quality.

McMillan company is a motor carrier headquartered in Bristol (Great Britain).
The п¬Ѓrm has recently semi-automatized the procedure for allocating outgoing parcels
to vehicles, using a decision support system. This software tool uses the 3-BP-L
algorithm as a basic heuristic, and then applies a local search procedure. Last 26
January the parcels to be loaded were those reported in Table 5.19. The characteristics
of the vehicles are indicated in Table 5.20. The parcels are mounted on pallets and

TLFeBOOK
DESIGNING AND OPERATING A WAREHOUSE 195

Table 5.20 Characteristics of the vehicles in the McMillan problem.

Length Width Height Capacity Capacity
(m3 )
(m) (m) (m) (kg)

6.50 2.40 1.80 28.08 12.30

4 4
4
3
1
3 H
2 2 2
2
1 3

W W W

3 3 H
5
5 5
3 4 3

W W W

Figure 5.26 Sections generated at the end of Step 1 of the 3-BP-L heuristic in
 << стр. 8(всего 15)СОДЕРЖАНИЕ >>