Orientador: Lehilton Lelis Chaves Pedrosa

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação

Resumo: Algoritmos de aproximação são algoritmos polinomiais para problemas de otimização que produzem soluções com uma certa garantia de qualidade. Para muitos problemas relevantes, não se conhecem algoritmos exatos eficientes e muitos deles são NP-difíceis. Desse modo, algoritmos de aproximação...

Resumo: Algoritmos de aproximação são algoritmos polinomiais para problemas de otimização que produzem soluções com uma certa garantia de qualidade. Para muitos problemas relevantes, não se conhecem algoritmos exatos eficientes e muitos deles são NP-difíceis. Desse modo, algoritmos de aproximação são uma alternativa para encontrar soluções boas para esses problemas. Neste trabalho, investigamos problemas que integram questões de inventário e roteamento. Mais especificamente, estudamos o Inventory Routing Problem (Problema de Estoque e Roteirização, IRP). Dado um ou mais depósitos, uma frota de veículos, um conjunto de clientes e um plano de horizonte de demandas de T períodos para cada cliente, o objetivo é formar entregas de forma que os veículos entreguem todas as demandas dos clientes a tempo, minimizando a soma dos custos de transporte e dos possíveis custos de armazenamento. Nossa contribuição é dividida em duas partes. Primeiro, estudamos o Inventory Access Problem (IAP), uma versão particular do IRP em que um único cliente enfrenta demandas em um horizonte de planejamento discreto e o objetivo é encontrar uma política de abastecimento que minimize a soma dos custos de transporte e armazenamento. Embora a versão não capacitada seja polinomial, apenas uma 3-aproximação é conhecida para o caso capacitado. Nós melhoramos esse fator para 2,619 e, como resultado direto, também diminuímos o melhor fator conhecido para o problema chamado Star Inventory Routing Problem with Facility Location (SIRPFL), que é uma extensão do IAP com vários depósitos e clientes e cujas soluções correspondem a rotas em formato de estrelas. Além disso, estudamos os casos capacitados do IAP e do SIRPFL em que todos os itens de uma mesma demanda devem ser entregues na mesma viagem e diminuímos os melhores fatores conhecidos também para essas versões. Em seguida, estudamos o Tree Joint Replenishment Problem (Tree JRP), outra versão particular do IRP em que um conjunto de clientes enfrenta demandas diárias por itens em um horizonte de planejamento discreto. As demandas são satisfeitas por itens já mantidos em estoque, que é reabastecido a partir de pedidos para um depósito que servem um subconjunto de clientes simultaneamente. No Tree JRP, a cadeia de abastecimento é representada por uma árvore cujas folhas são os clientes e o custo de um pedido para um subconjunto de clientes é determinado pelo custo de uma subárvore mínima que os conecta à raiz. O objetivo é decidir quando fazer os pedidos e quais clientes farão parte de cada pedido, de modo que os custos totais de transporte e armazenamento sejam minimizados. Neste trabalho, começamos o estudo da variante cujos pedidos têm capacidade limitada e fornecemos uma 5-aproximação baseada em arredondamento de PL. Destacamos que essa é a primeira aproximação tanto para o caso em que as demandas podem ser divididas em várias viagens, quanto para o caso em que a demanda de um período não pode ser dividida

Abstract: Approximation algorithms are polynomial algorithms for optimization problems that produce solutions with a certain quality assurance. For many interesting optimization problems, no exact efficient algorithms are known and many of them are NP-hard. Therefore, approximation algorithms are an...

Abstract: Approximation algorithms are polynomial algorithms for optimization problems that produce solutions with a certain quality assurance. For many interesting optimization problems, no exact efficient algorithms are known and many of them are NP-hard. Therefore, approximation algorithms are an alternative to find good solutions for these problems. In this work, we investigate problems that integrate inventory and routing decisions. More specifically, we study the Inventory Routing Problem (IRP). Given one or more depots, a fleet of vehicles, a set of customers, and a demand planning horizon of T periods for each customer, the objective is to make trips in a way that the vehicles deliver all customer demands on time, minimizing the sum of transportation and storage costs. Our contribution is divided into two parts. First, we study the Inventory Access Problem (IAP), a particular version of the IRP where a single client faces demands in a discrete planning horizon and the goal is to find a supply policy that minimizes the sum of transportation and storage costs. Although the uncapacitated version is polynomial, only a 3-approximation is known for the capacitated case. We improved this factor to 2.619 and, as a direct result, we also improved the best factor for the problem called Star Inventory Routing Problem with Facility Location (SIRPFL), which is an extension of the IAP with many depots and customers and whose solutions have the format of a star. Moreover, we study the capacitated cases of IAP and SIRPFL in which all items of a single demand must be delivered by the same trip, and we improved the best-known factors for these versions as well. Next, we study the Tree Joint Replenishment Problem (Tree JRP), another particular version of the IRP where a set of customers faces daily demands for items in a discrete planning horizon. The demands are satisfied by items already held in stock and replenished by joint orders for a depot that serve a subset of customers simultaneously. In the Tree JRP, the supply chain is represented by a tree whose leaves are the customers, and the cost of an order for a subset of customers is determined by the cost of a minimum subtree that connects them to the root. The goal is to decide when to make the orders and which customers will be part of each order, so the total ordering and storage costs are minimized. In this work, we start the study of the variant where the orders have limited capacity, and provide a 5-approximation that is based on the LP rounding technique. We emphasize that this is the first approximation for the splittable version, when a demand can be divided into multiple trips, as well as for the unsplittable version, when one period's demand must be delivered in a single trip

Requisitos do sistema: Software para leitura de arquivo em PDF