Batching strategies

There are a number of different ways to collect your orders. The simplest way is to collect one order at a time. But if there are many small orders, it can be more efficient to pick by article (pick-and-sort). There is also an intermediate form, in which several orders are picked together in one route and sorted by the picker (sort-while-pick). Batching is the process of combining one or more (customer)orders into one or more pick orders. All orders that are to be collected are joined together, after which they are sorted into separate pick orders. This means that in one route through the warehouse several (parts of) orders are picked. During the picking process, the items are sorted into the original customer orders.
In practice, all three ways of orderpicking can be used, but since most literature is focused on the batching of complete orders, this site concentrates on this batching form and refrains from the option where all orders are collected by article.
 
There are several ways to determine which orders have to be grouped together by using batching heuristics, but not all of these are equally qualified for every situation. An important restriction is not to exceed the maximum capacity of the orderpicking truck. If, for example, orders 1, 5 and 6 and orders 2, 3 and 4 have to be batched (see figure below), but the maximum capacity of the truck is exceeded by the first batch, then another combination of orders has to be found. Although the best solution to this batching problem can (among other things) be found by trying all possible combinations and then start picking the one with the shortest total travel time, in practice often a heuristic is used, because this is less time consuming to calculate. In order to facilitate the decision making process of batching, the customer orders into one or more batches, various heuristics have been developed. In this site only a selection of three heuristics, which have proved to be most suitable, are used.

EXAMPLE

This illustration shows a top view of a warehouse with seven different orders, each of the orders consists of a number of items. Some compartments in the figure contain a number, this means an item of the order concerned is located there. This example warehouse consists of 7 aisles and has 15 locations with a width of 1 meter at each side of the aisles. The aisle width is 4 meters. The maximum capacity of an order picker is 8 items. Changing aisles does not take any additional time and the average speed in- and outside the aisles is 1 m/s. The distance between the depot and the first location of the most left aisle is 2 meter.
Order 1: 3 items
Order 2: 2 items
Order 3: 6 items
Order 4: 4 items
Order 5: 2 items
Order 6: 5 items
Order 7: 1 item
Total: 23 items

First come, first served

As the title already suggests the order which comes first is served first. This means that the sequence of the arrival of the orders determines how the orders are grouped into batches. When the orders are generated in the warehouse, the order which arrives first there, is the order to which the next orders are added (as long as possible). Thus, the first batch consists of the first order, the second order, the third order etc. as long as the maximum capacity of the truck is not exceeded. If the fourth order can not be added to this batch (because there is not enough space left on the truck) a new batch (batch 2) is created. The fifth order, the sixth order, the seventh order, the eighth order etc. are added to the fourth order. The order, which does not fit to this batch any more, because the maximum capacity is reached, is the first order of a new batch. This algorithm is very simple to use, but will not lead to the best batching results.

EXAMPLE CONTINUED

If this algorithm is applied to the example, four batches are created: batch 1 containing order 1 and 2; batch 2 containing order 3, batch 3 containing order 4 and 5 and batch 4 containing order 6 and 7. Although the maximum capacity is 7 items per batch, none of the batches contains more than 6 items.
The total travel time depends on the routing strategy:

Seed algorithms

Seed algorithms start by choosing an order, the seed order, from all available orders. Other orders have to be added to this seed order. An order is chosen to be seed order on the basis of certain seed selection rules. This seed order is the beginning of a batch and is completed with other orders, which are not already added to a batch, with the use of order addition rules. The seed order is renewed every time an order is added to a batch.

Once the order, which is added to the batch, is determined (on the basis of an order adding rule) then the algorithm can be continued in two ways. The first way is the Single Seed Rule, where the seed order remains the seed order until no additional orders can be added to the batch. The second way is the Cumulative Seed Rule. Here, the order which was chosen to be seed order plus the order added, together form the new seed order: the seed is renewed every time an order is added to it. The order adding rules now apply to the renewed seed. In both ways a new batch is created only if there are no orders left which can be added to the batch. In the algorithm that is used on this internet site, the seed order is renewed every time an order is added; the Cumulative Seed Rule is used.

It is important to choose the best seed order to obtain good batches. There are several criteria on which you can choose a seed order. The order can be chosen arbitrarily, the order with the nearest or the furthest item, the largest or smallest number of aisles, the largest or smallest time to pick all items, the largest or smallest number of items or the order with the largest or smallest distance between the left and the right aisle can be chosen as seed order. Based on experiences, we have chosen to be the seed order when it takes the largest time to pick all of the items.

The next step is to select a rule on which you can base the addition of orders to the seed. Here the orders are added by selecting the candidate order, in such a way that the sum of the distances between every item of the seed order and the nearest item in the candidate order are minimized: sum = item distances, basis = seed order. If the candidate order was chosen to be the basis, then the sum of the distances between every item of the candidate order and the nearest item in the seed order had to be minimized. Other possibilities to select the candidate-order are on the basis of the number of similar locations, the Center of Gravity (the average number of aisles with items of the seed order compared to the candidate order must be minimized), the maximum saving of time (the difference between the time to pick the orders in one batch and the time to pick all orders separately) or with the Additional Aisle rule (the candidate order is the order where the extra number of aisles that have to be visited is the smallest).

The order addition rules, which select a candidate order when the sum of the distances between every item of the seed order and the nearest item in the candidate order are minimized, are using a metric to determine the distance between two locations. The metric we use here is based upon the time to travel from one item to another. Alternative metrics are the Euclidian metric, the Rectilineair metric, the Chebyshev metric and the metric based on the distance between the aisles where the item locations are. Actually, the Euclidian, Rectilineair and Chebyshev metrics are only suited in situations where the warehouse contains only one aisle and the picker goes from one item to the next in a straight line. The Euclidian metric simply calculates this distance, while the Rectilineair metric adds the horizontal to the vertical distance. The Chebyshev takes the maximum distance of these two distances.

This table shows all possible options. The criteria used here are coloured blue.
 

Seed Rule Seed Selection Order Adding Metric
Single Arbitrarely
Number of similar
locations
 Euclidian
Cumulative Furthest item
Sum item distances,
basis: seed order
 Rectilineair
Nearest item
Sum item distances,
basis: candidate order
 Chebyshev
Largest number of aisles  Center of Gravity  Aisle distance 
Smallest number of aisles  Saving of time Travel time
Largest time to pick  Additional Aisle
Smallest time to pick 
Largest number of items 
Smallest number of items
Largest distance between
 
the left and right aisle 
Smallest distance between
the left and right aisle

EXAMPLE CONTINUED

The number of the batches and the contents of the batches depends on the routing mechanism, because the seed selection rule, used here, is based on the largest time to pick, which varies per strategy. Order 6 turns out to be the one with the largest pick time in all routing strategies, but in this example only the S-Shape routing strategy is taken into account. Order 6 is seed order and since the maximum capacity of the truck is 8 items, four other orders (1, 2, 5 and 7) are eligible for candidate order. The sum of the item distances, based on the travel time results in order 7 as candidate order: the travel time between the items of order 6 and the items of order 7 is 7, compared to 18 (11 + 6 + 1) for order 1, 8 (3 + 5) for order 2 and 9 for order 2 (4 + 5). The seed order now is order 6 together with order 7. Only order 2 or 5 can be added . The next order to be added to the seed order is order 2 (the travel time between the items is 8, the travel time between the items of the seed order and order 5 is 9). The next seed order is 3 and only order 5 can be batched. Then, order 1 becomes the seed order and order 4 is added to this batch. These three batches are formed, using the S-Shape strategy, but are different using an other strategy: using the Largest Gap strategy the first batch would exist of order 3 and 7.

The time savings algorithm

The batching algorithm of Clarke and Wright is a savings algorithm and based on their algorithm for the Vehicle Routing Problem (VRP).
The algorithm used here is the basic variant of Clarke and Wright’s savings algorithm. This algorithm consists of several steps that have to be taken:
Determine the saving in time when you batch the orders compared to a separate pick of the orders for every pair of orders and select the combination of orders which generate the highest savings. When the orders are not already assigned to a batch and there is enough capacity left, then form a new batch. When one of the two combined orders is already assigned to a batch then check whether it is possible to assign the other order to the same batch, if not then make a new batch.

Repeat these steps and create new batches of the orders that cannot be assigned to already existing batches. To clarify this algorithm with the illustration above, again the S-Shape heuristic will be used. If this heuristic is used, the savings per combination of (two) orders can be reflected in a table which looks like this:
1
2
3
4
5
6
7
1
---
2
14
---
3
X
21
---
4
44
26
X
---
5
52
14
58
38
---
6
82
46
X
X
58
---
7
26
14
26
6
26
26
---
 

EXAMPLE CONTINUED

This table present the savings that can be reached by batching two orders compared with picking the items of the orders separately. If for example orders 3 and 5 are picked per order, total travel time would be 160 seconds (102 + 58). A combination of these two orders would lead to a travel time of 102 seconds. This means that adding order 5 to order 3 would not lead to additional picking time and thus a saving of 58 seconds. The largest savings (82) can be reached if order 1 and 6 are batched. The next batch consists of order 5 and 3, because after the combination of order 1 and 6, the combination of 3 and 5 leads to the largest savings( 58). The last batch includes orders 2, 4 and 7. If an other algorithm is used, the batches could be totally different.