A Novel One-to-Many Matching Method for the Assignment Problem: An ENEM Case Study

  • Giuseppe F. Neto UFRPE
  • Péricles B. C. Miranda UFRPE
  • Rafael Ferreira Mello UFRPE
  • André C. A. Nascimento UFRPE

Resumo


A distribuição de candidatos em locais de provas é um problema logístico relevante e afeta diversos países, inclusive o Brasil, que realizam exames de seleção por meio de avaliações presenciais. Definir uma distribuição adequada considerando critérios como distância, custo e ocupação é uma tarefa desafiadora. Este trabalho trata a tarefa em questão como um problema combinatório de casamento estável e propõe um novo algoritmo de otimização (O2MSM) para a distribuição automática de candidatos a locais de teste. O O2MSM visa encontrar uma correspondência estável entre candidatos e locais de prova, minimizando a distância entre eles e o número de locais de prova e maximizando a taxa de ocupação desses locais. Os resultados mostraram que o O2MSM superou a abordagem baseline, sendo mais eficiente, realizando a distribuição dos candidatos em segundos, e mais eficaz, reduzindo ao máximo o número de locais de prova, vagas e distância dos candidatos.

Referências

Biró, P. (2017). Applications of matching models under preferences. AI Access.

de Oliveira, F. M., Aloise, D. J., de Lima Júnior, F. C., Aloise, D., and do Nascimento, H. A. D. (2013). Problrma de localização de seções eleitorais e alocação de eleitores. In Anais do Simpósio Brasileiro de Pesquisa Operacional, pages 586-597.

Diebold, F. and Bichler, M. (2017). Matching with indifferences: A comparison of algorithms in the context of course allocation. European Journal of Operational Research, 260(1):268-282.

Fleiner, R., Ferkai, A., and Biró, P. (2019). College admission problem for university dual education. In 2019 IEEE 17th World Symposium on Applied Machine Intelligence and Informatics (SAMI), pages 31-36. IEEE.

Gale, D. and Shapley, L. S. (2013). College admissions and the stability of marriage. The American Mathematical Monthly, 120(5):386-391.

IBGE 2022. Portal de mapas. [link]. Online; acessado em 01 de maio de 2022.

INEP. Escolha e adaptação das salas para provas é processo complexo. [link]. Acessado: 08-05-2022.

INEP 2022. Dados Abertos INEP. http://inep.gov.br/dados. Online; acessado em 01 de maio de 2022.

Kawase, Y. and Iwasaki, A. (2017). Near-feasible stable matchings with budget constraints. arXiv preprint arXiv:1705.07643.

Lima, P. d. S. N., Ambrósio, A. P. L., Ferreira, D. J., and Brancher, J. D. (2019). Análise de dados do enade e enem: uma revisão sistemática da literatura. Avaliação: Revista da Avaliação da Educação Superior, 24(1):89-107.

Prima, P. and Arymurthy, A. M. (2018). Optimization of school location-allocation using genetic algorithm. In 2018 8th International Workshop on Computer Science and Engineering, WCSE 2018, pages 750-755. International Workshop on Computer Science and Engineering (WCSE).

Prima, P. and Arymurthy, A. M. (2019). Optimization of school location-allocation using firefly algorithm. In Journal of Physics: Conference Series, volume 1235, page 012002. IOP Publishing.

Ranjan, P. and Singh, S. (2018). A new algorithm for student-optimal matching: A framework for management institution's admission in india. Indian Institute of Management Calcutta-Working Paper Series-No, 805.

Rocha, E., Cunha Jr, J., Duarte, G., and Fernandes, G. (2019). Otimização para o problema de deslocamento dos candidatos a prova do enem. In Anais do Simpósio Brasileiro de Pesquisa Operacional.

Sanderson, C. and Curtin, R. (2016). Armadillo: a template-based c++ library for linear algebra. Journal of Open Source Software, 1(2):26.

Winarno, E., Hadikurniawati, W., and Rosso, R. N. (2017). Location based service for presence system using haversine method. In 2017 International Conference on Innovative and Creative Information Technology (ICITech), pages 1-4. IEEE.
Publicado
28/11/2022
F. NETO, Giuseppe; MIRANDA, Péricles B. C.; MELLO, Rafael Ferreira; NASCIMENTO, André C. A.. A Novel One-to-Many Matching Method for the Assignment Problem: An ENEM Case Study. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 19. , 2022, Campinas/SP. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 164-173. ISSN 2763-9061. DOI: https://doi.org/10.5753/eniac.2022.227548.

##plugins.generic.recommendByAuthor.heading##

<< < 1 2