Agent-based guided local search

The main contribution of the paper is to propose and validate a new hybrid approach for solving combinatorial optimization problems in which guided local search metaheuristic is incorporated into a cooperative multi-agent framework based on the concept of asynchronous teams (A-Teams). Generally, an A-Team assumes that a collection of software agents, each representing a particular problem solving method, cooperate to solve a problem by dynamically evolving a population of solutions. In the suggested implementation each software agent carries out a guided local search. The proposed approach has been extensively validated experimentally on one of the best known combinatorial optimization problem – the vehicle routing problem. The promising results of experiments have confirmed the effectiveness of the suggested approach.

► Cooperative multi-agent framework based on A-Team concept has been proposed.
► Guided local search (GLS) metaheuristic has been incorporated into the system.
► Proposed system has been validated experimentally on VRP instances.
► Positive impact of GLS metaheuristic on results (MRE) has been observed.
► Synergetic effect from cooperative solving instances by agents has been observed.