Multicommodity Distribution System Design by Benders Decomposition

Prévia do material em texto

Multicommodity Distribution System Design by Benders Decomposition
Descrição do problema:
		O artigo trata de um problema em que várias commodities são produzidas, em vários locais diferentes, cada um destes com capacidades conhecidas. Para determinar o quanto será produzido, é necessário obter informações sobre as demandas por cada commodity. Esta demanda é conhecida, e os dados estão distribuídos por “zonas de consumidor”. Ou seja, a demanda de cada commodity é conhecida para cada zona de consumidor.
		Para satisfazer a demanda por cada commodity, utilizam-se centros de distribuição, também conhecidos como hubs. Portanto, para atender as necessidades por cada commodity, utiliza-se uma navegação via os centros de distribuição e cada zona de consumidor é atendida apenas por um centro de distribuição. Todas as alocações possíveis para cada centro de distribuição são dadas pelo autor do artigo. Além disso, os custos do centro de distribuição são expressos como encargos fixos, que são os impostos para cada local utilizado, mais encargo de variável linear.
		Assim, o objetivo do problema consiste em determinar quais sites devem ser utilizados, quais serão os tamanhos dos centros de distribuição para cada site selecionado, qual zona de consumidor será atendida por cada centro de distribuição e qual deveria ser o fluxo padrão de transportes para todas as commodities.
Descrição das formulações utilizadas:
Parâmetros
i = Índice para commodities
j = Índice para as locais de produção de commodities
k = Índice para cada site de centro de distribuição possível
l = Índice para cada demanda de zona de consumidor
Sij = Fornecimento (capacidade de produção) para cada commodity i na planta j
Dil = Demanda de cada commodity i pela zona de consumidor l
k, k = Mínimo e máximo total permitido anualmente cedido pelo site k para o centro de distribuição
fk = Porção fixa da possessão anual e custo operacional de um site k para um centro de distribuição
cijkl = Custo unitário médio de produção e expedição da commodity i a partir da planta j, através de centro de distribuição, pelo site k para o consumidor da zona l. 
Variáveis
vk = Variável de custo unitário de rendimento de um centro de distribuição pelo site k
xijkl = Variável que denota a quantidade da commodity i para a planta j através do centro de distribuição, pelo site k para o consumidor da zona l
ykl = Uma variável tipo 0 ou 1. Seu valor será 1 se o centro de distribuição k serve o consumidor da zona l e 0 se não
zk = Uma variável tipo 0 ou 1. Seu valor será 1 se o centro de distribuição é adquirido no site k e 0 se não.
Função Objetivo
S.a.
Configuração linear para as restrições ligadas em y e/ou z.
Na Função Objetivo a parte significa o total anual de rendimento do késimo centro de distribuição. A restrição 2 é a restrição de capacidade e a 3 a que estipula ambas a demanda legitima que poderia ser encontrada (quando = 1) e que deve ser 0 para todo ij quando = 0. A restrição 4 especifica que cada zona de consumidores deve ser servida por um único centro de distribuição. Além disso, mantém o total anual de rendimento entre o mínimo e o máximo de ou 0 se o centro de distribuição está aberto ou não. A restrição 5 também enfatiza a relação lógica correta entre y e z. Já a restrição 6 revela apenas a simplicidade notacional.
Ponto de vista do modelo Segundo autor:
		No modelo, foram usados 2 conjuntos de variáveis cujos subscritos são triplos () ligados por uma restrição de conservação de fluxo para cada combinação commodity-centro de distribuição. Essa alternativa sofre com a falta de flexibilidade para algumas aplicações porque ela desconsidera a origem da commodity uma vez que esse chega até o centro de distribuição. Outra característica do modelo é que a zona do consumidor não é permitida para mais de um centro de distribuição, desde que ’s poderia ser 0 ou 1 e não fracional. Assim, cada demanda do consumidor poderia ser satisfeita por um único centro de distribuição ou diretamente a partir da planta de produção. 
		Pode surgir a desvantagem econômica devido à redução de economia de escala no embarque no centro de distribuição para o consumidor. Já que os custos no centro de distribuição são medidos em função do rendimento simplesmente introduzindo como alternativas de centro de distribuição locais com diferentes tamanhos controlados por e , com e especializados. Para isso introduziu-se um pedaço linear de centro de distribuição na função custo com três pedaços que poderiam requerer três alternativas para centros de distribuição (pequeno, médio e grande), cada um com e correspondendo cada pedaço da função custo de centro de distribuição.
		A configuração arbitrária da restrição 6 dá ao modelo um pouco mais de flexibilidade para incorporar muitas das complexidades e peculiaridades encontradas na maioria dos problemas reais. A restrição 6 permite que se aumente e diminua os bounds no número total de CDs abertos permitidos, que se especifique os subconjuntos de centros de distribuição que poderiam ser abertos (no mínimo um), que existe uma relação de precedência pertencente aos centros de distribuição abertos, existe uma restrição da área de serviço obrigatória (se centro de distribuição A está aberto, isso poderia servir o consumidor da zona B), que existem restrições de capacidade mais detalhadas para o tamanho de CD do que os permitidos, ponderados pelo consumo das características de cada commodity ou escritas em restrições separadas ou subconjuntos de commodities, também obtém-se restrições de capacidade de muitos CDs se eles compartilham de fontes comuns ou facilidades, além de restrições como serviço do consumidor (onde tikl é o tempo médio para a entrega da commodity i para a zona do consumidor l depois de receber ordem do CD k, e Di é um bound no atraso médio da entrega da commodity i).
Técnica da solução adotada:
Para resolver economicamente um código de programação linear inteira mista usa-se a decomposição de Benders.
Função Objetivo:
S.a.
 
Especialização da decomposição de Benders:
Passo 0:Selecionar a conversão para o parâmetro 
Passo 1: Resolver o problema mestre corrente
s.a. 
restrições 4, 5 e 6 e
Passo 2: Resolver o subproblema linear
s.a.
restrições 2 e 3 e
Resolvendo, tem-se:
A variante usada:
O 
Análise da Reotimização:
Uma das vantagens da aproximação pela decomposição de Benders é que ela oferece a possibilidade de refazer a relatada em um tempo consideravelmente mais baixo se comparado com o programa rodando individualmente.
As limitações do programa proposto podem ser resolvidas pelo problema dual na versão modificada. Assim, aumentando alguns custos e fazendo mudanças arbitrárias nos valores superiores e inferiores de V.
O problema mestre:
A programação linear de sub-rotina toma grande vantagem se comparada à restrição de bounding 4 e corresponde a outros problemas de estrutura. Isso economiza no uso do núcleo de armazenamento pela geração de colunas compactadas pelas dados arranjados.
O subproblema: a transposição do subproblema é resolvida utilizando um novo primal simplex baseado no algoritmo de fatoração. Os custos de transporte mudam entre sucessivas soluções.
Dados de entrada e armazenamento: O requerimento do núcleo de armazenamento é economizado pelo uso extensivo de sobrecarga, indexação acumulativa e conjunto de dados compactos com modelos de coeficientes que podem ser generalizados quando necessário. Os dados de custo e demanda dos consumidores são a entrada para o programa pré-processador que cria os conjuntos necessários no disco.
Os tipos de configuração para a restrição 6 acomoda a programação corrente incluindo: seleção fixada de reduzindo as versões do problema completo, oferecendo o limite máximo para os CDs abertos, área de serviço obrigatóriose lugar dos CDs.
O resultado teórico sugere uma metodologia geral para melhorar a representação do modelo: A partir dos vários subconjuntos de restrições envolvendo algumas variáveis inteiras, tentando explicitar um derivado complexo dos pontos característicos do invólucro. 
Análise crítica:
Esse artigo objetivou provar que a Decomposição de Benders é eficaz como estratégia computacional para multicommodities estáticas intermediadas por problemas de alocação. O resultado apresentado mostra que são necessárias poucas modificações para verificar a solução a 1 ou 2 décimos da solução ótima. O mesmo tipo de comportamento foi verificado em outra escala cheia de um hospital com 5 classes de commodities, 3 plantas, 67 possibilidades de CDs e 127 zona de consumidores. As razões do porquê a Decomposição de Benders necessita ainda de alguns pequenos cortes para se aproximar da solução ótima não está muito clara no estudo dos autores. Pode-se perceber, então, que o trabalho foi muito útil para melhorar o tempo de processamento de alguns dados para alocação de multicommodities em muitos trajetos desenhados pelos diversos centros de distribuição. No entanto, parece que quanto maior o número de possibilidades de centros de distribuição mais distante o resultado fica da solução ótima. Esse estudo não foi caracterizado no artigo e a distância da solução ótima é muito pequena, talvez não seja um erro significativo do método. 
A análise por decomposição de Benders se mostrou útil para todos os problemas estudados em sala e nesse também foi extremamente eficaz no que tange ao agrupamento dos dados para economizar espaço em disco e para o tempo de resolução do problema computacional fazendo com que as interações sejam rápidas se ao analisar o problema propriamente dito. Mas este artigo indica que mesmo facilitando o número de interações e trazendo os resultados em tempo consideravelmente melhor, ainda é necessário melhorar o modelo para trazer mais flexibilidade para as zonas de consumidores, adotando metodologias sem fixar um CD atendendo um tipo de consumidor. Vale ressaltar também que, mesmo com o problema de flexibilidade, a experiência prática dos autores mostrou um problema passível de aplicação em situações reais com redução do custo e resolução rápida, mas os próprios autores ressaltaram que ainda tem problemas de eficiência e são necessárias algumas poucas modificações para melhorar o desempenho do programa.
Dessa forma, o artigo é um dos mais complexos estudados em sala, pois o número de variantes é alto e as interações de branch e bound ainda dependem de algumas restrições que talvez não foram relatadas. A parte não linear do problema é de difícil resolução e ainda não foi levado em consideração o tempo de latência dos serviços. As aproximações são eficientes, mas ainda são necessárias algumas modificações no modelo, como relatam os próprios autores no último parágrafo do artigo.