Problem Description

The Order Batching Problem consist of grouping the orders (composed by a list of items) received in a warehouse in a set of batches in such a way that the time needed to collect all the orders is minimized. Each batch have to be collected by a single picker without exceeding a capacity limit.

We center our attention in rectangular warehouses with parallel aisles and two cross aisles (one at the front and one at the back of the warehouse), with a depot at the front cross aisle (or, as in the next figure, at the bottom, either left or centered):

This problem is divided into two different problems: the grouping of orders into batches and the routing to collect them.

State of the Art Methods

This problem has been proved to be NP-hard for general instances. Nonetheless, it is solvable in polynomial time if each batch does not contain more than two orders. Real warehouse instances does not usually fall into this category.

One of the fist heuristic approaches might be the First-Come First-Served (FCFS) strategy. In this strategy, orders are sorted according to their arrival time to the warehouse. Following this sorting, they are added to the first batch as far as its capacity limit is not exceeded. There are other heuristic approaches to the OBP in the literature. For instance, "seed methods" (Gibson and Sharp, 1992; Ho and Tseng, 2006; Pan and Liu, 1995) and "saving methods" (Rosenwein, 1996) are generaly considered as constructive methods.

The first metaheuristic algorithm was a Genetic Algorithm applied by Hsu et al., 2005.

Later, in Albareda-Sambola et al., 2009, the authors proposed a Variable Neighborhood Descent (VND) to tackle the problem. They improve the naive solution provided by its constructive method with a VND method, using three well-known routing strategies.

Henn et al., 2010, and Henn and Wäscher, 2012, proposed several methods to address the OBP. First, they proposed a Tabu Search metaheuristic and, second, an Attribute-Based Hill Climber (ABHC), among others. They also considered two well-known routing strategies to evaluate the solutions produced by their algorithms.

As far as we know, the most recent approach to tackle the Order Batching Problem was carried out by Öncan, 2014, where the author proposed an Iterated Local Search with Tabu Thresholding (ILST). The author considered three well-known routing strategies.

Instances

We have experimented with two sets of instances, totalizing 144 instances:

• Henn and Wäscher, 2012: This collection of instances consists of a rectangular warehouse with 10 aisles and 90 storage locations each. The depot is always located at the bottom left corner. The item distribution is both (i) ABC distribution and (ii) random distribution. Customer orders varies from 40 to 100 in steps of 20 and the capacity of the picker ranges between 30 and 75 in steps of 15.
• Albareda-Sambola et al., 2009: This set consists of four different rectangular warehouses with the depot located either at the bottom left corner or at the bottom center of the warehouse. The item distribution is also both (i) ABC distribution and (ii) random distribution. The number of orders varies from 50 to 250 in steps of 50 and the capacity of the picker depends on the warehouse.

The comparison has been made against three subsets of instances. The first one is a subset of Albareda-Sambola et al., 2009 and contains 80 instances. The second one is a subset of Henn and Wäscher, 2012 containing 64 instances. These 144 instances were used to compare our algorithm against ABHC and VND state-of-the-art algorithms; and you can download Order Batching Problem instances here. The third one is a subset of 400 instances of Henn and Wäscher, 2012 used to compare our algorithm against the ILST algorithm; you can download this set of 400 instances here.