A Parallel Hybrid Evolutionary Metaheuristic for the Vehicle Routing Problem with Time Windows

The vehicle routing problem with time windows (VRPTW) is an extension of the well-known vehicle routing problem with a central depot. The objective function of the VRPTW considered here combines the minimization of the number of vehicles (primary criterion) and the total travel distance (secondary criterion). In this paper, a two-phase procedural approach for solving the VRPTW is parallelized. The aim of the first phase is the minimization of the number of vehicles by means of a (1, λ)-evolution strategy, whereas in the second phase the total distance is minimized using a tabu search algorithm. The parallelization of this sequential hybrid procedure follows the concept of cooperative autonomy, i.e., several autonomous sequential solution procedures cooperate through the exchange of solutions. However, exchanges of solutions lead to the corresponding jumps in the solution space only if certain acceptance conditions are met. The good performance of both the sequential and the parallel approach is demonstrated by means of well-known and new benchmark problems.