用深度注意力模型联合优化多智能体路径与设施选址,显著提速降本。
Parametrized Multi-Agent Routing via Deep Attention Models
- 设计可微的SPN神经网络,联合优化路径与设施位置。
- 相比基线提速100倍,平均损耗仅6%,最优解差距小。
- 适合大规模物流、配送等混合整数优化场景。
我们提出一种可扩展的深度学习框架ParaSDM,用于参数化序列决策,多个智能体协同优化离散动作策略与共享连续参数。核心应用场景为设施选址与路径优化(FLPO),需同时确定最优路径和设施位置,以最小化网络内累计运输成本。由于混合离散-连续结构及高度非凸目标,此类问题属于NP难。为此,我们结合最大熵原理(MEP)与一种称为最短路径网络(SPN)的神经策略模型——一种排列不变的编码器-解码器架构,在近似MEP解的同时实现对共享参数的高效梯度优化。SPN在策略推理和梯度计算上相比MEP基线提速高达100倍,跨多种规模问题的平均最优性差距约6%。所提FLPO方法相较元启发式基线降低超过10倍成本,且运行更快;采用退火策略时,其成本逼近Gurobi最优解,速度提升达1500倍,确立了ParaSDM问题的新基准。结果表明,结构化深度模型在求解大规模混合整数优化任务中具有强大潜力。
原文摘要 · Abstract (English)
We propose a scalable deep learning framework for parametrized sequential decision-making (ParaSDM), where multiple agents jointly optimize discrete action policies and shared continuous parameters. A key subclass of this setting arises in Facility-Location and Path Optimization (FLPO), where multi-agent systems must simultaneously determine optimal routes and facility locations, aiming to minimize the cumulative transportation cost within the network. FLPO problems are NP-hard due to their mixed discrete-continuous structure and highly non-convex objective. To address this, we integrate the Maximum Entropy Principle (MEP) with a neural policy model called the Shortest Path Network (SPN)-a permutation-invariant encoder-decoder that approximates the MEP solution while enabling efficient gradient-based optimization over shared parameters. The SPN achieves up to 100$\times$ speedup in policy inference and gradient computation compared to MEP baselines, with an average optimality gap of approximately 6% across a wide range of problem sizes. Our FLPO approach yields over 10$\times$ lower cost than metaheuristic baselines while running significantly faster, and matches Gurobi's optimal cost with annealing at a 1500$\times$ speedup-establishing a new state of the art for ParaSDM problems. These results highlight the power of structured deep models for solving large-scale mixed-integer optimization tasks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。