Node-ejection chains for the vehicle routing problem: Sequential and parallel algorithms

We present a Tabu search algorithm for the vehicle routing problem (VRP) under capacity and distance restrictions. The neighborhood search is based on compound moves generated by a node-ejection chain process. During the course of the algorithm, two types of neighborhood structures are used and crossing infeasible solutions is allowed. Then, a parallel version of the algorithm which exploits the moves' characteristics is described. Parallel processing is used to explore the solution space more extensively and to accelerate the search process. Tests are carried out on a SUNSparc workstation and the parallel algorithm uses a network of four of these machines. Numerical tests indicate that the sequential version of the algorithm is highly competitive with the best existing heuristics and that the parallel algorithm outperforms all of these algorithms. (C) 2001 Elsevier Science B.V. All rights reserved.