Formulations and algorithms for a rich production-routing problem

Abstract

Este trabalho estuda um problema enriquecido e integrado de produção e roteamento, que consiste em determinar, a um custo mínimo, os planos de produção e distribuição para um mix de produtos a serem entregues através de rotas percorridas por uma frota heterogênea para suprir diferentes padrões de demanda de clientes espalhados ao longo do tempo enquanto controla os níveis de estoques na planta e nos clientes. O problema ainda permite a postergação das entregas e limita o tempo de viagem de cada veículo. Duas formulações foram propostas para o problema. Dado que os problema cresce rapidamente com o número de clientes, períodos, produtos e veículos, diferentes métodos foram desenvolvidos. Primeiro, são devenvolvidos três métodos híbridos que decompõem o problema em dois níveis usando uma estratégia top-down. O nível superior decides os níveis de produção e inventário e a distribuição dos produtos via CPLEX; enquanto o nível inferior roteia a frota heterogêna heuristicamente para cada período. Os métodos são imbutidos em um escopo da busca local iterativa combinado com novos esquemas de perturbação que operam em ambos níveis tático e operacional. No nível tático, movimentos viáveis modificam os planos de produção, transferindo quantidades produzidas entre diferentes períodos, enquanto no nível operacional as perturbações alteram o arranjo das rotas. Estes algoritmos top-down adotam um novo e implícito custo para as cargas entregues, que reflete sua influência sobre as decisões relativas a produção, inventário e transporte, provendo um importante auxílio no alcance de soluções melhores. Uma mateurística trabalhando com uma estratégia bottom-up é proposta. Ela seleciona operadores para modificar os planos de distribuição e roteamento, que são então reotimizados em sequência. Os melhores planos são então fixados no nível tático do problema. Finalmente, uma aproximação por geração de colunas e provida para alcançar limites inferiores melhores do que os obtidos pelas formulações. Um algoritmo de rotulamento ad hoc é proposto e as colunas são precificadas heuristicamente. Os algorimos foram testas em um conjunto proposto de instâncias e alcançaram resultados melhores e mais rapidamente do que o CPLEX, onde os métodos que focam no nível operacional obtiveram os melhores resultados. Sendo que o algoritmo bottom-up teve desempenho melhor do que os demais.