Uma Aproximação para o Problema de Reabastecimento em Conjunto com Capacidades

• Miguel Ángel Marfurt Alarcón Unicamp http://orcid.org/0000-0003-0106-1588
• Lehilton Lelis Chaves Pedrosa Unicamp https://orcid.org/0000-0003-1001-082X

DOI: https://doi.org/10.5753/etc.2021.16368

Resumo

O Joint Replenishment Problem (JRP) envolve um conjunto de varejistas que enfrentam demandas diárias por um item em um horizonte de planejamento. As demandas são satisfeitas por itens previamente mantidos em estoque e reabastecidos por meio de um pedido conjunto para um depósito de um subconjunto de varejistas. O objetivo é decidir quando fazer os pedidos e quais varejistas serão atendidos em cada pedido, de modo a minimizar os custos totais de entrega e armazenamento. No Tree JRP, a cadeia de fornecimento é representada por uma árvore cujas folhas são os varejistas e o custo de entrega para um subconjunto de varejistas é determinado pelo custo da subárvore minimal que os conecta à raiz. Neste trabalho, iniciamos o estudo da variante em que as entregas possuem capacidade limitada e fornecemos uma 6-aproximação baseada em arredondamento de PL.

Palavras-chave: Algoritmos de aproximação, Problema de Estoque e Roteirização, Problema de Reabastecimento em Conjunto com Capacidades

Referências

Bell, W. J., Dalberto, L. M., Fisher, M. L., Greenfield, A. J., Jaikumar, R., Kedia, P., Mack, R. G., and Prutzman, P. J. (1983). Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer. Interfaces.

Cheung, M., Elmachtoub, A., Levi, R., and Shmoys, D. (2015). The submodular joint replenishment problem. Mathematical Programming.

Fukunaga, T., Nikzad, A., and Ravi, R. (2014). Deliver or hold: Approximation algorithms for the periodic inventory routing problem. LIPIcs.

Jiao, Y. and Ravi, R. (2019). Inventory routing problem with facility location. ArXiv.

Nagarajan, V. and Shi, C. (2015). Approximation algorithms for inventory problems withsubmodular or routing costs. Mathematical Programming.

Pedrosa, L. L. C. (2014). Approximation Algorithms for Facility Location Problems and Other Supply Chain Problems. PhD thesis, Instituto de Compução, Unicamp.