Efficient Mixed Integer Programming Formulation for the Uncapacitated r-Allocation p-Hub Center Problem

Abstract

This paper addresses the uncapacitated r-allocation p-hub center problem (UrApHCP), which is essential in hub location modeling for transportation and telecommunications systems. The study enhances the computational efficiency of Mixed Integer Programming (MIP) formulations for UrApHCP, which often struggle with multiple equivalent solutions. The proposed method extends the traditional objective function by including overall transport cost along with the maximal minimal transportation cost, using a lexicographic objective function. This extension is applied to two MIP formulations, the four-index model (FIM) and the flow-based model (FBM), to better distinguish solutions and improve efficiency. Computational experiments on standard benchmark instances show that the extended models significantly reduce computational time, highlighting their practical advantages. This research advances optimization techniques for complex hub location problems by improving the computational efficiency of MIP formulations.