Routing strategies

A routing strategy is a strategy by which the route through the warehouse is determined. A route is a path in which you pass all items of an order. If you want to reduce the orderpicking costs to a minimum, the route have to be as short as possible.
There are several routing strategies, but not all of them are suited for any situation. We have decided to take the following four routing strategies into this page:

The S-Shape routing strategy

The S-shape strategy is also called the Traversal strategy. This strategy leads to a route in which the aisles, that are to be visited, are totally traversed. Aisles where nothing has to be picked are skipped. Thus aisles are visited in the shape of an S. The picker thus enters an aisle from one end and leaves the aisle from the other end, starting at the left side of the warehouse. After picking the last item, the order picker returns to the front end of the aisle. This strategy is used frequently, because it is very simple to use and to understand.

Below, you can see how the selected items are to be picked according to the S-shape heuristic in a warehouse with a central depot and no cross aisles. The order picker starts at the depot and then enters the left most aisle containing items or the right most aisle containing items, whichever is the closest. The picker goes from one item to another by crossing the (item containing) aisles entirely. Finally, he returns to the depot.

The Largest Gap routing strategy

In the Largest Gap strategy a picker enters an aisle as far as the largest gap within an aisle. A gap represents the distance between any two adjacent picks, between the first pick and the front aisle, or between the last pick and the back aisle. The largest gap is the part of the aisle that is not visited by the order picker. If the largest gap is between two adjacent picks, the picker performs a return route from both ends of the aisle. Otherwise, a return route from either the front or back aisle is used. The largest gap within an aisle is therefore the portion of the aisle that the picker does not traverse. The back aisle can only be accessed through either the first or last aisle. The Largest Gap heuristic is especially useful when the additional time to change aisles is short and the number of picks per aisle is low.

Below, you can see how the selected items are to be picked according to the Largest Gap heuristic in a warehouse with a central depot and no cross aisles. Similar to the S-shape heuristic, the order picker starts at the depot and goes to the front of the aisle, closest to the depot, that contains at least one item. Thus, this is the most left or most right item containing aisle. This aisle is traversed entirely after which each aisle at the rear end of the warehouse is entered as far as the 'largest gap' and left from the same side that it was entered. The last aisle is traversed entirely to the front. Now, the aisles are entered from the front end as far as the 'largest gap'. If all items are picked, the picker returns to the depot.

The Combined routing strategy

In this routing strategy, developed by Roodbergen and De Koster (1998), every time all items of one aisle are picked, the question is posed whether to go to the rear end of an aisle or to return to the front end. These two alternatives have to be compared with each other after which the one, resulting in the shortest route, is chosen. Thus, after leaving an aisle (at the front or at the rear end), a choice between the two alternatives ending at the back and a choice between the two alternatives ending at the front has to be made. This means there are always two possible routes to follow. If the last item is picked (now, the route ends at the front end) a final choice between the two alternatives is made. As you can see in the picture below the items are picked aisle by aisle.

The Optimal routing strategy

The optimal routing strategy can calculate a shortest route, regardless of layout or location of the items. Optimal routes will typically look like a mixture of S-Shape and Largest Gap. Ratliff and Rosenthal (1983) developed an optimal procedure for routing workers in a rectangular warehouse without cross aisles. Hall (1993) noted that heuristic strategies might provide near optimal routes and avoid the confusion inherent in optimal solutions. The majority of orderpicking operations uses heuristic routing strategies. The one advantage to the use of heuristics is that they are easy to understand and form routes that are fairly consistent in nature, which is why heuristic strategies are commonly used in practice.
Below, you can see how the selected items are to be picked according to the optimal routing strategy in a warehouse with a central depot and no cross aisles. 
This site uses an optimal routing method that can find shortest orderpicking routes in warehouses with 0 and 1 cross aisles.

Routing strategies and cross aisles

In the following part of this page an explanation of these strategies on how to use them if the warehouse is divided in blocks by cross aisles is given. The strategies are explained in the same order as before:

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 aislewhich 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.

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.

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).

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 a_j and the front end by b_j.

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 (1998).

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 (1998) 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. However, for this site such an algorithm is too complex.