Routing order pickers in a warehouse

Kees Jan Roodbergen

Contents

1 Introduction
2 Warehouse layout
3 S-shape heuristic
4 Largest Gap heuristic
5 Combined heuristic
6 Aisle-by-aisle heuristic
7 Optimal algorithm
8 References
9 Enter the interactive warehouse

1 Introduction

Order picking is the process by which products are retrieved from specified storage locations on the basis of customer orders. In general, the order picking process is the most laborious of all warehouse processes. It may consume as much as 60% of all labor activities in the warehouse. Especially in distribution environments, the pick process is usually carried out under time constraints. Orders tend, more and more, to arrive late and have to be shipped the same day at pre-fixed departure times per area of destination. This leads to peak loadings and an on-going pressure to carry out the order picking process as efficiently as possible.

One way to achieve savings on order pickers and equipment is by optimizing order picking routes. Given that the order picker has to collect a number of products in specified quantities at known locations, in what sequence should the order picker visit these locations in order to minimize the distance traveled?

The basic warehouse layout is one with parallel aisles, a central depot and two possibilities for changing aisles, at the front and at the rear of the warehouse. For this type of warehouses, various routing heuristics are known (see e.g. Hall, 1993). An efficient algorithm to find shortest order picking routes has been developed by Ratliff and Rosenthal (1983).

In practice, we often encounter warehouses that do not comply with this basic layout. In many warehouses it is possible not only to change aisles at the front and rear of the warehouse, but also at one or more positions in between. In this type of warehouse, consisting of two or more blocks of aisles, existing routing strategies can not be used.

On this internet site we demonstrate a number of heuristics for routing order pickers in a warehouse with any number of blocks. Two of these methods are based on existing heuristics for the basic layout. One is specially designed for the general layout. Furthermore an algorithm is used that can obtain shortest routes in warehouse consisting of one or two blocks.

On this page we describe a number of methods to route order pickers in a warehouse. For more information, e.g. on the implications for the layout of the warehouse, please refer to the paper "Routing order pickers in a warehouse with multiple cross aisles" of Kees Jan Roodbergen and René de Koster. For details see below.

2 Warehouse layout

The warehouse consists of a number of blocks, each consisting of a number of parallel aisles. The items are stored at both sides of the aisles. With main aisle we refer to an aisle between the front and rear end of the warehouse, going through all blocks. The front aisle and the rear aisle are located entirely at respectively the front and the rear of the warehouse. These two aisles do not contain items, but can be used for changing aisles. Between each pair of blocks, there is a cross aisle which can be used to go from one aisle to the next or from one block to the next.

Order pickers are assumed to be able to traverse the aisles in both directions and to change direction within the aisles. The aisles are narrow enough to allow picking from both sides of the aisle without changing position. Each order consists of a number of items that are usually spread out over a number of aisles. We assume that the items of an order can be picked in a single route. Aisle changes are possible at the front end, the rear end and in any of the cross aisles. Picked orders have to be deposited at the depot, where the picker also receives the instructions for the next route. The depot is located in the front aisle at the head of the first main aisle. The figure on the right gives an example of such a warehouse.

On this site we use four different types of routing. Two heuristics are based on well known heuristics for the basic layout: S-shape and Largest Gap. Furthermore, a hybrid strategy is introduced, combining aspects from both S-shape and Largest Gap. The fourth routing method, consists of finding a shortest route. Each method is described below and illustrated in a figure.


3 S-shape heuristic

Basically, any aisle containing at least one item is traversed through the entire length. Aisles where nothing has to be picked are skipped. In the following more elaborate description of the heuristic, numbers between brackets correspond to the numbers in the figure on the right.

The order picking route starts at the depot. It goes to the front of the main aisle closest to the depot, that contains at least one item (1). This main aisle is traversed up to and including the block farthest from the depot, that contains at least one item (2).

If the current block contains at least one item: Go to the left most aisle containing items or go to the right most aisle containing items, whichever is the closest (3); go from one aisle to the next and traverse any aisle containing items entirely; after picking the last item, return to the front of the block (4). If this block contains no items: Traverse the aisle of this block, that is closest to the current position. Repeat this procedure for all blocks until the block closest to the depot has been considered (5). Finally, return to the depot.


4 Largest Gap heuristic

A route resulting from this heuristic is depicted in the figure on the right. Numbers in this figure are explained below.

Similar to the S-shape heuristic, the order picking route starts at the depot; it goes to the front of the main aisle closest to the depot, that contains at least one item; traverses this main aisle up to and including the block farthest from the depot that contains at least one item (1).

On traversing the cross aisle (which is actually the rear aisle in the example of Figure 3), each aisle is entered as far as the ‘largest gap’ and left from the same side that it was entered (2). A gap represents the distance between any two adjacent items, or between a cross aisle and the nearest item. Thus, the largest gap is the part of the aisle that is not traversed.

The last aisle of the block is traversed entirely, by which we arrive in the next cross aisle (3). This cross aisle is traversed, while visiting the aisles of the blocks on both sides of the cross aisle up to the largest gap. First the aisles on one side of the cross aisle are visited (4) and thereafter the aisles on the other side (5). One aisle is again traversed entirely to reach the next cross aisle (6). This may be either the left or the right most aisle containing items, depending on which of the two gives the shortest travel distance within the cross aisle.

This process is repeated for all blocks containing items. If a block does not contain items, then the aisle of this block, that is closest to the current position is traversed entirely. After considering the last block, return to the depot (7).


5 Combined heuristic

This heuristic creates order picking routes that visit every aisle, that contains items, exactly once. The aisles of each block are visited sequentially, either from left to right or from right to left.

Similar to the S-shape and largest gap heuristics, the order picking route starts at the depot; it goes to the front of the main aisle closest to the depot, that contains at least one item; traverses this main aisle up to and including the block farthest from the depot that contains at least one item.

For each block we perform a small dynamic programming algorithm. In order to use the concept of dynamic programming, we have to define the potential states, the possible transitions between states, and the costs involved in such a transition. We define two states:

  1. the orderpicker is at the front of the block
  2. the orderpicker is at the rear of the block.

We define 6 transitions:

  1. go from the current aisle to the next aisle along the front of the block and traverse this aisle entirely, ending up at the rear of the block,
  2. go from the current aisle to the next aisle along the rear of the block and traverse this aisle entirely, ending up at the front of the block,
  3. go from the current aisle to the next along the front of the block and do not enter this aisle at all,
  4. go from the current aisle to the next along the rear of the block and do not enter this aisle at all,
  5. go from the current aisle to the next aisle along the front of the block and traverse this aisle up to the item farthest from the front and return to the front,
  6. go from the current aisle to the next aisle along the rear of the block and traverse this aisle up to the item farthest from the rear and return to the rear.

Clearly, transitions (3) and (4) are only allowed if the aisle does not contain any items. The cost of each transition is equal to the travel time needed for the distance in the transition.

The following figure depicts the 6 transitions. The current aisle is aisle j, the next aisle is aisle j+1. The rear end of aisle j is denoted by aj and the front end by bj.

Six transitions used for the combined heuristic.

We apply the dynamic programming algorithm to each block separately. The connection between the blocks is made in such a way that the distance traveled in the cross aisles in minimized. If the block closest to the depot has been evaluated, the order picker returns to the depot. A route resulting from this algorithm is depicted above on the right. For a more elaborate description of this heuristic, see Roodbergen and De Koster (2001a).

6 Aisle-by-aisle heuristic

This heuristic is described in Vaughan and Petersen (1999). Basically, every main aisle is visited once. The order pickers starts at the depot and goes to the left most aisle containing items. All items in this main aisle are picked and a cross aisle is chosen to proceed to the next main aisle. Again all items in this main aisle are picked and the order pickers proceeds to the next main aisle. The aisle-by-aisle heuristic determines which cross aisles to use to go from one aisle to the next in such a way that the distances traveled are minimized.

7 Optimal algorithm

For the basic warehouse layout we can find shortest order picking routes with the algorithm of Ratliff and Rosenthal (1983). However, adding just one cross aisle to this basic layout, complicates the solution procedure significantly. In Roodbergen and De Koster (2001b) an algorithm is described to find shortest order picking routes in a warehouse with three possibilities for changing aisles: at the front, at the rear and somewhere in between. Following the lines of Ratliff and Rosenthal (1983), this algorithm uses dynamic programming to solve the problem. From the paper it is apparent that any extension to more cross aisles is non-trivial and the number of equivalence classes and possible transitions increases rapidly.

Therefore, on this internet site it is only possible to calculate and display shortest order picking routes for warehouses consisting of one or two blocks.

Of course, in theory it is possible to calculate optimal routes for warehouses with any number of block by using a branch-and-bound algorithm. The route in the figure on the right is found this way (see also Roodbergen and De Koster, 2001b). However, for this site such an algorithm is too complex.


8 References

Hall, R.W. (1993), Distance approximations for routing manual pickers in a warehouse, IIE Transactions 25, 76-87.

Ratliff, H.D., and Rosenthal, A.S. (1983), Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem, Operations Research 31(3), 507-521.

Roodbergen, K.J. and De Koster, R. (2001a), Routing methods for warehouses with multiple cross aisles, International Journal of Production Research 39(9), 1865-1883.

Roodbergen, K.J. and De Koster, R. (2001b), Routing order pickers in a warehouse with a middle aisle, European Journal of Operational Research 133(1), 32-43.

Vaughan, T.S. and Petersen, C.G. (1999), The effect of warehouse cross aisles on order picking efficiency, International Journal of Production Research 37(4), 881-897.

9 Enter the interactive warehouse

Go to the Interactive Warehouse
 
Or read the introduction
 
 
 
 
The Interactive Warehouse is created by Kees Jan Roodbergen.
contact / feedback.