A parallel algorithm for the vehicle routing problem with time window constraints

In this paper, we describe a new parallel tabu search heuristic for the vehicle routing problem with time window constraints. The neighborhood structure we propose is based on simple customer shifts and allows us to consider infeasible interim-solutions. Similarly to the column generation approach used in exact algorithms, all routes generated by the tabu search heuristic are collected in a pool. To obtain a new initial solution for the tabu search heuristic, a fast set covering heuristic is periodically applied to the routes in the pool. The parallel heuristic has been implemented on a Multiple-Instruction Multiple-Data computer architecture with eight nodes. Computational results for Solomon's bench-mark problems demonstrate that our parallel heuristic can produce high-quality solutions.