Order batching in walk-and-pick order picking systems

This paper investigates the order-batching problem both as a theoretical problem, including its special variants, and as a practical problem, with possible heuristic solution procedures. It shows that certain special cases or variants of the order batching problem are solvable, while other cases of the problem are NP-hard. It also develops a new Mixed-Integer Programming (MIP) model to obtain near-exact solutions to the problem. The MIP provides good lower and upper bounds to the problem, which prove useful in the investigation of the heuristic solution procedures. The paper identifies and modifies slightly the order batching heuristic, which shows the strongest results in the numerical experiments. Although good solutions are obtained with this particular heuristic, the results indicate that it is computationally intensive. Furthermore, solutions obtained through the MIP model suggest there is still room to obtain even better solutions to the problem via heuristic procedures, although the challenge is to do so without further increasing the computational burden.