2. CLUMPY ORDERS AND THE NEAREST-END-POINT HEURISTIC

For an order of n ≥ 2 items, let l be the length of arc A, the longest arc between successive items on the circumference of the carousel (may not be unique), and C be the complementary arc, with length r = 1 − l. The entire order lies within C, including one item at each end. For n = 1, we define C as the point where this item is located and r = 0. As the spacing between the items in C is smaller than l, we call C a clump and say that orders are clumpy.

By our definition, all orders are clumpy; this is just a way of conceptualizing the problem. In a stochastic setting, we believe that this approach is useful when the items in an order tend to be closer together than

would predict.

If the items are located as points on a linear segment (straight line) rather than on the circumference of a circle, the optimal policy (for minimizing travel time) is obvious: Call the points that are farthest apart the two end points and suppose that the picker starts between them. The picker should first go to the nearest end point, then switch direction and go to the farthest end point. This suggests the following heuristic, where now an end point is an end point of C.

Nearest-End-Point Heuristic (NEPH): When starting in A, the picker sweeps in the direction of the nearest end point. When starting in C, the picker moves to the nearest end point, then switches direction and moves to the farthest end point.

Notice that when the picker starts in A, NEPH and NIH are identical. They may be quite different when the picker starts in C. We now present conditions where NEPH is optimal.

Theorem 2.1: When the picker starts in A, NEPH is optimal. When the picker starts in C and r ≤ 1/2, NEPH is optimal.

Proof: When the picker starts in A, it is easily shown that switching direction (once) cannot be optimal and, hence, NEPH is optimal. Suppose the picker starts in C. For n = 2, NEPH is optimal. Adding points (items) to an order cannot decrease the optimal travel time. For fixed r and picker location, adding points within C does not change the travel time under NEPH. Hence, NEPH is optimal for n > 2 as well. █

When the picker starts in C, it is easy to show that NEPH may not be optimal when r is large because traversing A may reduce the travel time. Here is an example that shows this can happen for any r > 1/2.

Example 2.2: Locate three items at 0, 1/2 − 2ε, and 1/2 + ε, where ε > 0. C is arc[0, 1/2 + ε] and r = 1/2 + ε. Suppose that the picker starts at 14;. NEPH gives travel time 3/4 + ε, which is longer than 3/4, the travel time by moving toward 1/2 + ε and sweeping.

This is just an example. For r > 1/2, NEPH may be optimal, depending on the initial location of the picker and the location of points within C. In particular, suppose that the picker is within s of its nearest end point. Then, NEPH is optimal if r + 2s ≤ 1. When the points are closely spaced and 1/2 < r < 2/3, NEPH will be optimal or nearly so.

2.1. Stochastic Performance of the Nearest-End-Point Heuristic

Let T^E be the (total) travel time (or distance) by the picker to pick an order under NEPH. Whether the picker starts in C or A, we write T^E as the sum

where Z^E is the time to travel to the nearest end point of C, and once there, r is the time to travel to the other end point. Notice that for fixed r, T^E is independent of the number and the location of points within C.

We now make assumption

, for the random picker: The location of the picker is uniformly distributed over the circumference and is independent of the location of the clump. The rationale for

is that when orders are diverse, the location of the picker when finished with one order is unrelated to the location of the clump for the next. This assumption is implied by the formulation of the queuing model in Section 4 and is much weaker than

.

Let U(a, b) denote a uniform distribution on interval (a, b) and the symbol ∼ mean “distributed as.” Under

, the picker starts in C with probability r, and, given that this occurs, it is readily shown that Z^E ∼ U(0, r/2). (Split the arc C into two arcs of equal length and condition on the picker starting in either one.) Similarly, the picker starts in A with probability 1 − r, and, given that this occurs, Z^E ∼ U(0, (1 − r)/2). Thus, under

, the distribution of Z^E is a mixture of uniforms:

and from Eq. (1), so is the distribution of T^E. The mean and (after some algebra) the variance of T^E readily follow from Eqs. (1) and (2):

3. NEAREST-ITEM HEURISTIC FOR CLUMPY ORDERS

Example 2.2 shows that NEPH may not be optimal for clumpy orders when r > 1/2. NIH is shown to perform well under

(Litvak and Adan [5], Litvak et al. [6]). A natural question is whether NIH performs well when orders are clumpy. A stochastic analysis of NIH for clumpy orders requires a model of how items within a clump are dispersed. We will make an assumption much like

, but with locations restricted to the clump.

When r ≤ 1/2, the picker will not traverse A under either NEPH (which is optimal) or NIH; the treatment of this case is similar to a linear segment of length r.

3.1. Stochastic Performance of the Nearest-Item Heuristic on a Unit Segment

Consider an order of n ≥ 2 items on a unit interval such that there is one item at each end point. We assume that the locations of the remaining n − 2 items and the initial location of the picker are i.i.d. uniform on this interval. Thus, there are n − 1 “inside” points, and our analysis will be based on the corresponding order statistics.

Label all the points from left to right as 0,1,…, n, where points 0 and n are the two end points. Let V_i be the distance between points i and i − 1, i = 1,…, n. It is well known that (V₁,…,V_n) has the same distribution as (X₁ /S_n,…, X_n /S_n), where X₁,…, X_n are i.i.d. exponential random variables and

(Karlin and Taylor [3, p.105]). For

, Litvak et al. [6] show that

We will use Eq. (4) to find properties of T_n^I, the total time to pick an order of n items under NIH. We write T_n^I as

where Z_n^I is the time for the picker to pick the first of the end points and 1 is the time to travel from the first picked to the other end point. In the limit when n → ∞, we use T_∞^I and Z_∞^I for T_n^I and Z_n^I, respectively.

Let Y_n be the index of the initial location of the picker before any move, Y_n ∈ {1,…, n − 1}. As these locations are equally likely, we write

To find E(Z_n^I|Y = 1), let Z_{j, n}^I be the additional time to travel to one of the end points given that the picker is at point j and any items at points 1,…, j have been picked; Z_{n, n}^I = 0. The indices of X_(·) are labeled according to their order of being considered by the heuristic. For j = 1,…, n − 1,

Applying Eq. (6) recursively and making use of Eq. (4) along the way, we have

E(Z_n^I|Y_n = y) for y > 1 may be found by conditioning, but the set of equations does not give a neat analytical expression. From these quantities, one can compute E(T_n^I). For example, E(T₂^I) = 1.25, E(T₃^I) = 1.2917, E(T₄^I) = 1.3229, and E(T₅^I) = 1.3466.

For large n, let m_n be the positive integer such that the probability of switching direction on the m_nth move, P(S_mn < X_mn+1) = 1/2^m_n, is small enough to make the total effect of any switch after m_n moves negligible. As n → ∞, the total time to visit m_n points is insignificantly small, and after these m_n moves, the picker is equally likely to be moving left or right from any initial location. Thus, as n → ∞, Z_∞^I → τ ∼ U(0,1); E(T_∞^I) = E(τ) + 1 = 1.5 and

.

To assess the performance of NIH, we compare E(T_n^I) with (optimal) E(T^E) on this line segment, where it is easily shown that E(T^E) = 1.25. Let the overshoot be the percentage by which E(T_n^I) exceeds the optimal value. For n = 2, NIH is the same as NEPH, and the overshoot is zero. The overshoot is as follows: For n = 3, it is 3.33%; for n = 4, it is 5.83%; for n = 5, it is 7.73%; and in the limit as n → ∞, it is 20%.

3.2. The Limiting Performance of NIH on Clumpy Orders

Consider a clumpy order with r ≤ 1/2. We now assume what we call

: the locations of the n − 2 items within the clump are i.i.d. ∼ uniform on C, an arc of length r. We also assume

. Redefine T_∞^I and Z_∞^I from a unit interval to arc C. Then, T_∞^I = Z_∞^I + r. Given that the picker starts in A, an event with probability 1 − r, Z_∞^I ∼ U(0,(1 − r)/2), the same as under NEPH. Given that picker starts in C, an event with probability r, we have a rescaling of the analysis of NIH on a unit segment and, hence, Z_∞^I ∼ U(0, r). Combining, we have

where

After some algebra, we get

Unlike the analysis of NIH under

(Litvak and Adan [5], Litvak et al. [6]), performance does not approach optimality as n increases, but gets worse, as the picker has a higher probability, approaching 1/2, of hitting the farthest end point first. The direction of the nearest point provides no information about the direction of the nearest end point. Under the assumption that the points within C are equally spaced (not random), rather than i.i.d. uniform, the distribution in Eq. (8) is exact.

4. QUEUING ANALYSIS FOR CLUMPY ORDERS

We now model the carousel under a set of assumptions we call

: The carousel operates as a single-server (picker) queue, where arriving orders are Poisson at rate λ. Orders are served FIFO and properties of orders, from order to order, are i.i.d. For order j, these properties include the following: Clump location (measured from either end point) is uniformly distributed on the circumference, clump arc length, R_j, and the number of items in the order, N_j, have some joint distribution. To analyze the queuing model under policies such as NIH, the distribution of points within the clump would also have to be specified.

Under any of the policies we have considered, let T_j be the travel time to pick order j. The service time S_j of this order is S_j = T_j when picking times are negligible. (More generally, we can write S_j = T_j + aN_j, where a is the time to pick an individual order; our approach still applies, but we omit this complication in the following.) Under

, the picker satisfies assumption

and the service times S_j are i.i.d. Thus, the queuing model is an M/G/1 queue. It is not necessary to assume the much stronger

to have this simple queue. We now present some results for this model. For them and additional properties of the M/G/1 queue, see Wolff [9, Chap.8].

Let delay D_j be the time from the arrival of order j to when service (travel time) on that order begins, let S = T be a generic service time, and let R be a generic arc length. When ρ ≡ λE(S) < 1, all customers are served, and the long-run average delay d is given by

Under NEPH, the conditional distribution of (T |R = r) is given by Eqs. (1) and (2), and the conditional mean and variance is given by Eq. (3). Thus, moments of S may be found from moments of R. This is clearly appropriate when P(R ≤ 1/2) = 1 and is also appropriate when the points within C are closely spaced and R_j rarely exceed 2/3.

Analytic expressions for the moments of S are not required to apply Eq. (10). They can be estimated easily by working out optimal travel times and service times (whether or not picking times are negligible) for a sample of orders.

The simplicity of this model is a consequence not only of

but also of the FIFO assumption. Particularly when most of the R_j are small, there are advantages to abandoning FIFO. Is it not foolish to pass over an order that could be picked, on the way to picking an order that arrived earlier? The nearest-order heuristic (NOH) (rather than nearest item within an order) deserves consideration and was analyzed in Krouse and Schmidt [4] under the special case where an order consists of a single item and picking time is not negligible. We are currently investigating NOH and other alternatives to FIFO.

5. LARGE r AND THE MODIFIED NEAREST-END-POINT HEURISTIC

For r ≤ 1/2, NEPH is optimal and there is no reason to consider any other way of picking orders. For the rest of this section, we assume

and

.

Now, consider the range 1/2 < r ≤ 2/3. Suppose that the picker starts in C. NEPH will be asymptotically optimal as the number of items n → ∞ because, on reaching the nearest end point, the picker will find that switching direction is better than traversing A. Under NIH, the picker may (foolishly) reach the farthest end point first and may find that traversing A is better than switching direction. Thus, Eqs. (8) and (9) are not valid in this range. Nevertheless, we expect NEPH to be better than NIH in this range when n is large.

Now, consider the range r > 2/3. Suppose the picker starts in C. Asymptotically, NEPH will not be optimal when the picker starts close to the middle of C because on reaching the nearest end point, traversing A will be better than switching direction.

We now propose a simple modification of NEPH that performs well for large r and n.

Modified Nearest-End-Point Heuristic (MNEPH): MNEPH is the same as NEPH, except in one situation: Under MNEPH, and when r > 2/3 and the picker starts in C, the picker sweeps in the direction of the nearest item.

For the rest of this section, assume r > 2/3. Let T_n^M be the travel time to pick an order of n items under MNEPH.

For ease of reference, we use the same symbols A and C to denote the events that the picker starts in arcs A and C, respectively. Given A, the time to pick the first of the end points is ∼U(0,(1 − r)/2), and the remaining time is r:

Given C, the picker starts in some interval between two items. Then, T_n^M = 1 − L, where L is the longer of the distances between the picker and the two neighboring items. The analysis is related to the shortest-distance heuristic (SDH) (Litvak et al. [6], Rouwenhorst et al. [7]); for SDH, they find the mean and variance of the time to pick n items to be 1 − (3/2(n + 1)) and (5n − 4)/4(n + 1)²(n + 2), respectively.

For our case, arc C is of length r and a clumpy order of n ≥ 2 items corresponds to an order of n − 1 items for SDH. Hence,

Unconditioning, we have

These results may be used in the queuing model in Section 4.

A further modification when r > 2/3 and the picker starts in C is as follows: Use the NEPH when the picker starts within 1 − r of an end point and have the picker sweep in the direction of the nearest item when it starts closer to the middle of C.

6. CONCLUDING REMARKS

We have reformulated the order-picking problem in terms of the clumpiness of orders, introduced the elementary NEPH to pick them, and obtained the travel time distribution under this heuristic and much weaker stochastic assumptions than in the literature. We have obtained conditions for NEPH to be optimal and discussed other circumstances where we expect it to perform well. Under an alternative to

, we have shown that NIH performs poorly, and believe that one should be wary of using it when

does not hold.

Our queuing analysis of order delays holds under much weaker stochastic assumptions than in the literature and under NEPH, NIH, or any other rule for picking orders. As done in Rouwenhorst et al. [7], we assumed FIFO, which greatly simplifies the analysis. As explained at the end of Section 4, there are alternatives to FIFO that we expect to perform much better. They are under investigation.