The Single Picker Routing Problem with Scattered Storage in Parallel-Aisle Warehouse with Multiple Blocks

This paper investigates the b-block single picker routing problem with scattered storage (b-SPRP-SS). For a parallel-aisle warehouse comprising b blocks, the b-SPRP-SS asks for the determination of a picker tour that minimizes travel distance while collecting all articles from a given pick list. Scattered storage, where articles can be stored at multiple locations, substantially increases the problem’s complexity by coupling the selection of collection points with routing decisions. Existing research on the b-SPRP-SS has predominantly focused on single-block and two-block warehouse layouts. To address this gap, we propose a novel formulation for warehouses with more than two blocks. The formulation is inspired by the dynamic-programming state spaces that Ratliff and Rosenthal introduced for the single-block case and Roodbergen and de Koster for the two-block case. The new state space is a relaxed one that omits connectivity information, thereby aggregating multiple original states into a single relaxed state. This relaxation significantly reduces Computational complexity, although it may lead to disconnected tour fragments. To ensure route connectivity, the problem is solved using a branch-and-cut algorithm which dynamically adds subtour-elimination constraints. Extensive computational experiments demonstrate that the proposed approach is effective and outperforms the only other competitive exact approach from the literature that relies on a transformation into a generalized traveling salesman problem.