An Estimated Formulation for the Capacitated Single Alocation p-hub Median Problem with Fixed Costs of Opening Facilities

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.

Keywords

• capacitated single allocation p-hub median problem
• mathematical formulation
• linearization
• preprocessing