A cooperative parallel meta-heuristic for the vehicle routing problem with time windows |
| |
| Affiliation: | 1. CIRRELT, Université de Montréal, C.P. 6128, Succ. Centre-ville, Montréal H3C 3J7, Canada;2. Département de management et technologie, École des sciences de la gestion, U.Q.A.M.;3. Département de mathématiques et génie industriel, École Polytechnique de Montréal;4. Departamento de Informática, Pontifícia Universidade Católica do Rio de Janeiro, Rua Marquês de São Vicente, 225 - Gávea, Rio de Janeiro - RJ, 22451-900, Brazil;5. Dept. Matematică, Informatică şi Ştiinţele Educaţiei, Universitatea “Vasile Alecsandri” din Bacău, Calea Mărăşeşti, nr. 157, Bacău, 600115, România;1. Graduate Program in Electrical Engineering, Federal University of Minas Gerais, Av. Antônio Carlos 6627, 31270-901 Belo Horizonte, MG, Brazil;2. Department of Electrical Engineering, Universidade Federal de Minas Gerais, UFMG, Belo Horizonte, Brazil;3. Departamento de Computação e Sistemas, Universidade Federal de Ouro Preto, UFOP, João Monlevade, MG, Brazil;4. Centre interuniversitaire de recherche sur les réseaux d’entreprise, la logistique et le transport (CIRRELT), Université de Montréal, C.P. 6128, succursale Centre-ville, Montréal, Québec, Canada H3C 3J7 |
| |
| Abstract: | 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 the literature. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
