# Network-Constrained Policy Optimization for Adaptive Multi-agent Vehicle Routing

arXiv: https://arxiv.org/abs/2510.26089 · HTML: https://mlsanity.com/paper/2510.26089/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 67 references that are in the map.
- First posted on arXiv 30 Oct 2025.

## Builds on (most cited first, 17 of 17)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting](https://mlsanity.com/paper/1709.04875/) (2017)
- [QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1803.11485/) (2018)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [GMAN: A Graph Multi-Attention Network for Traffic Prediction](https://mlsanity.com/paper/1911.08415/) (2019)
- [A Survey on Traffic Signal Control Methods](https://mlsanity.com/paper/1904.08117/) (2019)
- [Learning from Multiple Cities: A Meta-Learning Approach for Spatial-Temporal Prediction](https://mlsanity.com/paper/1901.08518/) (2019)
- [Deep Reinforcement Learning for Multi-Driver Vehicle Dispatching and Repositioning Problem](https://mlsanity.com/paper/1911.11260/) (2019)
- [Forecaster: A Graph Transformer for Forecasting Spatial and Time-Dependent Data](https://mlsanity.com/paper/1909.04019/) (2019)
- [MAGNNETO: A Graph Neural Network-based Multi-Agent system for Traffic Engineering](https://mlsanity.com/paper/2303.18157/) (2023)
- [Deep Reinforcement Learning Based Dynamic Route Planning for Minimizing Travel Time](https://mlsanity.com/paper/2011.01771/) (2020)
- [Hierarchical Deep Double Q-Routing](https://mlsanity.com/paper/1910.04041/) (2019)
- [Feudal Multi-Agent Reinforcement Learning with Adaptive Network Partition for Traffic Signal Control](https://mlsanity.com/paper/2205.13836/) (2022)
- [Scalable and Reliable Multi-agent Reinforcement Learning for Traffic Assignment](https://mlsanity.com/paper/2506.17029/) (2025)
- [PathletRL++: Optimizing Trajectory Pathlet Extraction and Dictionary Formation via Reinforcement Learning](https://mlsanity.com/paper/2412.03715/) (2024)
- [TrajLearn: Trajectory Prediction Learning using Deep Generative Models](https://mlsanity.com/paper/2501.00184/) (2024)

## Built on by (most cited first, 1 of 1)

- [FinInvest-GTCN: Explainable Graph-Temporal-Causal Modeling for Risk-Aware Investment Decision Optimization](https://mlsanity.com/paper/2606.28933/) (2026)

## Abstract (arXiv)

Traffic congestion in urban road networks leads to longer trip times and higher emissions, especially during peak periods. While the Shortest Path First (SPF) algorithm is optimal for a single vehicle in a static network, it performs poorly in dynamic, multi-vehicle settings, often worsening congestion by routing all vehicles along identical paths. We address dynamic vehicle routing through a multi-agent reinforcement learning (MARL) framework for coordinated, network-aware fleet navigation. We first propose Adaptive Navigation (AN), a decentralized MARL model where each intersection agent provides routing guidance based on (i) local traffic and (ii) neighborhood state modeled using Graph Attention Networks (GAT). To improve scalability in large networks, we further propose Hierarchical Hub-based Adaptive Navigation (HHAN), an extension of AN that assigns agents only to key intersections (hubs). Vehicles are routed hub-to-hub under agent control, while SPF handles micro-routing within each hub region. For hub coordination, HHAN adopts centralized training with decentralized execution (CTDE) under the Attentive Q-Mixing (A-QMIX) framework, which aggregates asynchronous vehicle decisions via attention. Hub agents use flow-aware state features that combine local congestion and predictive dynamics for proactive routing. Experiments on synthetic grids and real urban maps (Toronto, Manhattan) show that AN reduces average travel time versus SPF and learning baselines, maintaining 100% routing success. HHAN scales to networks with hundreds of intersections, achieving up to 15.9% improvement under heavy traffic. These findings highlight the potential of network-constrained MARL for scalable, coordinated, and congestion-aware routing in intelligent transportation systems.