Incomplete hub location networks with upgrading

Resumen

We will talk about different formulations for the uncapacitated single-allocation hub location problem with upgraded connections and incomplete hub networks. Upgrading is understood as an improvement of an edge performance in the sense that the cost of time to traverse that edge is reduced attending to a budget constraint. Two types of connectionsare considered to be upgraded: inter-hubs edges and edges that connect origin/destination points to hubs. A flow-based formulation is proposed for this problem where the flow sent from an origin to a destination can be routed using more than two hubs since the triangle inequality property can be lost when upgrades are made on edges. The network obtained must be connected since any site can send flow to any other site. For the resulting formulations, valid inequalities and ad-hoc preprocesing phase is developed to strengthened them. We report on a series of computational test performed to assess the models proposed and their enhancements.