Benders Decomposition using Core-Maximal Cuts and Its Application to the Single-Picker Routing Problem with Scattered Storage

We present a new solution approach to the single-picker routing problem with scattered storage (SPRP-SS) for order picking in warehouses. Heßler and Irnich (INFORMS J. on Comp. 36(6):1417–1435, 2024) demonstrated how to construct an extension to Ratliff and Rosenthal’s state space to incorporate the scattered storage dimension. Based on this extended state space, we propose a new formulation that makes two types of decisions: selection of pick positions and determination of the tour that visits the chosen pick positions. This novel formulation is an ideal starting point for a Benders decomposition. For this approach, a fast convergence is crucial. To this end, we analyze properties of the optimality cuts. We examine the most popular type of cut from the literature—the Magnanti-Wong cut—and determine how modified subproblems, such as Magnanti and Wong’s, generate stronger cuts than arbitrary subproblem solutions. As a result, we propose core-maximal cuts as a new type of optimality cut. In our computational experiments, we compare the resulting Benders decomposition algorithm with three mixed-integer linear programming formulations, as well as alternative Benders approaches. Core-maximal cuts can be used also for other Benders subproblems as well. We showcase the application to the capacitated facility location problem and the fixed charge network flow problem. Results show that this approach often requires fewer Benders iterations and has shorter total computation times than established Benders decomposition algorithms.