A parallel multi-neighborhood cooperative tabu search for capacitated vehicle routing problems |
| |
Authors: | Jianyong Jin Teodor Gabriel Crainic Arne Løkketangen |
| |
Institution: | 1. Molde University College, Specialized University in Logistics, N-6411, Molde, Norway;2. School of Management, UQAM & Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation, Montréal, QC, Canada |
| |
Abstract: | This paper presents a parallel tabu search algorithm that utilizes several different neighborhood structures for solving the capacitated vehicle routing problem. Single neighborhood or neighborhood combinations are encapsulated in tabu search threads and they cooperate through a solution pool for the purpose of exploiting their joint power. The computational experiments on 32 large scale benchmark instances show that the proposed method is highly effective and competitive, providing new best solutions to four instances while the average deviation of all best solutions found from the collective best results reported in the literature is about 0.22%. We are also able to associate the beneficial use of special neighborhoods with some test instance characteristics and uncover some sources of the collective power of multi-neighborhood cooperation. |
| |
Keywords: | Routing Parallel metaheuristics Multi-neighborhood Cooperative search Solution pool |
本文献已被 ScienceDirect 等数据库收录! |
|