Reshuffle-Aware Storage Assignment in Bin Stacking Robotic Warehouses

In bin stacking robotic warehouses, bins are stacked vertically to increase storage density and save floorspace. Retrieving a requested bin requires reshuffle any blocking bins above it. This operational characteristic creates strongly coupled decisions involving storage assignment, reshuffle, and retrieval, making the overall problem particularly difficult and relatively underexplored. We address this reshuffle-aware storage assignment problem by proposing a compact reshuffle–retrieval flow formulation, analyzing the symmetry and optimality properties inherent in storage and reshuffling decisions, and developing efficient exact and matheuristic algorithms. We propose a two-level decomposition-symmetry algorithm to solve the problem exactly. The first level employs logic-based Benders decomposition (LBBD) to decouple the problem into a Benders master problem for storage allocation and a Benders subproblem for reshuffle and retrieval decisions;efficient storage symmetry breaking cuts are further proposed to strengthen the Benders master problem.The second level tackles the Benders subproblem with a tailored branch-and-price method, which incorporates powerful reshuffle symmetry breaking cuts to further prune the solution space. To solve practical-scale instances involving tens of thousands of bins and thousands of items, we further develop a scalable LBBD matheuristic that integrates heuristic presolving and cutting planes to produce near-optimal solutions. Computational experiments demonstrate that the exact method outperforms a state-of-the-art commercial solver by solving substantially larger instances to optimality while significantly reducing computing time. Meanwhile,the LBBD matheuristic achieves consistently strong performance on real-world datasets. Finally,comparison with commonly used storage policies shows that the reshuffle-aware storage assignment considerably reduces bin-handling time and leads to significant improvements in operational efficiency.