地理学报

地理学报 ›› 2017, Vol. 72 ›› Issue (2): 256-268.doi: 10.11821/dlxb201702006

• 城市与区域发展 • 上一篇    下一篇

学校分区问题混合元启发算法研究

孔云峰1(), 朱艳芳1, 王玉璟1,2   

  1. 1. 河南大学黄河中下游数字地理技术教育部重点实验室, 开封 475000
    2. 河南大学计算机与信息工程学院,开封 475000
  • 收稿日期:2016-07-04 修回日期:2016-10-22 出版日期:2017-02-15 发布日期:2017-04-28
  • 作者简介:

    作者简介：孔云峰(1967-), 男, 博士, 博士生导师, 主要从事空间分析、空间优化等研究。E-mail: yfkong@henu.edu.cn

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-04-28

RichHTML

5

PDF (PC)

701

赞

被引次数

1

摘要：

中国城市义务教育学校采用单校划片或多校划片的方式确定招生范围,落实就近入学的法律要求。针对多校划片这一新的学校分区问题,提出“先学校分组,再学生分派”的策略进行划片,并设计了学校分组线性规划模型和学校分区混合元启发算法。分区算法包括初始解构造、邻域搜索算子、破坏重建扰动、集合划分问题（SPP）建模与求解等基本模块,在多启动迭代局部搜索（ILS）算法框架中进行问题求解。通过多启动、随机搜索、破坏重建扰动等机制提升算法的多样性,并引入SPP模型提升算法的全局寻优能力。选择一个县级市和一个市辖区分别进行学校划片实验,结果表明：混合元启发算法优化性能优异且收敛性好,适用于求解单校划片和多校划片问题;SPP模型在单校划片问题中具有明显的优势。

关键词: 学校分区问题, 空间连续约束, 邻域搜索, 混合元启发算法

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