Solving Scalable Multiagent Routing Problems With Reinforcement Learning
- 29 July 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Neural Networks and Learning Systems
- Vol. 36 (11) , 19604-19618
Abstract
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
Funding Information
- National Natural Science Foundation of China (62372376, 62102431)
This publication has 24 references indexed in Scilit:
- A hybrid genetic algorithm for the min–max Multiple Traveling Salesman ProblemComputers & Operations Research, 2023
- A bidirectional graph neural network for traveling salesman problems on arbitrary symmetric graphsEngineering Applications of Artificial Intelligence, 2021
- A reinforcement learning approach for optimizing multiple traveling salesman problems over graphsKnowledge-Based Systems, 2020
- Knowledge-guided local search for the vehicle routing problemComputers & Operations Research, 2019
- Simulated Annealing: From Basics to Applications2018
- The vehicle routing problem: State of the art classification and reviewComputers & Industrial Engineering, 2016
- Requiem for the Miller–Tucker–Zemlin subtour elimination constraints?European Journal of Operational Research, 2014
- A quantum-inspired Tabu search algorithm for solving combinatorial optimization problemsSoft Computing, 2013
- Complexity and Approximation1999
- The multiple vehicle routing problem with simultaneous delivery and pick-up pointsTransportation Research Part A: General, 1989