Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/275817
Type: DISSERTAÇÃO
Degree Level: Mestrado
Title: Algoritmos combinatorios para a logistica de distribuição
Author: Pereira, Ricardo Scachetti
Advisor: Souza, Cid Carvalho de, 1963-
Abstract: 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

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
Subject: Otimização combinatória
Language: Português
Editor: [s.n.]
Date Issue: 1999
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Pereira_RicardoScachetti_M.pdf5.88 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.