Multicommodity Distribution System Design by Benders Decomposition
5 pág.

Multicommodity Distribution System Design by Benders Decomposition

Disciplina:Logística11.823 materiais46.035 seguidores
Pré-visualização2 páginas
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órios