An Exact Method for the Uncapacitated Single Allocation Planar Hub Location Problem

Hub-and-spoke networks play a significant role in various fields such as transportation, telecommunications, and supply chain management. In this study, we address the problem of meeting the demand of n given customers (spokes) through p hubs to be located in continuous space. It is assumed that customers must be assigned to single hub, hub capacities are unlimited, all flows between customers are routed through hubs, hubs are fully connected, and hubs can be positioned anywhere on the plane. The considered problem is formulated as a nonlinear mathematical program which involves products of decision variables and Euclidean distances. Second Order Cone (SOC) constraints are employed to accurately represent the Euclidean distances, and a linearization approach is introduced to handle the nonlinearities arising from the products of decision variables. Thus, the problem is efficiently modeled as a Mixed Integer Second Order Cone Programming (MISOCP) formulation. To the best of our knowledge, this is the first exact solution method proposed for the problem even though there are some heuristics. Through computational experiments, the proposed MISOCP is compared with a well-known genetic algorithm from the literature on small sized instances. The results demonstrate that the exact method not only yields optimal solutions in reasonable time, but also outperforms the genetic algorithm in terms of both solution quality and computational time. Furthermore, for a larger 81-node real-life Turkish dataset, a high-quality feasible solution is obtained within 2-hour time limit.