Applying the Golden Ball to the Maximum Diversity 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/etc.2025.9173

Abstract

This work adapts the Golden Ball metaheuristic to the Maximum Diversity Problem in graphs, modifying the sports-inspired algorithm to select subsets of vertices that maximize the sum of their distances. Experiments with 80 instances demonstrated competitive performance, achieving solutions with deviations ranging from 0.06% to 0.95% compared to the best-known values, in addition to a considerably shorter execution time compared to the Scatter Search method, a reference in the literature. The algorithm excelled in geometric instances, obtaining solutions equivalent to the best-known values in 95% of cases, and exhibited consistent performance across the remaining instances.

References

Aringhieri, R., Bruglieri, M., Malucelli, F., and Nonato, M. (2015). Special issue on optimization in medicine and biology: Exact and heuristic approaches. European Journal of Operational Research, 244(3):647–648.

Blum, C. and Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys (CSUR), 35(3):268–308.

Carrabs, F., Cerulli, R., and Toth, P. (2022). New approaches for solving the maximum diversity problem in large graphs. Journal of Heuristics, 28(3):231–256.

Duarte, A., Martí, R., Sánchez-Oro, J., and Glover, F. (2015). Metaheuristics for the maximum diversity problem. European Journal of Operational Research, 240(1):24–36.

Gallego, M., Duarte, A., Laguna, M., and Martí, R. (2009). Hybrid heuristics for the maximum diversity problem. Computational Optimization and Applications, 44(3):411–426.

Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company.

Ghosh, J. B. (1996). Computational aspects of the maximum diversity problem.

Gonzalez, J. A., Hernández-Pérez, H., and Lozano, M. (2020). A review on maximum diversity problems. European Journal of Operational Research, 287(2):401–420.

Martí, R., Duarte, A., and Laguna, M. (2013). Advanced scatter search for the max-min diversity problem. INFORMS Journal on Computing, 25(2):245–260.

Osaba, E., Diaz, F., and Onieva, E. (2014). Golden ball: A novel meta-heuristic to solve combinatorial optimization problems based on soccer concepts. Applied Intelligence, 41(1):145–166.

Ruttanateerawichien, K., Kurutach, W., and Pichpibul, T. (2014). An improved golden ball algorithm for the capacitated vehicle routing problem. In Pan, L., Păun, G., Pérez-Jiménez, M. J., and Song, T., editors, Bio-Inspired Computing - Theories and Applications, pages 341–356, Berlin, Heidelberg. Springer Berlin Heidelberg.

Worawattawechai, T., Intiyot, B., Jeenanunta, C., and Ferrell, W. G. (2022). A learning enhanced golden ball algorithm for the vehicle routing problem with backhauls and time windows. Computers Industrial Engineering, 168:108044.