Localização Contínua de Hubs com Atribuição Múltipla Via Suavização Hiperbólica

Informações:

Publicações do PESC

Título
Localização Contínua de Hubs com Atribuição Múltipla Via Suavização Hiperbólica
Linha de pesquisa
Otimização
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
26/3/2012
Resumo

As redes hub − and − spoke (HS) são um conceito importante para o projeto de sistemas de transporte e telecomunicações. Nelas, o tráfego se origina em cada um de diversos locais distribuídos no espaço, com destino a todos os demais. Os fluxos são feitos através de ligações chamadas de spokes, que os concentram num conjunto de pontos (hubs), que são interconectados entre si por ligações especiais, de baixo custo unitário e grande capacidade. O problema em estudo é o de localizar um determinado número p de hubs, correspondendo a p-medianas, escolhidos no espaço plano contínuo e que formem, junto com os spokes, a rede HS mais barata. É atribuído tráfego a cada hub, considerando as demandas entre cada par de locais e os respectivos custos de transporte, e se permite que cada ponto receba e envie fluxos por mais de um hub. Ao especificar o problema, chega-se a uma formulação min − sum − min fortemente não-diferenciável. O método proposto supera esse problema com a técnica de suavização hiperbólica, que é capaz de resolver eficientemente instâncias grandes de problemas de agrupamento (clusters). A solução é obtida resolvendo-se uma sequência de subproblemas diferenciáveis de otimização sem restrições, de baixa dimensão. Mostra-se que o método é consistente através de uma série de experimentos com até mil pontos. 

Abstract
Hub-and-spoke (HS) networks are an important concept in the design of transportation and  telecommunications systems. In those systems, items originate in each one of several locations distributed in bi-dimensional space (spokes) and are destined to all the other locations. The traffic flows through links called spokes to a set of points (hubs), which are interconnected through special links with low unit cost and high capacity. The problem under study is the location of a certain number p of hubs, corresponding to p-medians, chosen in flat continuous space and making up, along with the spokes, the cheaper HS network. Traffic is assigned to each hub, considering the demands between each pair of locations and the respective transportation costs, and allowing each point to receive and send flows through more than one hub. The problem specification corresponds to a strongly non-differentiable min−sum−min formulation. The proposed method overcomes this difficulty with the hyperbolic smoothing strategy, which has been proven able to solve quite efficiently large instances of clustering problems. The solution is obtained by solving a sequence of low-dimensional differentiable optimization subproblems without constraints. The consistency of the method is shown through a set of computational experiments with up to one thousand points. 

Arquivo
1339703626.pdf
Topo