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

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.