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

Resumo

Este trabalho apresenta a GCS-H, uma heurística construtiva de passagem única para o Problema p-Hub Mediana com r-Alocação (UrApHMP). A abordagem utiliza Escalonamento Multidimensional (MDS) e K-Means para diversificação geográfica de candidatos e PageRank para seleção baseada em importância estrutural, seguida por uma construção gulosa. Validada em 231 instâncias do benchmark AP, a GCS-H supera a meta-heurística GRASP (redução de custo média de 2,47%) e alcança um gap médio de 2,35% em relação às soluções do estado da arte (Scatter Search). A heurística substitui buscas iterativas por análise estrutural, oferecendo uma solução escalável para problemas de localização de hubs.

Referências

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.