A cooperative parallel meta-heuristic for the vehicle routing problem with time windows

This paper presents a parallel cooperative multi-search method for the vehicle routing problem with time windows. It is based on the solution warehouse strategy, in which several search threads cooperate by asynchronously exchanging information on the best solutions identified. The exchanges are performed through a mechanism, called solution warehouse, which holds and manages a pool of solutions. This enforces the asynchronous strategy of information exchanges and ensures the independence of the individual search processes. Each of these independent processes implements a different meta-heuristic, an evolutionary algorithm or a tabu search procedure. No attempt has been made to calibrate the individual procedures or the parallel cooperative method. The results obtained on an extended set of test problems show that the parallel procedure achieves Linear accelerations and identifies solutions of comparable quality to those obtained by the best methods in tie literature. (C) 2003 Elsevier Ltd. All rights reserved.