Modelo híbrido constituído por algoritmo genético e Space Filling Curve aplicado à otimização de rotas veiculares

Abstract

RESUMO: Alinhado à proposta do Mestrado Profissional, este trabalho é aplicado na resolução de um problema real de roteamento existente na Companhia Espírito Santense de Saneamento, que hoje dispõe de um Sistema de Informações Geográficas, mas não possui nenhum módulo ou mecanismo de geração de rotas de atendimento aos seus clientes, os quais abrem, diariamente, em média 2148 solicitações de serviços. Nesse contexto, este trabalho apresenta a proposta de um Algoritmo Híbrido de Otimização, formado pela combinação dos Algoritmos Genéticos e Space-Filling Curves, aplicado a resolução do Problema de Roteamento de Veículos. Além da elaboração de um módulo de geração de rotas automáticas utilizando informações georreferenciadas existente no sistema. Ao longo deste trabalho também é demonstrado a viabilidade do algoritmo híbrido proposto por meio de testes realizados em duas bases distintas de benchmark existentes na literatura. Comparações realizadas demonstram que o algoritmo chegou a alcançar um resultado médio de 12,7% em relação a solução ótima da primeira base e de 4,1% da segunda, em relação a solução ótima. Em complemento, com intuito de reforçar a validação do algoritmo proposto, foram realizadas comparações entre ele e cinco variações do Algoritmo da Otimização da Colônia de Formigas. Nessa comparação, os resultados alcançados demonstram a superioridade do algoritmo híbrido em quase todas as simulações, comprovando a viabilidade do método proposto.

ABSTRACT: Aligned to the proposal of the Professional Master's Degree, this work is applied in the resolution of a real routing problem in the Espírito Santense de Saneamento Company, which now has a Geographic Information System, but does not have any module or mechanism to generate service routes to its clients, who daily open an average of 2148 requests for services. In this context, this work presents the proposal of a Hybrid Optimization Algorithm, formed by the combination of Genetic Algorithms and Space-Filling Curves, applied to the resolution of the Vehicle Routing Problem. In addition to the elaboration of an automatic route generation module using existing georeferenced information in the system. Throughout this work the feasibility of the proposed hybrid algorithm is also demonstrated through tests carried out in two benchmark databases in the literature. Comparisons showed that the algorithm reached an average result of 12.7% in relation to the optimal solution of the first base and of 4.1% of the second one, in relation to the optimal solution. In addition, in order to reinforce the validation of the proposed algorithm, comparisons were made between it and five variations of the Antimony Optimization Algorithm. In this comparison, the obtained results demonstrate the superiority of the hybrid algorithm in almost all the simulations, proving the feasibility of the proposed method.