Comparing multicore implementations of evolutionary meta-heuristics for transportation problems

Zusammenfassung

The set of NP-hard problems require vast computational resources to solve exactly. With the aim of overcoming this limitation several heuristic and meta-heuristic approaches have been proposed in the past. However, the performance of these approaches degradates when solving large problem instances of complex problems. Fortunatelly, parallel processing can be applied to obtain better solutions than the sequential algorithm in the same runtime. The traditional fields of improvement in parallelism have been orientated to experimentation on highbudget equipment, such as clusters of computers or shared memory machines thanks to their high-performance and scalability. In recent years, the generalization of multi-core microprocessors in almost all the computing platforms makes it possible to take advantage of parallel processing even for the desktop computer user. This paper analyzes the performance of population-based meta-heuristics using MPI, OpenMP, and hybrid MPI/OpenMP implementations in a workstation having a multi-core processor when solving a vehicle routing problem, one of the major tasks in the context of transportation. The results obtained when using different number of processes/threads show that these parallel implementations produce high quality solutions compared with the sequential algorithm