New formulation and a branch‐and‐cut algorithm for the multiple allocation p‐hub median problem

This article deals with the uncapacitated multiple allocation p‐hub median problem, where p facilities (hubs) must be located among n available sites in order to minimize the transportation cost of sending a product between all pairs of sites. Each path between an origin and a destination can traverse any pair of hubs. For the first time in the literature, an integer programming formulation with O(n ²) variables has been devised to approach this problem. Based on this formulation, a branch‐and‐cut algorithm has been developed which allows to solve larger instances than those previously solved in the literature. The proposed algorithm performs specially well for relatively large values of p.