The authors present a new LP formulation for the single allocation p-hub median problem, which requires fewer variables and constraints than those traditionally used in the literature. They develop a good heuristic algorithm for its solution based on simulated annealing (SA). They use the SA upper bound to develop an LP-based branch-and-bound solution method. They present computational results for well-known problems from the literature which show that exact solutions can be found in a reasonable amount of computational time. They also benchmark their new solution approach on a new data set. This data set, which includes problems that are larger than those used in the literature, is based on a postal delivery network.