arXiv:2511.09563cs.AImath.CO2025-11被引 1

提出新方法解决大规模联合路径分配问题,精度接近最优且效率更高。

An Efficient and Almost Optimal Solver for the Joint Routing-Assignment Problem via Partial JRA and Large-α Optimization

  • 通过部分路径重构技术缩小问题规模,快速求解子问题
  • 在n=300~1000的测试中平均偏差为0.00%,接近最优解
  • 适用于物流、旅行商等优化问题,具有广泛扩展潜力

联合路由-分配(JRA)问题需同时确定物品到占位符的分配及访问每对节点恰好一次的哈密顿环,以最小化总行程成本。以往研究采用精确混合整数规划(MIP)求解器,虽保证最优性,但在大规模实例下计算效率低。为此,基于合并算法与扰动策略的启发式方法被提出,可实现约1%偏差内的解。本文提出一种更高效的新方法,通过引入部分路径重构(PPR)求解器,先识别关键物品-占位符对形成简化子问题,高效求解后优化全局解,使初始解偏差减半。结合沿优化路径迭代使用PPR求解器,可进一步提升解精度。此外,在模型中加入全局大α约束,进一步增强解的最优性。在n=300、500、1000的基准数据集上实验表明,该方法始终获得几乎最优解,平均偏差为0.00%,同时保持高计算效率。该框架还可推广至TSP等其他优化问题。

原文摘要 · Abstract (English)

The Joint Routing-Assignment (JRA) optimization problem simultaneously determines the assignment of items to placeholders and a Hamiltonian cycle that visits each node pair exactly once, with the objective of minimizing total travel cost. Previous studies introduced an exact mixed-integer programming (MIP) solver, along with datasets and a Gurobi implementation, showing that while the exact approach guarantees optimality, it becomes computationally inefficient for large-scale instances. To overcome this limitation, heuristic methods based on merging algorithms and shaking procedures were proposed, achieving solutions within approximately 1% deviation from the optimum. This work presents a novel and more efficient approach that attains high-accuracy, near-optimal solutions for large-scale JRA problems. The proposed method introduces a Partial Path Reconstructon (PPR) solver that first identifies key item-placeholder pairs to form a reduced subproblem, which is solved efficiently to refine the global solution. Using this PJAR framework, the initial heuristic merging solutions can be further improved, reducing the deviation by half. Moreover, the solution can be iteratively polished with PPR based solver along the optimization path to yield highly accurate tours. Additionally, a global Large-α constraint is incorporated into the JRA model to further enhance solution optimality. Experimental evaluations on benchmark datasets with n = 300, 500, and 1000 demonstrate that the proposed method consistently delivers almost optimal solutions, achieving an average deviation of 0.00% from the ground truth while maintaining high computational efficiency. Beyond the JRA problem, the proposed framework and methodologies exhibit strong potential for broader applications. The Framework can be applied to TSP and related optimization problems.

组合优化路径规划近似算法启发式求解

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。