Single-allocation hub location problems with capacity decisions and balancing requirements

摘要

In this paper an extension of the capacitated single-allocation hub location problem is considered in which the capacity of the hubs is part of the decision making process and also balancing requirements are imposed to the network. The decisions to be made comprise i) the selection of the hubs, ii) the allocation of the non-hub nodes to the hubs, iii) the flow shipment through the sub network defined by the hubs and iv) the capacity level at which each hub should operate. In the latter case, for each potential hub, a set of available capacities is considered among which one can be chosen. The objective is to minimize the total cost which includes the setup cost for the hubs as well as the flow shipment cost. Economies of scale are assumed for the costs. Balancing requirements are imposed to the network. In particular, a value is considered for the maximum difference between the maximum and minimum number of spoke nodes that are allocated to the hubs. Two mixed-integer linear programming formulations are proposed for this problem. In order to evaluate the possibility of solving the problem to optimality using a commercial solver, a set of computational experiments were performed which results are reported. The experiments also include an analysis of the gap of the bounds provided by linear relaxation.