The uncapacitated single allocation $p$-hub median problem (USApHMP) is one of the popular classical models in hub location theory that has been studied in the Operations Research literature for several years. It is a cornerstone problem for designing efficient and cost-effective logistics and telecommunications networks, where consolidation of flows through hub facilities leads to significant economies of scale. The main purpose of this chapter is to review a general variable neighborhood search that has been developed for this problem and successfully tested on standard benchmark datasets, including AP and URAND instances with up to 1000 nodes. We also examine the usefulness of a $p$-median formulation that approximates the USApHMP and can find good starting solutions for the presented VNS procedures. The computational experiments show the superiority of GVNS over other state-of-the-art heuristics for solving the USApHMP. In addition, it is empirically shown that a surrogate $p$-median problem that deletes transfer costs between hubs from the objective function (i.e., considers only collection and distribution costs) can be used to generate high-quality starting solutions.