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

loading (see Section 5.4.3).

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.

• Two-dimensional packing problems usually arise when loading a pallet with

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