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 ...