A hybrid exact algorithm for order batching and assignment in warehouses

Abstract

This paper studies an order batching and assignment problem for a warehousing system considering uncertain future orders. Orders that continuously enter a pool are handled in batches, and the core decision of the problem is to categorize the orders in the pool into batches and assign the orders in the current batch to picking stations in the system. When making the decision for the current batch of orders, we consider future orders with uncertain Stock Keeping Units (SKU) requirements and their quantities. Using mixed-integer linear programming, this paper proposes a two-stage stochastic programming model with integer recourses, which is difficult to solve using traditional algorithms. Thus, a hybrid exact algorithm that combines the branch-and-price algorithm, column generation, and the logic-based Benders decomposition is designed and implemented to solve the model. To accelerate the algorithmic solving process, we propose some new cuts and apply parallel computing techniques to solve some of the subproblems embedded in the algorithm. We also conduct experiments to validate the efficiency of the proposed algorithm and derive some potentially useful managerial insights. For example, a counter-intuitive result is that the more picking stations there are, the worse the objective is (i.e., the total travel time of used pods). In addition, the more SKUs are required per order, the worse the objective is, while the more SKUs are stored per pod, the better the objective is. Furthermore, the deployment of picking stations along one short side of the warehouse is the best layout for the system.