Formulations and resolution procedures for upgrading hub networks

Zusammenfassung

Hub location problems have become an important stream of research within Location Sciencedue to their relevance in many applications emerging in logistics, telecommunications, andtransportation [1]. This talk presents different formulations for the single-allocation hublocation problem with edge upgrades. In the broad context of network design and optimization,upgrading aims to reduce the transportation costs between sites that are connected by theupgraded edges. Two types of connections are considered to be upgraded: inter-hubs edgesand edges that connect origin/destination sites to hubs.Upgrading may be motivated by different contexts. In telecommunications, upgrading an edgemay involve using a higher speed cable between a pair of servers. Similarly, in logistics andtransportation, upgrading an edge may correspond to using a faster transportation mode,such as using a plane instead of a truck between a pair of cities, thus achieving a reducedtravel time. Another possibility is to redesign a trajectory (e.g. using a highway instead of asecondary road).Formulations for solving the problemWe consider a maximum number of connections that can be upgraded between hubs and amaximum number of connections between spokes (non-hubs) and hubs. This may correspond,for instance, to a limited number of alternative vehicles available for accomplishing theimprovement.We start by considering complete hub networks. Afterward, we extend the work to problemsin which hub network design decisions have also to be made. For the latter, no specifictopology is imposed for the hub-level network. Given that the objective function accounts only for the transportation costs, a constraint is set on the number of hubs to install [2]. These formulations present high computing burden, and therefore, various valid inequalities are included as cuts in branch-and-cut procedures. The methodological developments are computationally tested for two purposes: firstly, to emphasize the relevance of embedding upgrading decisions in single-allocation hub location problems by analyzing the savings achievedand the structural changes in the hub networks after upgrading edges; secondly, to evaluate the effectiveness of the formulations and solution methods for different instances.