Exact and heuristic methods for the uncapacitated single allocation planar hub location problem with service-level considerations
Computers and Industrial Engineering, vol.219, 2026 (SCI-Expanded, Scopus)
- Publication Type: Article / Article
- Volume: 219
- Publication Date: 2026
- Doi Number: 10.1016/j.cie.2026.112209
- Journal Name: Computers and Industrial Engineering
- Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, ABI/INFORM, Aerospace Database, Applied Science & Technology Source, Compendex, INSPEC, DIALNET, Business Source Ultimate (EBSCO), Engineering Source (EBSCO), Technology Collection (ProQuest)
- Keywords: Genetic algorithm, Matheuristic, Mixed Integer Second Order Cone Programming, Planar hub location problem, Service level, Single allocation, Uncapacitated
- Hacettepe University Affiliated: Yes
Abstract
Hub-and-spoke networks play a significant role across several application areas. In this study, we consider the uncapacitated single allocation planar hub location problem in which the demand of n spokes is served via p hubs located anywhere in continuous space. Each customer is assigned to one hub, capacities are unlimited, all inter-customer flows are routed through hubs, and hubs are fully connected. In addition, we incorporate service-level requirements by imposing a maximum allowable spoke–hub distance. The resulting problem is formulated as a Mixed Integer Second Order Cone Program (MISOCP). To the best of our knowledge, this is the first exact solution method proposed for the considered problem. While the MISOCP provides an exact model, it becomes computationally challenging for large-scale instances, particularly when the service-level requirement is not very restrictive. To address this, we develop two matheuristics. Both approaches first solve a discrete version and then apply an alternating improvement scheme (location–allocation refinement). The matheuristics differ in their initial candidate facility sets: the first restricts hub candidates to spokes, whereas the second employs an enriched candidate set. We also modify a genetic algorithm from the literature for service-level constraints. Through computational experiments, we compare the exact MISOCP against the proposed matheuristics and the modified genetic algorithm. The results illustrate the trade-offs between solution quality and runtime and demonstrate the effectiveness of the proposed approaches on benchmark instances. Furthermore, for a larger 81-node real-life Turkish dataset, high-quality solutions are obtained within a reasonable time limit.