Branch-Price-and-Cut-Based Solution of Order Batching Problems

Given a set of customer orders each comprising one or more individual items to be picked, the order batching problem (OBP) in warehousing consists of designing a set of picking batches such that each customer order is assigned to exactly one batch, all batches satisfy the capacity restriction of the pickers, and the total distance traveled by the pickers is minimal. In order to collect the items of a batch, the pickers traverse the warehouse using a predefined routing strategy. We propose a branch-price-and-cut (BPC) algorithm for the exact solution of the OBP investigating the routing strategies traversal, return, midpoint, largest gap, combined, and optimal. The column-generation pricing problem is modeled as a shortest path problem with resource constraints (SPPRC) that can be adapted to handle the implications from nonrobust valid inequalities and branching decisions. The SPPRC pricing problem is solved by means of an effective labeling algorithm that relies on strong completion bounds. Capacity cuts and subset-row cuts are used to strengthen the lower bounds. Furthermore, we derive two BPC-based heuristics to identify high-quality solutions in short computation times. Extensive computational results demonstrate the effectiveness of the proposed methods. The BPC is faster by two orders of magnitude compared with the state-of-the-art exact approach and can solve to optimality hundreds of instances that were previously unsolved. The BPC-based heuristics are able to significantly improve the gaps reported for the state-of-the-art heuristic and provide hundreds of new best-known solutions. Funding: This research was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) [Grant 418727865]. This support is gratefully acknowledged. Supplemental Material: The e-companion is available at https://doi.org/10.1287/trsc.2023.1198 .