A HYBRID HEURISTIC ALGORITHM FOR SCHOOL DISTRICT DIVISION

Abstract. Single-school and multi-school district divisions are the two main ways to balance educational resources for enrollment in primary and secondary schools. A hybrid heuristic algorithm (M-ILS-SA) for school district division is proposed based on the combination of a Multi-Start Iterative Local Search (M-ILS) algorithm and a Simulated Annealing (SA) algorithm. According to the principle of “school grouping first and student assigning second”, a K-Medoids model is first used to implement school grouping. Then, the initial solution for each run of ILS that starts is generated by the region growth algorithm. After completing the neighborhood search, the SA algorithm is finally used to choose the optimal solution from the historically generated school districts identified by ILS. The experimental results show that the proposed M-ILS-SA algorithm can effectively reduce the total elapsed time and the number of over-enrolled students in each school district, and ensure spatial continuity in both single-school and multi-school district divisions.