Abordagem de um problema de entrega de jornais a assinantes por métodos heurísticos e estatísticos

Abstract

Resumo: Existe uma preocupação constante por parte das empresas jornalísticas com respeito ao tempo necessário para os jornais serem entregues a seus assinantes, pois é preciso que estes os recebam em suas casas antes de sua saída para o trabalho. Neste trabalho, se analisou um problema real existente em uma empresa de Curitiba e se procurou, inicialmente, traduzi-lo de forma matemática. Buscou-se, então, uma solução para a melhoria do sistema em vigor, com a pesquisa de locais que fossem mais adequados para servirem como postos de distribuição. Com o intuito de reduzir os tempos computacionais demandados para encontrar uma solução ótima quando são utilizadas as técnicas da Programação Linear Inteira, foram empregados alguns procedimentos heurísticos, obtendo-se soluções que, embora boas, possam não ser as melhores. Foi abordado o algoritmo de Teitz e Bart, que mostrou ser eficiente e simples de ser implementado; depois se estudou a meta-heurística Simulated Annealing, que exigiu tempos computacionais mais elevados, porém atingindo os mesmos resultados do algoritmo anterior; foi estudado também o Algoritmo Genético, que apresentou resultados inferiores aos conseguidos pelos dois primeiros algoritmos. Visando achar a melhor forma dos bairros serem atendidos pelos postos de distribuição, foram estudados ainda alguns métodos estatísticos da Análise de Agrupamentos; os resultados alcançados, entretanto, se mostraram menos apropriados para o caso em estudo, em virtude de não ser considerado o número de assinantes em cada bairro. Após serem definidas as melhores soluções, foram comparados esses resultados com o sistema atualmente empregado pela empresa, tendo sido constatada uma redução significativa na soma ponderada das distâncias a serem percorridas pelos entregadores

Abstract: Joumalistic companies are always worried about the time of delivery of the daily newspapers to their subscribers, because they need to receive them in their houses before the exit to the work. In this study an real problem was analyzed in a company located in Curitiba and it was sought, initially, to translate it in a mathematical way. Then, a solution was looked for improving the current system by searching the appropriate places for serving as points of distribution and by a new grouping of the neighborhoods supplied by the points. Some heuristic procedures were used, in order to reduce computational times by finding the solution through the techniques of Lineal Programming, getting Solutions that can be not the best ones; firstly the algorithm of Teitz and Bart were analyzed and showed efficiency, leading to the best Solutions; then the Simulated Annealing algorithm was studied and demanded higher computacional times to reach the same Solutions of the previous algorithm; Genetic Algorithm was also studied and presented worst results than those gotten by the first two algorithms. Seeking to analyze the best form of the neighborhoods be assisted by the distribution points, some statistical methods of Clusters Analysis was studied; however, the reached results were less appropriate for the case in study, because the number of subscribers was not considered in each neighborhood. After the best Solutions were defined, those results were compared with the system used currently by the company; an important reduction in the total distance to be traveled by the newspapers deliverers was verified