Resolução de problemas de roteamento de veículos na entrega de produtos da indústria avícola

Abstract

Resumo: Neste trabalho é apresentada uma proposta de solução para o problema de localização de facilidades e o subseqüente roteamento dos veículos que realizam entregas em uma empresa do setor avícola. Analisou-se o caso de uma empresa situada no município de Maringá, no Noroeste do Paraná. A localização de facilidades é obtida como solução de um problema de pmedianas, visando minimizar a distância média de deslocamento dos caminhões que transportam as mercadorias e, conseqüentemente, realizar o atendimento em tempo hábil com menor custo. Para resolver esse problema são propostos dois métodos, sendo o primeiro, baseado em um algoritmo de Programação Linear Inteira e o segundo, baseado em algoritmos Heurísticos. O método de Programação Linear Inteira fornece uma solução descrevendo quais os caminhões transportam as cargas para as respectivas cidades e a rota a ser percorrida através da solução de um modelo matemático. O método Heurístico fornece o mesmo formato de resposta através de algoritmos para a formação de clusters (agrupamentos). A designação dos pontos às medianas é realizada utilizando-se um algoritmo baseado nas razões entre as duas menores distâncias desses pontos às medianas encontradas. O roteamento, em cada agrupamento, é obtido como solução de um problema dos Múltiplos Caixeiros Viajantes, visando à construção de vários roteiros otimizados que minimizam a distância total percorrida pelos veículos. Foi utilizado, para isso, um algoritmo baseado na inserção de pontos que resultem em economias nos roteiros obtidos. Palavras-chave: p-medianas, roteamento, designação.

Abstract: In this work it is presented a proposal of solution for the problem of localization of facilities and the subsequent routing of the vehicles that carry out deliveries in a company of the poultry business area. The case of a situated company in the district of Maringá, the Northwest of Paraná was analyzed. The localization of facilities is obtained as solution of a problem of p-medians, aiming to minimize the average distance of displacement of the trucks that carry the merchandises and, consequently, to carry out the attendance in skillful time with lesser cost. To solve this problem two methods for the solution are considered, being the first one, based on an algorithm of Integer Linear Programming and second, based on Heuristical algorithms. The method of Integer Linear Programming supplies a solution describing which trucks carry loads to the respective cities and the route to be covered through the solution of a mathematical model. The Heuristical method supplies the same format of reply through algorithms for the formation of clusters (groupings). The designation of the points to the medians is determined using an algorithm based on the ratios between the two shorter distances of these points to detected medians. The routing in each clustering is obtained as a solution to the Multiple Salesman problem, aiming the construction of various optimized routes, which minimize the total distance covered by the vehicles. For this purpose, an algorithm based on the insertion of points was used and which can result in economy regarding the obtained routes. Key words: p- medians, routing, designation.