18 ago 2021
14:00 Defesa de Mestrado Integralmente a distância
Tema
Algoritmos de aproximação para problemas de estoque e roteirização
Aluno
Miguel Angel Marfurt Alarcon
Orientador / Docente
Lehilton Lelis Chaves Pedrosa
Breve 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 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 é divida 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,618 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 um item 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 6-aproximação para o caso que as demandas podem ser divididas em várias viagens e uma 5-aproximação para o caso que todas as demandas devem ser entregues na mesma viagem, ambas baseadas na técnica de arredondamento de PL.
Banca examinadora
Titulares:
| Lehilton Lelis Chaves Pedrosa | IC/UNICAMP |
| Mário César San Felice | DC/UFSCar |
| Fábio Luiz Usberti | IC/UNICAMP |
Suplentes:
| Kelly Cristina Poldi | IMECC/UNICAMP |
| Rafael Crivellari Saliba Schouery | IC/UNICAMP |