Solucionando o problema de roteamento de veículos capacitado com uso de algoritmos genéticos e paralelismo

Abstract

O Problema de Roteamento de Veículos Capacitado (CVRP) é um clássico problema de otimização combinatória que lida com o roteamento de veículos para atender às demandas de clientes. Rotas são projetadas para partir de um único depósito, formando um conjunto de circuitos hamiltonianos que visa minimizar o custo total, obedecendo às restrições de capacidade de carga e atomicidade. O CVRP é classificado como NP-difícil, onde o espaço de solução cresce exponencialmente com o número de clientes, tornando inviável obter soluções ótimas em tempo hábil. O uso de heurísticas tem se mostrado uma alternativa na construção de algoritmos para a sua resolução. Dentro desse contexto, o Algoritmo Genético (AG) surge como opção promissora, explorada por trabalhos acerca do tema. Neste, propomos uma abordagem baseada no AG para a resolução do CVRP, aprimorando-o com o uso de paralelismo. Um algoritmo foi implementado usando o modelo de ilhas, explorando multithreading e memória compartilhada. Um total de 24 instâncias, divididas em grupos, foram utilizadas como experimentos para a solução desenvolvida, selecionadas a partir de benchmarks na literatura. Foram realizadas variações no número de ilhas durante os testes para avaliar o impacto do paralelismo. Os resultados revelaram uma melhoria na qualidade das soluções à medida que mais ilhas foram adicionadas, apesar do aumento no custo computacional. O AG padrão apresentou uma distância média de 19,79% em relação às soluções ótimas. No entanto, com 2 ilhas, essa distância diminuiu para 16,22%, com 4 ilhas para 14,40%, e com 6 ilhas para 13,23%. O aumento médio no custo de processamento, medido em segundos, variou entre 1,08(1), 1,11(2), 1,13(4) e 1,31(6). Além disso, os resultados também demonstraram uma redução na variância, resultando em maior consistência com o uso de mais ilhas. O método proposto mostrou-se promissor na abordagem de problemas de maior complexidade, particularmente em cenários onde as soluções convencionais encontram limitações. Ele se destaca como alternativa através da escalabilidade horizontal dos recursos computacionais.

The Capacitated Vehicle Routing Problem (CVRP) is a classic combinatorial optimization problem that involves routing vehicles to meet customer demands. Routes are designed to originate from a single depot, forming a set of Hamiltonian circuits aimed at minimizing the total cost while adhering to load capacity and atomicity constraints. CVRP is classified as NP-hard, where the solution space grows exponentially with the number of customers, making it impossible to obtain optimal solutions in a timely manner. In this context, the use of heuristics has proven to be an alternative in constructing algorithms to solve it. Within this framework, the Genetic Algorithm (GA) has emerged as a promising option, as explored by studies on the subject. In this article, we propose a GA-based approach to solving the CVRP, enhancing it with the use of parallelism. An algorithm was implemented using the island model, leveraging multithreading and shared memory. A total of 24 instances, divided into groups, were used as experiments for the developed solution, selected from benchmarks in the literature. Variations were made to the number of islands during the tests to assess the impact of parallelism. The results demonstrated an improvement in the quality of solutions as more islands were added, despite the increase in computational cost. The standard GA exhibited an average distance of 19.79% from the optimal solutions. However, with 2 islands, this distance decreased to 16.22%, with 4 islands to 14.40%, and with 6 islands to 13.23%. The average increase in processing cost, measured in seconds, varied between 1.08(1), 1.11(2), 1.13(4), and 1.31(6). Additionally, the results also indicated a reduction in variance, leading to greater consistency with the use of more islands. The proposed method has demonstrated promise in addressing problems of greater complexity, particularly in scenarios where conventional solutions encounter limitations. It stands out as an alternative due to the horizontal scalability of computational resources.