Acta Geographica Sinica ›› 2017, Vol. 72 ›› Issue (2): 256-268.doi: 10.11821/dlxb201702006

• Urban and Regional Development • Previous Articles     Next Articles

A hybrid metaheuristic algorithm for the school districting problem

Yunfeng KONG1(), Yanfang ZHU1, Yujing WANG1,2   

  1. 1. Key Laboratory of Geospatial Technology for the Middle and Lower Yellow River Regions, Ministry of Education, Henan University, Kaifeng 475000, Henan, China
    2. College of Computer and InformationEngineering, Henan University, Kaifeng 475000, Henan, China
  • Received:2016-07-04 Revised:2016-10-22 Online:2017-02-15 Published:2017-02-15

Abstract:

School districting has been widely introduced for compulsory education in urban areas of China in recent years according to the national policy of nearby school enrollment. A new enrollment policy for compulsory schools was issued by the Ministry of Education of China in 2016. According to the policy, a new school districting scheme for a district consisting of multiple schools is recommended to cities with uneven provision of compulsory schools, which aims to stabilize the apartment price in some existing school districts, and also to appease the public criticism on the phenomenon of school choice. This paper proposes a hybrid metaheuristic algorithm for solving both the classical single-school and the new multi-school districting problems. A two-stage strategy of "school grouping first and student assigning second" was used for multi-school districting. The school grouping problem was solved by mixed linear programming. An algorithm of multi-start iterated local search (ILS) with set-partitioning modeling (M-ILS-SPP) was introduced to solve the student assigning problem, which is a difficult problem due to the constraints of district contiguity and school capacity. Each run of ILS starts with an initial solution generated by the region growth method, and then executes neighborhood search and ruin-and-recreate perturbation iteratively. The proposed algorithm adopted four neighborhood search operators, three ruin methods and two solution acceptance rules. In addition, a model of set-partitioning problem (SPP) was used to choose a better solution from the historical districts identified by ILS. Two cases were used to test the performance of the proposed algorithm. The results from multiple scenarios of school districting show that the M-ILS-SPP algorithm for single-school or multi-school districting problems is effective in terms of solution quality and algorithm convergence. It is also found that the newly-designed neighborhood operators which move more spatial units simultaneously and the use of three perturbation methods randomly are critical for finding high quality district solutions. In addition, the set-partitioning modeling overcomes the short-sight limitation of local search operators and is capable of finding globally best solutions, especially for the single-school districting problem.

Key words: school districting problem, spatial contiguity, neighborhood search, hybrid metaheuristic