Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/8652
Type: Tese
Title: Resolvendo problemas de localização de hubs com alocação múltipla em modelagens contínua e discreta tipo p-medianas através da abordagem de suavização hiperbólica
Author(s)/Inventor(s): Gesteira Neto, Claudio Joaquim Martagão
Advisor: Xavier, Adilson Elias
Abstract: As redes hub-and-spoke (HS) constituem um conceito importante para o projeto de sistemas de transporte e telecomunicações. Nelas, o tráfego se origina em cada um de diversos pontos distribuídos no espaço, e tem como destino todos os demais pontos. O tráfego flui através de diversos caminhos (spokes) a partir dos pontos de origem, se concentrando num conjunto menor de pontos (hubs), interconectados através de ligações de baixo custo unitário e grande capacidade, provendo economias de escala, e deles finalmente seguem para seus respectivos destinos. O problema em estudo é o da localização de um determinado número p de hubs, escolhidos no espaço plano contínuo ou, alternativamente, entre os pontos que se quer conectar, para servir como p-medianas. Procura-se encontrar os hubs que formam, junto com os pontos de origem e destino, a rede HS mais barata, ao mesmo tempo atribuindo tráfego a cada um desses hubs, considerando as demandas de tráfego entre cada par de pontos origem-destino e os respectivos custos de transporte. Na formulação adotada, cada ponto pode receber e enviar fluxos através de mais de um hub. A especificação do problema corresponde a uma formulação min–sum–min fortemente não-diferenciável. O método proposto supera essa dificuldade com a estratégia de suavização hiperbólica, que já se provou capaz de resolver com bastante eficiência instâncias grandes de problemas de agrupamento (clusters). A solução é obtida, em última análise, ao se resolver uma sequência de subproblemas diferenciáveis de otimização sem restrições, de baixa dimensão. A consistência do método é mostrada através de um conjunto de experimentos computacionais realizado em espaços contínuos e discretos com grandes problemas hub-and-spoke, de 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 of several points scattered in space and, from each of those points, they can be destined to any of the other points. The traffic flows through several routes (spokes) from the points of origin and is concentrated in a smaller set of points (hubs), interconnected through links with a low unit cost and high capacity, capable of providing economies of scale, and finally flowing from these hubs to their respective points of destination. The problem under study is the location of a certain number p of hubs, chosen in a flat continuous space or, alternatively, among the points that have to be connected, to serve as p-medians. It consists in finding hubs that make up, along with the origin-destination points, the cheaper HS network and, at the same time, to assign traffic to each of these hubs, considering the traffic demands between each pair of points and the transportation costs. In this particular formulation, it is assumed that each point can 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 a hyperbolic smoothing strategy, which has already been proven capable of solving quite efficiently large instances of clustering problems. The solution is obtained, ultimately, 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 in both continuous and discrete spaces, addressing large hub-and-spoke problems with up to one thousand points.
Keywords: Processamento digital de sinais
Distribuições (probabilidade)
Modelos lineares generalizados
Subject CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Program: Programa de Pós-Graduação em Engenharia de Sistemas e Computação
Department : Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia
Publisher: Universidade Federal do Rio de Janeiro
Issue Date: Dec-2017
Publisher country: Brasil
Language: por
Right access: Acesso Aberto
URI: http://hdl.handle.net/11422/8652
Appears in Collections:Engenharia de Sistemas e Computação

Files in This Item:
File Description SizeFormat 
880221.pdf981,88 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.