Network hub locationmodels, algorithms, and related problems

Resumen

Network hub location problems (HLPs) define a well-known family of difficult problems within discrete location, In the case of HLPs several nodes (locations) in a transportation or communication network send and receive some commodity. The performance of these systems can be improved by using transhipment points (hubs), where the flow between origin-destination pairs are consolidated and re-routed to their destinations. Broadly speaking HLPs consist of locating hubs on a network and designing the hub network so as to minimize the total flow cost. The aim of this dissertation is the development of models and algorithms for solving some classes of HLPs and one particular related problem namely, the Optimum Communication Spanning Tree Problem. One of the objectives of this dissertation is to study the Capacitated Hub Location Problem with Single Assignment (CHLPSA). This problem considers the case when there is a limited capacity on the incoming flow at the hubs. Also, there is a fixed set-up cost for establishing each hub and each non-hub node is allocated to only one hub. The objective is to minimize the fixed costs of locating hubs plus the routing costs of the overall network. We propose an exact solution method for obtaining optimal solutions to the optimal value of the problem. On the one side, we develop two heuristics methods, a Lagrangean heuristic and a greedy randomized adaptive search procedure, to obtain feasible solutions and thus upper bounds for the CHLPSA. On the other side, we present two different relaxations methods, a Lagrangean relaxation approach and a column generation algorithm, for obtaining lower bounds of CHLPSA. Finally, we embedded all these procedures into an exact branch-and-price algorithm to obtain optimal solutions for the CHLPSA. Also, in this dissertation we propose the Tree of Hubs Location Problem (THLP). It is a single-allocation hub location problem where a fixed number of hubs has to be located on a network, with the particularity that it is required that the hubs are connected by means of a tree. The objective is to minimize the total flow cost, subject to the above assumptions. We propose several integer programming formulations for the THLP, we compare and analyze them, based on its natural linear programming bounds and the time needed to obtain optimal solutions. Given that the computational effort considerably increases with the size of the instances when lower bounds are obtained by solving LP relaxations with a commercial solver, we propose a Lagrangean relaxation approach to obtain tight lower and upper bounds for the THLP, based on the most promising of the proposed formulations. The last part of the dissertation is devoted to the Optimum Communication Spanning Tree Problem (OCT). This problem, which is a particular case of the Network Design Problem, consists of finding a spanning tree for serving a set of communication requirements between pairs of nodes at a minimum total cost. The OCT problem appears as a subproblem in some Network Hub Location Problems. In particular, in the THLP, when both the set of hubs and the allocation pattern of nodes to hubs are known, the problem can be polynomially transformed into an OCT. We propose several integer programming formulations for the OCT and theoretically analyze them, based on its natural linear programming relaxation bounds. Given that the computational effort considerably increases with the size of the instances when lower bounds are obtained by solving LP relaxations with a commercial solver, we propose a Lagrangean relaxation based on the most promising of the proposed formulations.