Otimização por nuvem de partículas para problemas de roteirização de veículos capacitados com frota heterogênea e coleta e entrega simultânea

Abstract

Resumo: Este trabalho apresenta uma nova estratégia de solução para problemas de roteirização de veículos capacitados, com frota heterogênea fixa e entrega e coleta simultânea utilizando a meta-heurística Otimização por Nuvem de Partículas Discreta Adaptada (ONPDA) proposta. O algoritmo Otimização por Nuvem de Partículas (ONP) faz parte de uma área de estudos conhecida como Inteligência de Enxame, que é baseado no comportamento inteligente de revoadas de pássaros, e contempla uma série de algoritmos que simulam o comportamento social encontrado na natureza para aplicações na área de otimização. O modelo proposto difere do ONP clássico, as adaptações propostas estão presentes na codificação das partículas e nas operações estabelecidas. A criação de novas gerações de partículas, a fim de aumentar a diversidade de busca para o problema também foi utilizada. A técnica ONPDA proposta foi aplicada ao Problema do Transporte Escolar em 32 municípios do Estado do Paraná e os resultados dos experimentos computacionais foram comparados com os resultados obtidos com a utilização da heurística ALBH (Adapted Location Based Heuristic). Os resultados apresentados pela metodologia proposta foram superiores à técnica ALBH em 29 dos 32 municípios testados, proporcionando uma economia para estes municípios que variou de 0,10% à 21,37% na quilometragem diária total percorrida. Os resultados encontrados pelo ONPDA foram também comparados à solução exata para o problema executada no Software Lingo aplicado ao problema do Transporte Escolar a quatro municípios do Paraná. Para a solução exata foram escolhidos os menores municípios devido à complexidade computacional da formulação do problema. Os resultados mostraram que o modelo proposto encontrou a solução ótima para três dos quatro municípios testados. A experiência computacional realizada mostrou que o algoritmo desenvolvido obteve soluções de boa qualidade. Os resultados apontam para a efetividade da abordagem proposta para os conjuntos de problemas analisados. Palavras-chave: Otimização por Nuvem de Partículas. Roteirização. Transporte Escolar.

Abstract: This work presents a new strategy for solving problems of capacitated vehicle routing with heterogeneous fixed fleet and delivery and simultaneous collection using meta-heuristic Particle Swarm Optimization Discrete Adapted (PSODA) suggestion. The algorithm Particle Swarm Optimization (PSO) is part of an area of research known as Swarm Intelligence which is based on the intelligent behavior of flight of birds, and comprises a series of algorithms that simulate the social behavior found in nature for applications in the area of optimization. The proposed model differs from classic PSO, suggested adaptations are present in the coding of the particles and on established operations. The development of new generations of particles in order to increase the diversity of search to the problem was also used. The proposed technique PSODA was applied to Problem of School Transportation in 32 municipalities of the State of Paraná and the results of computational experiments were compared with the results obtained from the use of heuristic ALBH (Adapted Location Based Heuristic). The results presented by the proposed methodology were superior in comparison to ALBH technique in 29 of 32 cities tested, providing savings for these counties ranged from 0,10% to 21,37% in the total daily mileage. The results were also compared by PSODA to the exact solution to the problem implemented in software Lingo applied to the problem of the School Transportation in four municipalities of Paraná. Exact solution for the smaller municipalities were chosen due to the computational complexity of the problem formulation. The results showed that the proposed model found the optimal solution in three of four cities tested. The computational experiment conducted showed that the proposed algorithm could obtain good quality solutions. The results show the effectiveness of the proposed approach for sets of analyzed problems. Keywords: Particle Swarm Optimization. Routing. School Transportation.