Analysis of OpenMP and MPI implementations of meta heuristics for vehicle routing problems
Graphical abstractDisplay Omitted HighlightsWe parallelize a sequential meta heuristic based on simulated annealing.The island and master worker models, and OpenMP and MPI implementations are used.Vehicle routing problems with time windows are used as benchmarks.The performance of multithreading and multi core processing is analyzed.The different implementation alternatives are statistically compared by using ANOVA. 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.
Appl. Soft Comput.