Assignment-Routing Optimization: Solvers for Problems Under Constraints

📄 arXiv: 2512.18618v1 📥 PDF

作者: Yuan Qilong, Michal Pavelka

分类: cs.AI

发布日期: 2025-12-21

备注: 11 pages, 1 figures

💡 一句话要点

提出基于MIP的联合路由-分配优化求解器，解决约束下的包装规划问题

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 联合路由分配 混合整数规划 包装规划 机器人运动规划 物流优化

📋 核心要点

  1. 现有联合路由-分配问题求解器在处理复杂约束和实际包装场景时存在局限性，计算效率有待提高。
  2. 提出一种基于混合整数规划（MIP）的求解器，专门针对具有多种约束的实际包装规划场景进行优化。
  3. 实验结果表明，该MIP方法能稳定且快速地获得全局最优解，显著优于现有方法，并接近最优距离。

📝 摘要（中文）

本文研究了联合路由-分配（JRA）问题，其中物品必须与占位符进行一对一分配，同时确定一个精确访问所有节点的哈密顿回路。通过使用Gurobi和切割平面子回路消除扩展先前的精确MIP求解器，我们开发了一个为具有更丰富约束的实际包装规划场景量身定制的求解器。这些约束包括多个占位符选项、时间范围限制和多类物品包装。在46个移动操作数据集上的实验表明，所提出的MIP方法实现了全局最优，且计算时间稳定且低，显著优于基于摇动的精确求解器，性能提升高达一个数量级。与贪婪基线相比，MIP解决方案实现了始终如一的最优距离，对于简单启发式方法，平均偏差为14%，证实了效率和解决方案质量。结果突出了基于MIP的JRA优化在机器人包装、运动规划和复杂物流中的实际适用性。

🔬 方法详解

问题定义：论文旨在解决联合路由-分配（JRA）问题，该问题要求在满足特定约束（如多个占位符选项、时间范围限制和多类物品包装）的情况下，将物品一对一地分配给占位符，并同时找到访问所有节点的哈密顿回路。现有方法，特别是基于摇动的精确求解器，在处理复杂约束和大规模问题时效率较低，难以在实际应用中达到全局最优解。

核心思路：论文的核心思路是利用混合整数规划（MIP）的强大优化能力，将JRA问题建模为一个MIP问题，并使用Gurobi求解器进行求解。通过引入切割平面子回路消除技术，进一步提高求解效率，确保找到全局最优解。这种方法能够有效地处理各种约束条件，并提供高质量的解决方案。

技术框架：该方法的技术框架主要包括以下几个步骤：1) 将JRA问题建模为MIP问题，包括定义决策变量、目标函数和约束条件；2) 使用Gurobi求解器求解MIP问题，得到物品分配和路由方案；3) 引入切割平面子回路消除技术，迭代地识别并消除子回路，直到获得一个完整的哈密顿回路；4) 对求解结果进行验证和评估，确保满足所有约束条件。

关键创新：该论文的关键创新在于将MIP方法应用于具有复杂约束的JRA问题，并开发了一种专门针对实际包装规划场景的求解器。与传统的基于摇动的求解器相比，MIP方法能够更有效地处理各种约束条件，并获得全局最优解。此外，切割平面子回路消除技术的引入进一步提高了求解效率。

关键设计：MIP模型中的关键设计包括：1) 决策变量：用于表示物品与占位符之间的分配关系以及节点之间的连接关系；2) 目标函数：通常是最小化总的路由距离或成本；3) 约束条件：包括一对一分配约束、时间范围约束、多类物品包装约束以及子回路消除约束。切割平面子回路消除技术通过迭代地添加线性不等式来消除子回路，这些不等式基于识别到的子回路的节点集合。

🖼️ 关键图片

fig_0
img_1

📊 实验亮点

实验结果表明，所提出的MIP方法在46个移动操作数据集上实现了全局最优，且计算时间稳定且低。与基于摇动的精确求解器相比，性能提升高达一个数量级。与贪婪基线相比，MIP解决方案实现了始终如一的最优距离，对于简单启发式方法，平均偏差为14%，证实了效率和解决方案质量。

🎯 应用场景

该研究成果可广泛应用于机器人包装、运动规划和复杂物流等领域。例如，在电商仓库中，可以优化拣货机器人的路径规划和物品分配，提高拣货效率和降低运营成本。在自动化生产线上，可以优化物料的运输和分配，提高生产效率和产品质量。此外，该方法还可以应用于无人机配送、智能交通等领域，具有广阔的应用前景。

📄 摘要（原文）

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 .