Solving Scalable Multiagent Routing Problems With Reinforcement Learning.

Area of Science:

• Operations Research
• Artificial Intelligence
• Computer Science

Background:

• Multiagent routing problems (MARPs) are critical in logistics and transportation.
• Scalability challenges arise from the exponential growth of search spaces in MARPs.
• Existing methods struggle with MARPs involving multiple dedicated depots.

Purpose of the Study:

• Introduce RouteMaker, a novel system for multiagent routing problems with multiple dedicated depots.
• Develop an effective location assignment and path planning strategy for agents.
• Enable generalization to large-scale and real-world scenarios without fine-tuning.

Main Methods:

• Leverage a role-interaction-based graph neural network (RIGNN) for location assignments.
• Integrate an advanced planner for agent travel path optimization.
• Train the model on small-scale problems for generalization.

Main Results:

• RouteMaker produces optimal solutions comparable or superior to heuristic baselines.
• Achieves significant speed improvements (over 600x) and cost reductions (over 88%) compared to ORTools.
• Demonstrates seamless generalization to large-scale (40 agents, 1000 locations) and real-world problems.

Conclusions:

• RouteMaker offers a highly effective and efficient solution for multiagent routing problems with multiple depots.
• The RIGNN approach enables robust generalization and superior performance on complex routing tasks.
• RouteMaker significantly advances the state-of-the-art in solving large-scale, real-world routing challenges.