IEEE Transactions on Neural Networks and Learning Systems · 2025 · 22 citations · 21 references
ComputingComputer ScienceTransportation PlanningArtificial IntelligenceMachine LearningPath PlanningCombinatorial OptimizationHeuristic SearchMulti-agent SystemsReinforcement LearningRoute PlanningRoutingAgent-based OptimizationGraph-based Multi-agent LearningMulti-agent LearningMulti-agent Path PlanningMulti-agent PlanningRouting ProblemsScalable Planning AlgorithmsScalable Routing
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).
21
DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2023 · 76.3K citations · Full text
Metaheuristics in combinatorial optimization
Christian Blum, Andrea Roli · ACM Computing Surveys · 2003 · 3.1K citations