BENDERS DECOMPOSITION FOR THE UNCAPACITATE

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Benders decomposition for the uncapacitated 
multiple allocation hub location problem
1 Descriçao sucinta do problema
Nos sistemas de telecomunicação e transporte, o problema de localização de Hubs não capacitado com alocação múltipla (UMAHLP), é aplicável quando nós precisamos fluir produtos ou informação entre diversos pares de origem-destino. Em vez de estabelecer uma conexão direta do nó de origem a seu destino, os fluxos são concentrados com os outros nas facilidades chamadas hubs. Estes fluxos são transportados nas ligações estabelecidas entre hubs, o hub então recebe o fluxo, divide e despacha aos seus destinos. Os sistemas com esta “cara” são nomeados hub-and-spoke (HS). São projetados para explorar as economias de escala atingíveis com o uso compartilhado das ligações entre hubs. Conseqüentemente, o problema é encontrar a rede menos cara de HS, selecionando hubs e atribuindo o tráfego a eles, dado as demandas entre cada par de origem-destino e os respectivos custos do transporte.
Os sistemas de HS são apropriados quando os produtos (dados da telecomunicação, passageiros ou cargas de pacote) entre um par origem-destino dos nós de uma rede não podem ser enviados por uma conexão exclusiva direta ou porque esta é cara de mais para ser realizada.
Em redes de HS, o tráfego entre dois nós não é enviado diretamente, mas é distribuído geralmente com um ou dois nós, designados como hubs, antes de ser entregue a seu destino final. Esses hubs centralizam o produto e reduzem a instalação da rede e os custos operacionais substituindo as conexões diretas de um par de origem–destino por ligações indiretas. O projeto de redes de HS consiste geralmente na seleção de que nós da rede estarão agindo como hubs e em como os outros nós serão alocados aos hubs. 
O projeto de tais redes tem que ser feito com cuidado, uma vez que envolve quantidades grandes de recursos e tem um impacto fundamental nos custos operacionais mais tarde. Assim, gastando algumas horas para resolver problemas enormes da rede de HS de forma ótima ou para aproximar-se do ótimo é considerado razoável. 
2 Descrição rápida das formulações utilizadas
No modelo abaixo, a função objetivo (1) minimiza o custo total. O custo total é a soma dos custos de instalação dos hubs com os custos do transporte. As restrições (2) garantem que o fluxo o qual atravessa um hub acontece somente se esse hub for instalado. As restrições (3) asseguram que a soma do fluxo que sai de i e vai para j passando por todos os pares de hub k-m é igual a demanda do par i-j. Se somente um cubo estiver sendo usado, nós temos k = m. As restrições (4) faz com que o fluxo que sai de i e vai para j passando por qualquer par de hub k-m é não negativo, e as restrições (5) restringirem o yk a ser binária 0 ou 1 ( 1 se o hub k pertencente a K é instalado e 0 caso contrário).
 
OBS: também é possível modelar esse problema considerando o fluxo Xijkm como sendo uma fração variando de 0 a 1. Para isso basta dividir o lado direito das restrições 2 e 3 por Wij e multiplicar os custos da função objetivo por Wij. Esse novo problema é de mais rápida solução computacional.
3 Relatório Rápido da técnica de solução adotada
Para resolver o problema proposto acima para grande escala foi utilizado o método de decomposição de Benders. O problema é então projetado no espaço y (6 a 9 abaixo). A variável y deixa de ser variável e passa a ser um parâmetro fixado. A partir daí gera-se o problema dual projetado (10 a 14 abaixo). E então obtém-se o Problema Mestre de Benders (16 a 20 abaixo).
 
 
Durante o artigo os autores mostram além do algoritmo de decomposição de Benders clássico outros dois algoritmos (Multi-cortes e o Modificado). Todos os três algoritmos mostraram ser ferramentas poderosas da engenharia, podendo resolver problemas de grande escala sob 10 horas de máquina.
4 Comentário Crítico
	A formulação proposta é sem dúvida extraordinária e permitiu a resolução de problemas até então tido como não resolvíveis ou que demorava um tempo de máquina muito alto para se resolver. Entretanto o modelo ainda apresenta suas limitações:
Não há restrições de capacidade explícita dos hubs. Assim uma solução tida como ótima pode ser não viável, caso ultrapasse a capacidade do hub. Esse problema pode ser resolvido com a adição de uma restrição de capacidade, mas ela piora muito o problema que passa a não ser mais decomponível no espaço Y. Para resolver esse problema uma solução seria tratar a inviabilidade como custo.
A demanda considerada é dada a priori (determinística). Mas no mundo real a demanda está sujeita a variações tanto positivas quanto negativas, o problema não considera essas variações. Uma solução possível seria a inclusão de uma demanda estocástica, mas que também pioraria muito a resolução do problema
O problema funciona bem para sistemas em projeto. Mas se for para resolver um problema que já existem hubs concentradores, seria interessante verificar os custos de desinstalar um hub já instalado e toda sua infra estrutura e instalar um outro hub.
Uma versão hibrida da decomposição de Benders clássica com a multi cortes sugere ser um caminho prometedor.