Applying Answer Set Programming and Metaheuristics to the Volunteer Assignment Problem with Preferences

• Francisco R. Dutra UFC
• Thiago P. Valente UFC
• Carlos V. Araújo UECE
• Alexandre M. Arruda UFC

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

Resumo

The Volunteer Assignment Problem, an NP-hard variant of the Generalized Assignment Problem, poses significant computational challenges for exhaustive search. This work evaluates three strategies to maximize a volunteer-preference-based function: exact search via Answer Set Programming (ASP), and two hybrid approaches combining a greedy heuristic or ASP itself with Simulated Annealing and Genetic Algorithm refinement. The exact method alone exceeded the time limit without proving optimality, whereas the hybrid strategies delivered high-quality solutions efficiently. The ASP-initialized GA achieved the best overall performance, outperforming the constructive heuristic and maximizing allocation quality

Referências

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

Brewka, G., Eiter, T., and Truszczyński, M. (2011). Answer set programming at a glance. Communications of the ACM, 54(12):92–103.

Burkard, R. E., Dell’Amico, M., and Martello, S. (2012). Assignment Problems, Revised Reprint. SIAM.

da Silva Neto, V. S., França, R. L. d. M., Silva, K. K. N., da Costa, L. C. A., and Kramer, H. H. F. R. (2024). A mixed-integer linear programming model for scheduling volunteers in technical support teams in Non-Governmental Organizations. Socioeconomic Analytics, 2(1):19–36.

Ferreira, P. and Arruda, A. (2025). Post-improving the capacitated vehicle routing problem using a max-sat solver. In Anais do VI Workshop Brasileiro de Lógica, pages 32–39, Porto Alegre, RS, Brasil. SBC.

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

Gebser, M., Kaminski, R., Kaufmann, B., and Schaub, T. (2012). Answer Set Solving in Practice. Synthesis Lectures on Artificial Intelligence. Morgan & Claypool Publishers.

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley.

Hoos, H. and Stützle, T. (2005). Stochastic Local Search: Foundations and Applications. The Morgan Kaufmann Series in Artificial Intelligence. Elsevier Science.

Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220:671–680.

Reis, E. R. d. S. (2024). Alocação otimizada de voluntários em programa de restabelecimento de laços familiareas por uma ONG Internacional.

Rossi, F., van Beek, P., and Walsh, T. (2006). Handbook of Constraint Programming. Foundations of Artificial Intelligence. Elsevier Science.

Sampson, S. E. (2006). Optimization of volunteer labor assignments. Journal of Operations Management, 24(4):363–377. Operations Management in Not-For-Profit, Government and Public Services: Innovative Applications and Case Studies.

Sarhani, M., Voß, S., and Jovanovic, R. (2023). Initialization of metaheuristics: comprehensive review, critical analysis, and research directions. International Transactions in Operational Research, 30(6):3361–3397.

Silva, P., Silva, F., Dantas, R., Araújo, C., and Arruda, A. (2026). A clustering-based maxsat hybrid approach for the capacitated vehicle routing problem with time windows. In Anais do XI Encontro de Teoria da Computação, pages 1–5, Porto Alegre, RS, Brasil. SBC.

Sousa, F. Y. d. (2019). Uma abordagem inicial em answer set programming para o problema de programação de tripulação.

Talbi, E.-G. (2009). Metaheuristics: From Design to Implementation. Wiley.

Wolsey, L. and Nemhauser, G. (1999). Integer and Combinatorial Optimization. Wiley Series in Discrete Mathematics and Optimization. Wiley.