Algorithm 1
Algorithm 1
复制标题
算法1
DOI：
10.7717/peerj-cs.338/table-7
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
M. C. Cera
中科院分区：
文献类型：
--
作者：
Henrique de Oliveira Gressler;M. C. Cera
路径车辆问题（RVP）是一个难以解决的组合问题，用于改善运输企业的物流以及改善公共道路的交通。为了解决这个问题，随着问题规模的扩大，测试所有组合（强力方法）变得不可行，因为它需要大量的计算时间。遗传算法 (GA) 是元启发式算法，能够在可接受的计算时间内找到解决方案。然而，即使是遗传算法也可能需要大量的计算时间。计算架构的演变和多核扩散成为多线程编程减少 GA 时间的替代方案。本文旨在通过使用 OpenMP 的 GA 并行化来加速 RVP 解决方案，OpenMP 是多线程编程的流行标准。我们的结果显示，四核处理器中的 4 个线程的加速速度高达 2。根据我们实施的 GA，这种增益是有限的。除了性能影响之外，我们还表明 OpenMP 的使用不会影响解决方案的质量。此外，OpenMP 允许 GA 找到更好的解决方案，因为它可以增加一个时间片内的进化数量。
Routing Vehicle Problem (RVP) is a combinatorial problem, hard to solve, used to improve the logistics of transport enterprises as well as to improve the traffic in the public ways. To solve it testing all combinations (brute force method) became unfisible as the problem scale, because it demands a large computing time. Genetic Algorithms (GA) are meta-heuristics able to find solutions in an acceptable computing time. However, even GA can demand a large computing time as they are set. Computional architectures evolution and the multicore difusion became the multithread programming an alternativ to reduce GA time. This article aims to speed up the RVP solution through the GA parallelization using OpenMP, which is a popular standard to multithreading programming. Our results show an speedup up to 2 for 4 threads in a quadcore processor. This gain is limited according to our GA is implemented. Beside the performance impact, we also show that the usage of OpenMP did not affect the solutions quality. Furthermore, OpenMP allow the GA to find better solutions because it make possible to increase the number of evolution in an time slice.