International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences
Publications Copernicus
Download
Citation
Volume XLII-3/W10
Int. Arch. Photogramm. Remote Sens. Spatial Inf. Sci., XLII-3/W10, 1113–1120, 2020
https://doi.org/10.5194/isprs-archives-XLII-3-W10-1113-2020
© Author(s) 2020. This work is distributed under
the Creative Commons Attribution 4.0 License.
Int. Arch. Photogramm. Remote Sens. Spatial Inf. Sci., XLII-3/W10, 1113–1120, 2020
https://doi.org/10.5194/isprs-archives-XLII-3-W10-1113-2020
© Author(s) 2020. This work is distributed under
the Creative Commons Attribution 4.0 License.

  08 Feb 2020

08 Feb 2020

A HYBRID HEURISTIC ALGORITHM FOR SCHOOL DISTRICT DIVISION

X. He1,2 and B. Wei1,3 X. He and B. Wei
  • 1Guangxi Key Laboratory of Spatial Information and Geomatics, Guilin University of Technology, Jiangan Road, Guilin, China
  • 2Nanning Land Surveying and Mapping Geographic Information Center, Jinchun Road, Nanning, China
  • 3College of Geomatics and Geoinformation, Guilin University of Technology, Jiangan Road, Guilin, China

Keywords: Single-School District Division, Multi-School District Division, Hybrid Heuristic, Multi-Start Iterative Local Search, Simulated Annealing, Neighborhood Search, Spatial Continuity

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.