多自动导引车缓冲区存储、检索与重排问题：精确与启发式方法研究
The Multi-AMR Buffer Storage, Retrieval, and Reshuffling Problem: Exact and Heuristic Approaches
作者:
Max Disselnmeyer, Thomas Bömer, Laura Dörr 等5人
分类:
cs.RO, cs.AI, cs.MA, math.OC
📝 论文摘要
缓冲区在生产系统中至关重要，用于解耦顺序流程。在密集地面存储环境中，例如空间受限的棕地设施，人工操作正日益受到严重劳动力短缺和运营成本上升的挑战。实现这些区域的自动化需要解决缓冲区存储、检索和重排问题（BSRRP）。虽然先前的研究已经解决了仅限于重排和检索固定物品集的场景，但现实世界的制造需要一种自适应方法，同时还要考虑到达的单元负载。本文介绍了多自主移动机器人BSRRP，协调机器人车队在共享地面区域内管理并发的重排任务，以及时间窗口化的存储和检索任务。我们构建了一个二进制整数规划（IP）模型，以获得用于基准测试的精确解。由于该问题是NP难的，使得精确方法在工业规模上计算不可行，我们提出了一种分层启发式方法。该方法将问题分解为用于单元负载放置任务级序列规划的A*搜索，以及用于多机器人协调和调度的约束规划（CP）方法。实验表明，与精确公式相比，计算时间减少了数个数量级。这些结果证实了该启发式方法作为高密度生产环境响应控制逻辑的可行性。
📊 核心分析
研究动机：解决高密度生产环境中缓冲区管理的自动化难题。研究背景包括：
- 在空间受限的棕地(brownfield)设施中，密集地面存储环境面临劳动力短缺和运营成本上升的挑战
- 现有研究主要关注固定物品集的重新整理(reshuffling)和检索(retrieval)，但实际制造过程需要处理动态到达的单元载荷(unit loads)
- 需要协调多机器人车队管理并发的重新整理、有时限的存储和检索任务
核心方法：
- 建立二元整数规划(Binary Integer Programming, IP)模型以获得精确解作为基准
- 提出分层启发式(hierarchical heuristic)方法，将问题分解为：
1. 使用A*搜索(A* search)进行单元载荷放置的任务级序列规划
2. 使用约束规划(Constraint Programming, CP)进行多机器人协调和调度
核心创新点：
- 首次提出多自主移动机器人(Multi-AMR)缓冲区存储、检索和重新整理问题(Multi-AMR BSRRP)，将动态存储任务纳入统一框架
- 创新性地将时间窗口(time-windowed)存储任务与并发重新整理操作相结合，更贴合实际生产需求
- 设计分层优化架构，有效平衡解的质量与计算效率，解决了工业规模问题的可计算性难题
总体贡献：
- 为高密度生产环境提供了首个完整的Multi-AMR BSRRP问题建模和求解框架
- 通过实验验证启发式方法相比精确方法可实现数量级级的计算时间减少
- 证明了所提启发式方法作为高密度生产环境响应控制逻辑的可行性，为工业自动化提供了实用解决方案