Solving Scalable Multiagent Routing Problems With Reinforcement Learning

Yujiao Hu

doi:10.1109/TNNLS.2025.3591311

Solving Scalable Multiagent Routing Problems With Reinforcement Learning

2025-07-01

13

PRE

AI

DOI：10.1109/TNNLS.2025.3591311

Original

Original request for help

Save

Abstract

En 中文

Multiagent routing problems, arising from practical applications, such as logistics, transportation, and emergency response, face challenges due to the exponential growth of the search space with increasing problem scales. This article proposes RouteMaker to address the often-overlooked multiagent routing problems involving dedicated multiple depots. RouteMaker leverages role-interaction-based graph neural network (RIGNN) to realize effective locations assignments and integrates an advanced planner to plan travel path for each agent. RouteMaker is trained on small-scale problems and can produce comparable or superior approximate optimal solutions compared with the best heuristic baselines. Notably, the learned RouteMaker generalizes seamlessly to large-scale problems and real-world problems without the need for fine-tuning, delivering significantly higher quality solutions in relatively less time. For scenarios involving 40 agents and 1000 locations, RouteMaker achieves over $600\times $ speed improvement and more than 88% cost reduction, compared with the representative classical heuristic solver (ORTools).

Keywords:

Routing

Optimization

Urban areas

Search problems

Planning

Graph neural networks

Transportation

Supervised learning

Space exploration

Logistics

Combinatorial optimization

deep reinforcement learning (RL)

generalization testing

multiagent routing problems

scalable model

Solving Scalable Multiagent Routing Problems With Reinforcement Learning

Abstract

Journal

Organization