Search modes for the cooperative multi-agent system solving the vehicle routing problem

Cooperation as a problem-solving strategy is widely used to build methods addressing complex hard optimization problems. It involves a set of highly autonomous programs (agents), each implementing a particular solution method, and a cooperation scheme combining these autonomous programs into a single problem-solving strategy. Possible form of such cooperation may be based, for example, on adaptive memory methods, where partial elements of good solutions are stored and next combined to create new complete solutions. Alternative approach is based on central memory, where complete elite solutions are exchanged among various agents and/or heuristics. Moreover, cooperatively solving a task is often combined with learning mechanism, where agents adapt their behavior to the new states of environment during the process of solving the problem. The main goal of the paper is to evaluate to what extent a mode of cooperation (synchronous or asynchronous) between a number of optimization agents cooperating through sharing a central memory influences the quality of solutions while solving instances of the Vehicle Routing Problem. The investigated search modes are evaluated using a dedicated cooperative multi-agent system allowing for various modes of cooperation and with the reinforcement learning mechanism implemented in it. (C) 2012 Elsevier B.V. All rights reserved.