Item batching for picker routing in warehouses: Applying column generation with an exact, novel subproblem algorithm

Abstract

The item batching problem concerns finding an optimal partitioning of items waiting to be picked in a warehouse into batches, such that these batches can be picked with minimal total walking distance. In this project, the item batching problem is solved through column generation, an efficient method for solving linear optimization problems with an enormous number of variables (which, in this case, represent possible batches). In order to achieve optimality through column generation, one needs to be able to solve a problem-specific subproblem to optimality. For the item batching problem, this subproblem is a version of the computationally intensive prize-collecting travelling salesperson problem. To solve this subproblem to optimality, a novel dynamic programming algorithm with a heuristic guide is developed, which solves the subproblem optimally in times ranging from milliseconds to seconds, depending on the details of the problem instance. Overall, the implemented column generation algorithm finds optimal solutions in a matter of seconds per generated batch for all test cases, but sometimes requires hours to verify that these solutions are optimal. The optimal solutions provide great improvements over current batching strategies, often more than halving the total distance that the warehouse workers need to walk while picking. However, simple, alternative algorithms provide similar improvements in a matter of milliseconds, making the column generation time-consuming, computationally intensive, and unwieldy for very little gain when compared to the simple, alternative algorithms. The developed subproblem algorithm is easily generalizable, and could be used for more complicated variants of the item batching problem, like the order batching problem, where the simple, alternative algorithms are less likely to perform well.