Integer and stable marriage models for assignments to preschools

Abstract

Á hverju vori lýkur stór hópur barna leikskólavist á höfuðborgarsvæðinu til að hefja grunnskólagöngu þá um haustið. Um það leyti stendur Reykjavíkurborg frammi fyrir ákvörðunartökuvandamáli um hvernig úthluta eigi lausum plássum leikskóla, sem staðsettir eru víðsvegar um borgina. Í þessari ritgerð eru skoðuð tvö ólík stærðfræðilíkön sem kunna að koma að gagni við úthlutun á lausum plássum og þau borin saman við núverandi fyrirkomulag hjá borginni. Líkönin eru hönnuð með það að markmiði að mæta sem best óskum foreldra um leikskólapláss en jafnframt tryggja að jafnræðis sé gætt við úthlutunina og að úthlutunin sé í samræmi við reglur borgarinnar. Að auki er lagt mat á það hvort slík líkön gætu komið að gagni við úthlutanir hjá sjálfstætt starfandi leikskólum. Útkoma úthlutunarinnar kemur óneitanlega til með að hafa áhrif á daglegt líf fjölskyldna sem nýta sér leikskólaþjónustu Reykjavíkurborgar og því mikilvægt að hún sé með besta móti. Líkönin sem um ræðir eru annarsvegar heiltölubestunarlíkan og hinsvegar líkan sem byggir á stöðugu hjónabandsaðferðinni. Bæði líkönin nýta sér val úr umsókn umsækjanda ásamt fjarlægðum frá heimili umsækjanda til leikskóla til að ná fram sem bestri niðurstöðu um úthlutun. Niðurstöðurnar gefa til kynna að líkan sem byggir á stöðugu hjónabandsaðferðinni gæti talist vænlegur kostur fyrir Reykjavíkurborg. Líkanið skilar góðri lausn sem er jafnframt gegnsæ og í samræmi við reglur borgarinnar. Líkönum sem þessum hefur verið beitt erlendis við úthlutun á skólaplássum með góðum árangri. Frekari rannsókna er þörf áður en slíkt líkan er tekið í notkun. Ef gera á beinan samanburð á líkönum og núverandi fyrirkomulagi eftir sömu forsendum, þá er þörf á breytingum á umsóknarferli svo kanna megi hvort líkön af þessu tagi skili í raun þeim ávinningi umfram núverandi aðferð sem réttlætir notkun þeirra.

Every spring, a large group of children graduate from preschools in the municipality in order to begin attending elementary school in the autumn. Around this time the City of Reykjavík is faced with a decision problem how to assign children to vacant places at the preschools, which are scattered across the city. In this thesis, two mathematical models are presented that might help with the assignment of the vacant places, and they are compared to the assignment process currently being used by the city. The goal of the models is to meet the applicants' preschool preferences as far as possible, while ensuring the applicants' equality and fulfilling the assignment rules of the city. Additionally, it is assessed if such models could be beneficial for private preschools. The outcome of the assignments will undeniably affect everyday life of families that use the preschool services provided by the City of Reykjavík. It is thus important that they are carried out in the best way possible. The models under consideration are an integer programming model and a stable marriage model. Both models use the preferences given by the parents in their application as well as the distances between the applicants' homes and the preschools in order to reach the best possible solution. The results show that a model that is based on the stability of marriage method is a promising alternative for the City of Reykjavík. The model provides a good solution that is both transparent and in accordance with the rules of the city. Models like these have been applied abroad for assignments to schools with good results. Additional research is required before such a model can be implemented. If the models and the current assignment process are to be compared under the same assumptions, then the application process must be changed. It will then be possible to examine whether the models are really better than the current method and thus whether their usage is justified.