The paper proposes a new hybrid approach for solving optimization problems, which integrates the multiple neighborhood search with a multi-agent paradigm. Using the multiple neighborhoods, explored by different heuristics during the search allows one to guide the search and avoid the reaching unsatisfactory results, whenever the search is getting trapped in a local optimum. On the other hand, a multi-agent architecture provides an effective mechanism for solving the problem in parallel. It also assures cooperation between agents (representing search methods) operating on a sharable population of solutions. In order to validate the proposed approach, a computational experiment has been carried out using instances of the capacitated vehicle routing problem.