A Novel One-to-Many Matching Method for the Assignment Problem: An ENEM Case Study
Abstract
Distributing candidates in test locations is a relevant logistics problem and affects different countries, including Brazil, that conduct selection exams through face-to-face assessments. Defining an appropriate distribution considering criteria such as distance, cost, and occupation is a challenging task. This work treats the task in question as a combinatorial problem of stable marriage and proposes a new optimization algorithm (O2MSM) for the automatic distribution of candidates to test sites. The O2MSM aims to find a stable correspondence between candidates and test locations, minimizing the distance between them and the number of test locations and maximizing the occupancy rate of these locations. The results showed that O2MSM surpassed the baseline approach, being more efficient, performing the distribution of candidates in seconds, and more effective, reducing the number of test locations, vacancies, and distance to candidates as much as possible.
References
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.
