Algoritmos para a resolução do problema de estoque e roteamento de veiculos

Este trabalho enfoca a resolução do problema de estoque e roteamento de veículos (PERV). O problema é modelado matematicamente como um problema de otimização combinatorial onde o problema do longo prazo é transformado em um de curto prazo, incluindo custos para representar a influência das decisões atuais no futuro. A estocasticidade da demanda dos clientes é considerada através de estoques de segurança, calculados em função da distribuição de probabilidade da demanda de cada cliente e da relação de custo entre uma entrega normal e uma entrega de emergência. São apresentadas três formulações para o problema. As duas primeiras não incluem restrições sobre a duração das rotas e estão baseadas no problema de roteamento de veículos (PRV) ou no problema do caixeiro viajante (PCV). A terceira formulação incorpora restrições sobre a duração total das rotas executadas por um veículo. A metodologia de resolução utilizada parte de uma das formulações apresentadas. Para as duas primeiras formulações basta simplificar a função objetivo para obter um problema de atribuição generalizado. Em seguida, são resolvidos os subproblemas resultantes, que podem ser PRVs ou PCVs, para obter uma solução inicial. Na terceira formulação são relaxadas as restrições de disponibilidade de atendimento dos veículos para que possa ser empregada uma solução obtida por urna das formulações anteriores. Em seguida, é utilizada uma heurística para encontrar o conjunto das rotas atendidas em cada veículo. Duas heurísticas são sugeridas para a melhoria da solução inicial: busca tabu com penalidades e trocas simultâneas. São apresentados resultados das heurísticas propostas para o problema. Também é feita a comparação entre as soluções do modelo dinâmico proposto e do modelo periódicoThis thesis focuses on the Inventory Routing Problem (IRP). It is modeled as a combinatorial optimization problem where the long-term issues are reduced to the short term with the inclusion of special costs that represent the influence of present decisions in the future. The client' demands stochastic nature are treated by safety stock levels, which are obtained by means of the demands probability distribution and the ratio between the normal and emergency delivery costs. Three problem formulations are presented. The first two do not include restrictions on the length of routes and are based on the Vehicle Routing Problem (VRP) and the Traveling Salesman Problem (TSP). In the third formulation, restrictions on the vehicles total workload are added. To solve the IRP we begin with one of the formulations. For the first two, the objective function is simplified in order to produce a Generalized Assignment Problem, then, the subproblems, VRPs or TSPs, are solved and an initial feasible solution is obtained. For the third formulation we also have to relax the restrictions on the total workload of the vehicles to obtain an initial solution using one of the earlier formulations. To assign the routes to the vehicles a heuristic algoritm is used. Two heuristcs for the improvement of the initial solutions are suggested: tabu search with penalties and simultaneous exchanges. Computational results are presented for the two heurists. Finally, we compare two approaches for the IRP, the proposed dinamic model and the periodic mode