Analysis of OpenMP and MPI implementations of meta-heuristics for vehicle routing problems

The parallelization of heuristic methods allows the researchers both to explore the solution space more extensively and to accelerate the search process. Nowadays, there is an increasing interest on developing parallel algorithms using standard software components that take advantage of modern microprocessors including several processing cores with local and shared cache memories. The aim of this paper is to show it is possible to parallelize algorithms included in computational software using standard software libraries in low-cost multi-core systems, instead of using expensive high-performance systems or supercomputers. In particular, it is analyzed the benefits provided by master-worker and island parallel models, implemented with MPI and OpenMP software libraries, to parallelize population-based meta heuristics. The capacitated vehicle routing problem with hard time windows (VRPTW) has been used to evaluate the performance of these parallel strategies. The empirical results for a set of Solomon's benchmarks show that the parallel approaches executed on a multi-core processor produce better solutions than the sequential algorithm with respect to both the quality of the solutions obtained and the runtime required to get them. Both MPI and OpenMP parallel implementations are able to obtain better or at least equal solutions (in terms of distance traveled) than the best known ones for the considered benchmark instances. (C) 2016 Elsevier B.V. All rights reserved.