Resolvendo Problemas de Localização de Hubs com Alocação Múltipla de Modelagens Contínua e Discreta Tipo P-Medianas Através da Abordagem de Suavização Hiperbólica
Autores
|
6515 |
47,2366
|
|
|
6516 |
47,2366
|
Informações:
Publicações do PESC
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çc 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 ultima 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.
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 trafic 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 owing 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 trafic to each of these hubs, considering the trafic 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-diferentiable min-sum-min formulation. The proposed method overcomes this dificulty with a hyperbolic smoothing strategy, which has already been proven capable of solving quite eficiently large instances of clustering problems. The solution is obtained, ultimately, by solving a sequence of low-dimensional diferentiable 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.