The Multi-AMR Buffer Storage, Retrieval, and Reshuffling Problem: Exact and Heuristic Approaches

Max Disselnmeyer; Thomas Bömer; Laura Dörr; Bastian Amberg; Anne Meyer

cs.ROMar 27, 2026

The Multi-AMR Buffer Storage, Retrieval, and Reshuffling Problem: Exact and Heuristic Approaches

Authors: Max Disselnmeyer, Thomas Bömer, Laura Dörr, Bastian Amberg, Anne Meyer

Organizations: Karlsruhe Institute of Technology, Zirkel 2, 76131 Karlsruhe, Germany

Abstract

Buffer zones are essential in production systems to decouple sequential processes. In dense floor storage environments, such as space-constrained brownfield facilities, manual operation is increasingly challenged by severe labor shortages and rising operational costs. Automating these zones requires solving the Buffer Storage, Retrieval, and Reshuffling Problem (BSRRP). While previous work has addressed scenarios where the focus is limited to reshuffling and retrieving a fixed set of items, real-world manufacturing necessitates an adaptive approach that also incorporates arriving unit loads. This paper introduces the Multi-AMR BSRRP, coordinating a robot fleet to manage concurrent reshuffling, alongside time-windowed storage and retrieval tasks, within a shared floor area. We formulate a Binary Integer Programming (IP) model to obtain exact solutions for benchmarking purposes. As the problem is NP-hard, rendering exact methods computationally intractable for industrial scales, we propose a hierarchical heuristic. This approach decomposes the problem into an A* search for task-level sequence planning of unit load placements, and a Constraint Programming (CP) approach for multi-robot coordination and scheduling. Experiments demonstrate orders-of-magnitude computation time reductions compared to the exact formulation. These results confirm the heuristic's viability as responsive control logic for high-density production environments.

Figures & tables

Panel of Figure 1 — Figure 1: Real-world buffer scenario from the surface coating industry. Automating material flow in such space-constrained brownfield facilities requires solving the Buffer Storage, Retrieval, and Reshuffling Problem (BSRRP) to ensure continuous machine supply.

Panel of Figure 2 — Figure 2: Conceptual comparison of buffer accessibility: a) Access from the Perimeter, as defined in the BSRRP. a) In-Grid Access, typical for Robotic Mobile Fulfillment Systems (RMFS) where agents navigate within the grid; In the former, AMRs are restricted to the exterior aisles, necessitating strategic reshuffling of obstructing unit loads to access deep LIFO slots.

Reference	Handling Operations	Access Mode	Fleet	Temporal Representation	Method
Caserta et al. (2012)	$\LEFTcircle$	Perimeter	1 Crane	Moves	IP
Borjian et al. (2015)	●	Perimeter	1 Crane	Continuous	IP
Ji et al. (2015)	$\LEFTcircle$	Perimeter	n Cranes	Moves	Genetic Algo.
Bömer et al. (2024)	$\bigcirc$	Perimeter	n AMRs	Moves	CP
Disselnmeyer et al. (2024)	$\LEFTcircle$	Perimeter	1 AMR	Continuous	IP
Hu et al. (2025)	$\bigcirc$	In-Grid	n AMRs	Steps	CBS Search

Table 1: Comparison of related literature in the field of Block Relocation and Buffer Reshuffling.

Panel of Figure 3 — Figure 3: Logical decomposition of the storage area. (a) The continuous floor is discretized into slots. (b) These slots are grouped into Static Lanes (colored), where each lane acts as a LIFO stack accessible from the perimeter. The grey numbered rectangles represent the unit loads

Notation	Description
$\mathcal{N},\mathcal{V},\mathcal{T}$	Sets of unit loads, AMRs, and time steps.
$\mathcal{I},\mathcal{I}^{\prime}$	Sets of all lanes (incl. I/O), Set of all buffer lanes (excl. I/O).
$[i,j]$	Slot at lane $i$ and position $j$ ( $j=1$ is deepest in the lane).
$d_{ijkl}$	Distance between slots $[i,j]$ and $[k,l]$ .
$\tau_{ijkl}$	Travel and handling time (cost) between slots $[i,j]$ and $[k,l]$ .
$h$	Handling time for picking up or dropping a unit load.

Table 2: Sets, indices, and parameters

Panel of Figure 4 — Figure 4: Overview of the hierarchical heuristic. The sequential stages transform the input from a linearized task sequence into strict precedence constraints, then into timed assignments, and finally into collision-free trajectories.

Symbol	Description
Sets and Indices
$\mathcal{O}$	Set of storage and retrieval orders ( $\mathcal{O}=\mathcal{O}_{S}\cup\mathcal{O}_{R}$ )
$\mathcal{O}_{S},\mathcal{O}_{R}$	Subsets of storage and retrieval orders
$o,p$	Indices for specific orders ( $o,p\in\mathcal{O}$ )
$\mathcal{G}$	Set of dependency groups formed during priority assignment
$\mathcal{M}$	Set of moves generated by A* search

Table 3: Notation and parameters used in the heuristic approach

Parameter	Category	Small ( $3\times 3$ )	Large ( $4\times 4$ )
Fleet Size ( $\|\mathcal{V}\|$ )	1 AMR	151	0
	2 AMRs	288	48
	3 AMRs	277	46
Access Directions	1 Side	72	1
	2 Sides	373	54
	4 Sides	271	39

Table 4: Composition of the Benchmark Reference Set: 810 high-quality instances filtered from a pool of 6,903 generated small-scale scenarios.

		Solve Rate Heuristic			Computational Efficiency (Median)			Median Opt.
Layout	Fleet ( $\|\mathcal{V}\|$ )	Number of Instances	Solved	Rate	EF Runtime	Heur. Runtime	Speedup	Gap (%)
$3\times 3$	1 AMR	151	139	92.1%	515.5 s	0.05 s	10,310x	2.56%
	2 AMRs	288	284	98.6%	253.0 s	0.08 s	3,163x	10.20%
	3 AMRs	277	275	99.3%	307.2 s	0.09 s	3,413x	14.58%
$4\times 4$	2 AMRs	48	44	91.7%	1,524.3 s	3.37 s	452x	4.70%
$4\times 4$	3 AMRs	46	45	97.8%	2,927.9 s	2.52 s	1,162x	10.63%

Table 5: Performance assessment: Feasibility, Runtime, and Optimality Gap comparison between the EF and the Heuristic approach across the reference set.

Figure 5: Performance comparison between the EF and the proposed Heuristic. Top panels: Runtime distributions (logarithmic scale) across $3\times 3$ and $4\times 4$ layouts. Bottom panels: Optimality gaps relative to the exact lower bound, categorized by unit-load-to-slot-ratio.

Figure 6: Visualization of a solution in a high-density $8\times 3$ layout (21 unit loads) with 4 AMRs. The bottom-left of each sub-figure indicates the corresponding decision variable from the EF (also visualized with the dotted arrows; white for empty drives; black for transportation of an UL), while T denotes the discrete time step of the event.

Panel of Figure 7 — Figure 7: Real-world use case (surface coating). This brownfield scenario demonstrates the conversion of dead floor space into an autonomous buffer. Unlike open grids, the layout is dictated by the footprint of the machinery. The visualization highlights the heuristic’s capability to assign inventory to separated zones (depth 1 vs. depth 2) to optimize storage utilization within the irregular boundaries.

Panel of Figure 8 — Figure 8: Algorithmic storage location assignment in the brownfield scenario. The heatmaps contrast buffer duration (a) with traffic flow (b), highlighting the differentiation between high-density storage and transfer zones.

Layout Topology	Ratio	Access Directions				Solve Rate
Layout Topology	Ratio	1	2	3	4
Rectangle ( $8\times 3$ )	0.7	30/50	50/50	–	–	80.0%
	0.8	15/50	50/50	–	–	65.0%
	0.9	5/50	50/50	–	–	55.0%
	1.0	0/50	45/50	–	–	45.0%
Block ( $5\times 5$ )	0.7	0/50	85/100	–	50/50	67.5%

Table 6: Sensitivity Analysis: feasibility by unit load to slot ratio and access directions. The table displays the success rate as a fraction (Solved/Generated) for various layouts.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Element	Notation	Description
Sets and Indices
Set of unit loads	$\mathcal{N}$ , $n$	Range: $\{1,2,\dots,N\}$
Set of time steps	$\mathcal{T}$ , $t$	Range: $\{1,2,\dots,T\}$
Set of all lanes	$\mathcal{I}$ , $i,k$	Range: $\{0,1,\dots,I\}$
Set of buffer lanes	$\mathcal{I^{\prime}}$	Range: $\{1,2,\dots,I-1\}$ (excluding sink and source)
Set of slots	$\mathcal{J}_{i,k}$ , $j,l$	Range: $\{1,2,\dots,J\}$

Appendix

Table 7: Sets, indices, and general notation for the Integer Programming model

Industrial Robotics

Industrial robotics develops robots, control systems, and planning methods for manufacturing, assembly, inspection, and material handling.

See all 67 papers

Complete, Scalable, and Robust Prioritized Planning for Multi-Robot Ordered Storage and Retrieval at Maximum Capacity
Aug 7, 2026William Zhang, Tzvika Geft, Jingjin Yu +1Multi-Robot Motion Planning Multi-Robot Systems
Department of Computer Science, Rutgers University, New Brunswick, NJ, USA
CREST: Constraint-Release Execution for Multi-Robot Warehouse Shelf Rearrangement
Mar 27, 2026Jiaqi Tan, Yudong Luo, Sophia Huang +2Multi-Robot Systems Robotics
School of Computing Science, Simon Fraser University, Burnaby, BC V5A 1S6, Canada · HEC Montréal, Montréal, QC H3T 2A7, Canada · Purdue University, West Lafayette, IN 47907 USA
ARMATA: Auto-Regressive Multi-Agent Task Assignment
May 5, 2026Yazan Youssef, Aboelmagd Noureldin, Sidney GivigiMulti-Agent System Optimization Multi-Robot Task Allocation
Department of Electrical and Computer Engineering, Queen’s University, Kingston, ON, Canada · Department of Electrical and Computer Engineering at the Royal Military College of Canada, and the Department of Electrical and Computer Engineering at Queen’s University, both in Kingston, Canada · School of Computing, Queen’s University, Kingston, ON, Canada

Aug 7, 2026J/K move · Enter open · S save

Complete, Scalable, and Robust Prioritized Planning for Multi-Robot Ordered Storage and Retrieval at Maximum Capacity

William Zhang, Tzvika Geft, Jingjin Yu, Kostas Bekris

Department of Computer Science, Rutgers University, New Brunswick, NJ, USA

Multi-Robot Motion Planning Multi-Robot Systems Robust MAPF Multi-Agent Path Finding

Open paper AskPDF arXiv

Automated warehouses face a fundamental trade-off between maximizing storage density and achieving high retrieval throughput. While puzzle-based storage (PBS) architectures increase capacity by eliminating aisles, coordinating multiple robots in these high-density spaces is computationally challenging due to the potential for deadlocks. This paper introduces a novel multi-robot formulation for the ``ordered storage and retrieval problem at maximum capacity''. The focus is on rectangular grids accessible from a single boundary, where loads need to be first stored up to full capacity and then efficiently retrieved, given a planned departure sequence. This work bridges the gap between geometric feasibility and execution efficiency by leveraging the properties of relocation-free arrangements. These properties guide an online, prioritized multi-agent path-finding algorithm, which is the main contribution of this work. Unlike general centralized planners, the approach exploits the specific invariants of the storage arrangement to guarantee completeness and prevent deadlocks, enabling scalability. Experiments demonstrate that the method achieves near-linear improvement in makespan with respect to the number of robots, up to

m = C

, where

C

is the grid width. Crucially, the algorithmic overhead of supporting robustness is negligible; the system handles uncertainty in departure sequences using robust storage arrangements with no significant penalty in execution speed compared to the non-robust baseline.

Abstract

Industrial Robotics

Explore similar work

Complete, Scalable, and Robust Prioritized Planning for Multi-Robot Ordered Storage and Retrieval at Maximum Capacity

CREST: Constraint-Release Execution for Multi-Robot Warehouse Shelf Rearrangement

ARMATA: Auto-Regressive Multi-Agent Task Assignment