Publicação: Uso dos algoritmos genéticos para a otimização de rotas de distribuição
Carregando...
Arquivos
Tipo do documento
Data
Direito de acesso
Área do conhecimento
CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA
Título da Revista
ISSN da Revista
Título de Volume
Autores
Orientador
Coorientador
Resumo
Quando 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.
Abstract
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.
Palavras-chave
Roteirização, Algoritmo genético, Otimização, Routing, Genetic algorithm, Optimization., Otimização combinatória, Caminhões - Rotas - Levantamentos, Medicamentos - Transporte, Logística empresarial - Estudo de casos
Citação
MALAQUIAS, Neli Gomes Lisboa. Uso dos algoritmos genéticos para a otimização de rotas de distribuição. 2006. 113 f. Dissertação (Mestrado em Engenharias) - Universidade Federal de Uberlândia, Uberlândia, 2006.