Uso dos algoritmos genéticos para a otimização de rotas de distribuição

When the suply chain of medicine logistic is analysed, critical points can be found in the actual model of deliveries to the drugstores, which are the direct clients of the dealer. The clients demand full requests to be delivered on time. In this context, this work starts with the evaluation of the logistic process of the dealer. A field study has been conducted in order to diagnose and develop a core system for vehicle routing. The idea is that an optimized delivering process will reduce costs and, most importantly, the delay on deliveries. Considering the complexity and relevance of the problem in the context of logistics, the chosen approach uses genetic algorithms as the metaheuristic. It is robust enough to tackle the given problem. It is an interactive method with some intelligence in the process of searching for solutions which does not stop on the first local optimum that is found. The problem is to optimize the allocation of deliveries to the available vehicles, taking into account the restrictions of each vehicle, in such a way that the total travelled distance will be minimized. The representation of the solutions and the genetic operators used are based on the travelling salesman problem. In order to produce competitive results on this class of problems, Genetic Algorithms need to be associated with a local method of search. This should be done at each iteration of the algorithm. This allows the generation of better solutions when compared to conventional heuristic methods. The system has been implemented in the Ocaml programming language. Ocaml is a modern language which allow quick development and the code is less error prone, when compared to other programming languages common on the software market, like C, C++ and Java. Known problems from the literature have been used to test the system. The results show that it is possible to obtain optimized routers to solve the problem of delivery of medicines to the clients, taking into account restrictions like capacity of vehicles and transported value limitations.Mestre em CiênciasQuando se analisa a cadeia de abastecimento do setor farmacêutico, identica-se pontos críticos do modelo atual de entregas de medicamentos às farmácias, clientes diretos da distribuidora, que exigem pedidos completos (in full) e nos prazos combinados (on time). Diante deste contexto, este trabalho tem início com a avaliação do processo logístico de uma distribuidora de medicamentos, mediante estudo de campo para diagnosticar e desenvolver um núcleo de roteirização de veículos básico, tendo em vista que a otimização da distribuição irá reduzir custos e principalmente o atraso nas entregas. Mediante a complexidade e relevância do problema no contexto logístico, foi escolhida a abordagem utilizando a metaheurística Algoritmos Genéticos pela sua robustez diante das características do problema. É um método interativo que possui alguma inteligência no processo de busca por soluções que não param no primeiro ótimo local encontrado. O problema é otimizar a alocação das entregas para os veículos disponíveis, levando em consideração as restrições de cada veículo, de tal forma que a distância total percorrida por todos eles seja mínima. A representação das soluções e os operadores genéticos utilizados são baseados no problema do caixeiro viajante. Para que os Algoritmos Genéticos produzam resultados competitivos nessa classe de problemas, precisa ser hibridizado com um método de busca local aplicada a cada geração a determinados indivíduos, por exemplo, um método de descida. Com isso, geram soluções de melhor qualidade se comparadas às soluções geradas pelos métodos heurísticos convencionais. Para a implementação foi utilizada a linguagem Ocaml, cujas características permitem um desenvolvimento mais rápido, sujeito a menos erros, quando comparados à outras linguagens comumente utilizadas no mercado, como C, C++ e Java. Para testar o sistema foram utilizados problemas conhecidos na literatura, cujos resultados demonstram que é possível automatizar a construção de roteiros com custo otimizado, para atender a distribuição de medicamentos aos clientes, levando em consideração diversas restrições, como capacidade de volume e limitação do valor das mercadorias transportadas