Collaborative & Bi-directional Communication in Multi-Agent Metaheuristic Optimization

Abstract

This study introduces a Collaborative Multi-Agent Metaheuristic System for solving combinatorial optimization problems, using the Capacitated Vehicle Routing Problem (CVRP) as a case study. The system integrates both single-solution metaheuristics (Simulated Annealing, Tabu Search, Hill Climbing) and population-based metaheuristics (Genetic Algorithm, Particle Swarm Optimization, Golden Ball Algorithm, Ant Colony Optimization) to balance intensification and diversification. Agents cooperate by asynchronously sharing solutions through a common pool, enabling flexible communication without direct messaging. This collaborative approach enhances robustness, adaptability, and solution diversity while preventing premature convergence. We compare this to a Bi-directional communication protocol where population-based agents generate solutions that single-solution agents improve iteratively via direct exchanges. Experimental evaluation on benchmark CVRP instances shows the proposed Multi-Agent System outperforms individual metaheuristics and achieves competitive or superior results with simpler communication management, demonstrating its effectiveness and scalability for complex optimization problems.