Parametrized Multi-Agent Routing via Deep Attention Models
This provides a scalable solution for large-scale mixed-integer optimization in multi-agent routing and facility location, with significant speed and cost improvements over existing methods.
The paper tackles the NP-hard Facility-Location and Path Optimization (FLPO) problem, where multiple agents optimize routes and facility locations to minimize transportation costs, by proposing a deep learning framework called ParaSDM that integrates the Maximum Entropy Principle with a neural policy model. The approach achieves up to 100× speedup in policy inference with a 6% optimality gap, yields over 10× lower cost than metaheuristic baselines, and matches Gurobi's optimal cost with a 1500× speedup.
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.