Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem

In this paper new MILP formulations for the multiple allocation p-hub median problem are presented. These require fewer variables and constraints than those traditionally used in the literature. An efficient heuristic algorithm, based on shortest paths, is described. LP based solution methods as well as an explicit enumeration algorithm are developed to obtain exact solutions. Computational results are presented for well known problems from the literature which show that exact solutions can be found in a reasonable amount of computational time. Our algorithms are also benchmarked on a different data set. This data set, which includes problems that are larger than those used in the literature, is based on a postal delivery network and has been treated by the authors in an earlier paper.