用混合整数规划优化机器人包装中的物品分配与路径规划。
Assignment-Routing Optimization: Solvers for Problems Under Constraints
- 基于MIP构建求解器，整合多项实际约束条件。
- 在46个数据集上实现全局最优，计算速度比传统方法快一个数量级。
- 适合机器人包装、物流调度等复杂场景的高效决策需求。
我们研究联合路由-分配（JRA）问题：需将物品一一对应分配至位置点，并同时确定访问所有节点恰好一次的哈密顿回路。在先前基于Gurobi的精确混合整数规划（MIP）求解器基础上，引入割平面子环消除技术，开发出适用于实际包装规划场景的求解器，支持多种位置选项、时间窗限制及多类别物品打包。在46个移动操作数据集上的实验表明，所提MIP方法能稳定达到全局最优，计算时间显著低于基于扰动的精确求解器，最快提升达一个数量级；相较于贪心基线，其路径长度平均偏差仅14%，验证了方法的高效性与解的质量。结果表明，基于MIP的JRA优化在机器人包装、运动规划与复杂物流中具有强实用性。
原文摘要 · Abstract (English)
We study the Joint Routing-Assignment (JRA) problem in which items must be assigned one-to-one to placeholders while simultaneously determining a Hamiltonian cycle visiting all nodes exactly once. Extending previous exact MIP solvers with Gurobi and cutting-plane subtour elimination, we develop a solver tailored for practical packaging-planning scenarios with richer constraints.These include multiple placeholder options, time-frame restrictions, and multi-class item packaging. Experiments on 46 mobile manipulation datasets demonstrate that the proposed MIP approach achieves global optima with stable and low computation times, significantly outperforming the shaking-based exact solver by up to an orders of magnitude. Compared to greedy baselines, the MIP solutions achieve consistent optimal distances with an average deviation of 14% for simple heuristics, confirming both efficiency and solution quality. The results highlight the practical applicability of MIP-based JRA optimization for robotic packaging, motion planning, and complex logistics .
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。