Abstract:
In this paper, we consider the capacitated single allocation p-hub median problem generalized with fixed costs of opening facilities. The quadratic mathematical formulation of this problem is first adapted and then linearized. The typical approaches of linearization result in a high size complexity, i.e., having a large number of variables. To downsize the complexity, variables of the formulation are analyzed and some preprocessing approaches are defined. An estimated formulation is then developed to approximately solve large instances of the problem by commercial optimization solvers. The basic idea of this formulation is mapping the linearized formulation of the problem to a new formulation with fewer variables and a modified objective function. The efficacy of this formulation is shown by a computational study, where the estimated formulation is compared to a modified genetic algorithm from the literature. Results of computational experiments indicate that the estimated formulation is capable of generating good solutions within reasonable amount of
time.
Machine summary:
"The literature includes several mathematical formulations for the single allocation hub location problems, but they cannot solve large instances of the problem.
The estimated formulation presented in this paper has the following three desirable characteristics: It is easily solved within reasonable amount of time even for larger instances of the problem with 200 nodes.
However, the contribution of our research is developing the concept of estimated formulation to solve larger instances of a variety of single allocation hub location problems.
Related literature In this section, we review some heuristic procedures as well as mathematical programming formulations developed to solve single allocation hub location problems.
O'Kelly (1992) also presented a binary quadratic programming formulation for the single allocation hub location problem with fixed costs.
Ernst and Krishnamoorthy (1999) presented an integer linear programming formulation for the capacitated single allocation hub location problem.
The capacitated single allocation p-hub median problem with fixed costs of opening facilities can be easily formulated by merging the presented formulations in Section 1.
So, for smaller instances, the gap is calculated as follows: gap Objective value Optimal value 100% Optimal value Since for the larger instances of the problem the optimal solution cannot be achieved by solving mathematical formulations, we computed relative gaps for heuristics as follows: gap Objective value min (Objective values) 100% min (Objective values) Table 2 summarizes results of different classes of instances.
Conclusion In this study, we generalized the capacitated single allocation p-hub median problem by considering fixed costs of opening facilities."