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

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.