Algoritmos geneticos aplicados na abordagem de um problema real de roteirizacao de veiculos

Abstract

Resumo: Neste trabalho é apresentada uma proposta de solução para o problema de roteirização de veículos no transporte dos funcionários de uma empresa. Analisou-se o caso de uma refinaria de petróleo situada na região metropolitana da cidade de Curitiba (PR), cujos funcionários, em sua maioria, residem dentro do município, onde foi efetuado todo o serviço de otimização de rotas. O trabalho foi dividido em cinco fases : Na primeira, foi realizado o cadastramento de todas as residências dos funcionários, chamadas de pontos de parada, em um mapa digitalizado da cidade de Curitiba, obtendo-se assim, as coordenadas geográficas destes pontos. Na segunda fase, utilizando o algoritmo genético GenPMed, aqui proposto, foram estabelecidos p pontos notáveis (p-medianas) dentre os diversos pontos de parada, determinando-se assim as sementes ou depósitos fictícios. Na terceira fase, utilizando a heurística para formação de clusters M-Dep-Cap, designou-se cada um dos demais pontos de parada, a alguma das pmedianas, formando p conjuntos de pontos. A cardinalidade de cada um destes conjuntos é, no máximo, igual a capacidade de cada um dos veículos que serão utilizados no transporte. No caso do problema abordado a frota é homogênea. Na quarta fase, utilizou-se o algoritmo genético GenPCV, para construir uma seqüência para coleta dos funcionários em cada um dos conjuntos determinados na fase anterior. Finalmente, na última fase foram realizados melhoramentos nas rotas iniciais obtidas na quarta fase, utilizando as heurísticas 2-Opt e 3-Opt. Para avaliar as soluções obtidas pelos algoritmos, fez-se alguns ajustes, e os resultados foram comparados com a solução utilizada hoje pela empresa. Pelos resultados obtidos justifica-se a sua implementação

Abstract: In this work it is proposed a solution for the vehicle routing problem to perform the transportation of the employees of a company. It was analysed a case of a petroleum refinery located in the metropolitan area of Curitiba City, whose employees, in its majority, reside inside of Curitiba district, where the whole Service of routes optimization is done. The work is divided in five phases: In the first one, it was performed the registration of ali employees’ residences, called demand points, in a digitalized map of Curitiba City, which allowed to list the geographical coordinates of these points. In the second phase, by using the genetic algorithm GenPMed, proposed in this work, p notable points (referred to as p-medium) were found among the several demand points, determining, by this way, the seeds or dummy depots. In the third phase, by using the heuristic M-DepCap in order to form the clusters, each one of the other demand points, was assigned to some of the p-medium points, forming p groups of points. The number of points of each one of these groups, cannot exceed the capacity of each vehicle that will be used to the transportation. In the case studied the fleet is homogeneous. In the fourth phase, the genetic algorithm GenPCV was used in order to build a sequence that the vehicle has to take to pick up the employees in each demand points for ali the groups established in the previous phase. Finally, in the last phase, improvements were done in the routes of the fourth phase by using the 2-Opt and 3-Opt heuristics. In order to evaluate the Solutions obtained with the use of the algorithms, some fittings were done, as well as a comparison between the solution obtained in this work and the solution used nowadays by the company, showing that the results obtained may be implemented