GCS-H: A Geo-Structural Constructive Heuristic for the Uncapacitated r-Allocation p-Hub Median Problem

• Carlos V. Dantas Araújo UFC
• Jailon W. B. Oliveira da Silva UFC
• Pablo L. Braga Soares UFC

DOI: https://doi.org/10.5753/eniac.2025.14185

Abstract

This paper introduces GCS-H, a single-pass constructive heuristic for the Uncapacitated r-Allocation p-Hub Median Problem (UrApHMP). The approach uses Multidimensional Scaling (MDS) and K-Means clustering for geographic candidate diversification and PageRank for selection based on structural importance, followed by a greedy construction phase. Validated on 231 instances from the AP benchmark, GCS-H outperforms the GRASP metaheuristic (mean cost reduction of 2.47%) and achieves a mean gap of 2.35% from state-of-the-art Scatter Search solutions. The heuristic replaces iterative searches with structural analysis, offering a scalable solution for hub location problems.

References

Corberán, , Peiró, J., Marti, R., and Saldanha-da Gama, F. (2018). Heuristic solutions for a class of stochastic uncapacitated p-hub median problems.

Ernst, A. T. and Krishnamoorthy, M. (1996). Efficient algorithms for the uncapacitated single allocation p-hub median problem. Location science, 4(3):139–154.

Hastie, T., Tibshirani, R., and Friedman, J. (2009). The elements of statistical learning: data mining, inference, and prediction. Springer Science & Business Media.

Love, R. F., Morris, J. G., and Wesolowsky, G. O. (1988). Facilities location: Models & methods. Publications in operations research series, 7.

MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, 1(14):281–297.

O’Kelly, M. E. (1987). The p-hub median problem. Transportation Science, 21(3):183–195.

Page, L., Brin, S., Motwani, R., and Winograd, T. (1999). The pagerank citation ranking: Bringing order to the web.

Yaman, H. (2011). Allocation strategies in hub networks. European Journal of Operational Research, 211(3):442–451.