Resumo: Neste trabalho são estudados dois problemas combinatórios que ocorrem ao utilizar uma abordagem hierárquica para definir a estratégia a ser adotada na logística de distribuição de revistas. Tipicamente, a primeira fase da logística envolve a definição da região geográfica que será alocada a cada entregador. O problema de definir estas regiões é denominado problema do distritamento (PD). Na segunda fase da logística, para cada região de entrega, é preciso encontrar uma rota que minimize a distância percorrida pelo entregador. Esta rota deve satisfazer tanto a restrição de capacidade de carga do entregador quanto as restrições de fluxo de revistas, considerando-se as demandas dos pontos de entrega e o estoque nos depósitos. O problema combinatório referente a esta fase é denominado o problema da entrega de revistas (PE). Neste trabalho propõe-se algoritmos heurísticos para ambos os problemas acima, que são modelados por meio de grafos. Para o problema da entrega de revistas é proposto ainda um algoritmo exato do tipo branck-and-cut. Este algoritmo está baseado em uma formulação de Programação Linear Inteira e em desigualdades válidas fortes adaptadas dos problemas de roteamento de veículos e de fluxo em redes com custos fixos. Além disso, propõe-se um Sistema Espacial de Apoio à Decisão (SEAD) baseado em um Sistema de Informação Geográfica (SIG) para a Logística de Distribuição de revistas que pressupõe a integração das soluções dos problemas do distritamento e da entrega. Todos algoritmos propostos são implementados e testados para um amplo conjunto de instâncias. Um protótipo do SEAD proposto é implementado através da integração das heurísticas ao SIG ArcView Ver menos

Abstract: In this work we study two combinatorial problems that arise when a hierarchical approach is used to define the strategy to be adopted in the logistics of magazine distribution. Typically, the first phase of the logistics involves the definition of the geographical region to be assigned to each deliverman. The problem of defining such regions is called the district determination problem. In the second phase of the logistics, to each deliver region, we have to find a route that minimizes the distance traversed by the deliverman. This route must satisfy both the deliverman capacity and the magazine flow constraints, given the demands in the delivery points and the stocks in the depots. The combinatorial problem related to this phase is called the magazine delivery problem. In this work we propose heuristic algorithms for both problems above, which are modeled with graphs. For the the magazine delivery problem we also propose an exact branch-and-cut algorithm. This algorithm is based on an Integer Programming formulation and on strong valid inequalities adapted from the vehicle routing and fixed-charge network problems. Besides, we propose a Spatial Decision Support System (SDSS) based on a Geographical Information System (GIS) for the logistics of magazine distribution that assumes the integration of the solutions of the district determination and magazine delivery problems. All the algorithms proposed are implemented and tested over a wide set of instances. A prototype of the proposed SDSS is implemented via the integration of the heuristics to the GIS ArcView Ver menos