Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Equity-Transformer: Solving NP-Hard Min-Max Routing Problems as Sequential Generation with Equity Context
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Equity-Transformer, a sequential-generation attention model with multi-agent positional encoding and an equity context encoder that solves large-scale min-max mTSP and mPDP, beating LKH3, OR-Tools, ScheduleNet, NCE, AM and HAM in cost-runtime trade-offs.
Problem
Min-max multi-agent routing (minimizing the maximum tour length across agents) is NP-hard, and existing heuristics and parallel-planning neural solvers struggle to scale to thousands of cities and hundreds of agents while keeping workloads equitable.
Approach
Cast min-max routing as one long sequential action generation (sub-sequences per agent split by depot tokens), with virtual-order multi-agent positional encoding for agent precedence and an equity context (problem, agent, scale N/M, and distance context) fed as the decoder query so tours stay balanced.
Key results
- On mTSP with N=1000, M=100, Equity-Transformer reaches cost 2.05 versus LKH3 2.92 and NCE 2.16, about 335x faster than LKH3 (1.79s vs 600s).
- On N=5000 mTSP, ScheduleNet runs out of budget, and Equity-Transformer beats NCE at 2.40 vs 2.97 with roughly 33x speedup.
- On mPDP with N=200, M=10, the augmented ET-dagger variant reaches 4.68 cost versus OR-Tools (600s) 18.76.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Equity-Transformer instead of NCE | mTSP · mTSP (N=1000, M=100) | cost: 2.16 -> 2.05 | Helped |
| Use Equity-Transformer instead of LKH3 | mTSP · mTSP (N=1000, M=100) | cost: 2.92 -> 2.05 | Helped |
| Use Equity-Transformer† instead of HAM† | mPDP · mPDP (N=200, M=10) | cost: 5.30 -> 4.68 | Helped |
| Use Equity-Transformer† instead of OR-Tools | mPDP · mPDP (N=200, M=10) | cost: 18.76 -> 4.68 | Helped |
| Add multi-agent positional encoding and context encoder (ablation) | sequential-planning AM · mTSP (N=100, M=10) | cost: 2.12 -> 1.96 | Helped |
| Add multi-agent positional encoding and context encoder (ablation) | sequential-planning AM · mTSP (N=200, M=10) | cost: 2.92 -> 2.15 | Helped |
| Add multi-agent positional encoding and context encoder (ablation) | sequential-planning AM · mTSP (N=200, M=15) | cost: 2.90 -> 1.99 | Helped |
| Add multi-agent positional encoding and context encoder (ablation) | sequential-planning AM · mTSP (N=200, M=20) | cost: 2.90 -> 1.98 | Helped |
| Add multi-agent positional encoding without context encoder (ablation) | sequential-planning AM · mTSP (N=200, M=20) | cost: 2.90 -> 2.80 | Helped |
| Add context encoder without multi-agent positional encoding (ablation) | sequential-planning AM · mTSP (N=200, M=10) | cost: 2.92 -> 2.28 | Helped |
| Add context encoder without multi-agent positional encoding (ablation) | sequential-planning AM · mTSP (N=200, M=20) | cost: 2.90 -> 1.98 | Helped |
| Add multi-agent positional encoding to the context-encoder variant (ablation) | sequential-planning AM · mTSP (N=200, M=20) | cost: 1.98 -> 1.98 | No clear effect |
Surprising findings
- Standard AM and HAM produce identical min-max costs across several agent counts, suggesting min-sum designs ignore equity among agents.
Limitations
- Training and finetuning took about one day (mTSP) and four days (mPDP), and scaling beyond the reported sizes is not tested.
- LKH3 cannot handle mPDP, so the mPDP comparison omits it.
- Speed comparison between CPU classical solvers and GPU learning methods is hard to make fair.
Experimental setup
Datasets: uniform random synthetic mTSP and mPDP instances TSPLIB converted to mTSP
Benchmarks: min-max mTSP synthetic (N up to 5000) min-max mPDP synthetic (N up to 5000) TSPLIB-derived mTSP mCVRP30 distribution shift instances
Metrics: min-max tour cost runtime in seconds
Baselines: LKH3 OR-Tools ScheduleNet Neuro Cross Exchange AM HAM GNN-DisPN SplitNet
Builds on: Attention Model REINFORCE ScheduleNet POMO-style symmetric shared baseline
Closest papers by meaning
- Hybrid-Balance GFlowNet for Solving Vehicle Routing Problems (NeurIPS 2025 · similarity 0.85)
- DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems (ICML 2024 · similarity 0.83)
- DualOpt: A Dual Divide-and-Optimize Algorithm for the Large-scale Traveling Salesman Problem (AAAI 2025 · similarity 0.83)
- Neural Combinatorial Optimization for Robust Routing Problem with Uncertain Travel Times (NeurIPS 2024 · similarity 0.83)
- GLOP: Learning Global Partition and Local Construction for Solving Large-Scale Routing Problems in Real-Time (AAAI 2024 · similarity 0.83)
- URB - Urban Routing Benchmark for RL-equipped Connected Autonomous Vehicles (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.