Solving Scalable Multiagent Routing Problems With Reinforcement Learning

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× speed improvement and more than 88% cost reduction, compared with the representative classical heuristic solver (ORTools).