Hub location problems appear at the core of strategic planning for many transportation and logistics problems. This class of optimization problems has received a wide gamut of research attention during the last few decades. However, the associated mathematical formulations are mainly developed with deterministic parameters to avoid the complexities and computational difficulties. In this paper, we put forward an extension to the uncapacitated single allocation p-hub median problem under uncertainty in which demands and travel times are stochastic. A robust optimization approach is used to deal with uncertainty in parameters and design a robust hub-and-spoke network. The developed model minimizes the total expected transportation costs, while bounding the relative regret in each scenario. To efficiently solve the model, a two-stage approach is investigated to design two hybrid heuristics. We firstly apply a meta-heuristic (i.e., variable neighborhood search (VNS) or particle swarm optimization (PSO)) to find the best combination for the hubs location. Then, by fixing the hubs location, the original model easily decomposes by scenario for which an efficient tabu search (TS) is designed. Encouraging results on a wide-range of test problems are reported.
