一种求解学区划分问题的混合启发式算法

• 作者: 何雪 姜建武 康传利 张晓宇 李景文 韦波
• 来源期刊: 测绘科学
• 学科: 地球科学
• 关键词: 学区划分 混合启发式算法 迭代禁忌搜索算法 模拟退火算法 全局优化
• 年，卷（期）: 2020,（1）
• 所属期刊栏目: 地图学与地理信息
• 页码范围: 163-170
• 页数: 8页
• 分类号: P208
• 语种: 中文
• DOI: 10.16251/j.cnki.1009-2307.2020.01.023

摘要

针对目前求解学区划分问题算法搜索过程缺乏记忆,搜索效率不高,容易陷入局部最优而收敛慢等问题,该文提出一种多启动(M)框架下,迭代禁忌搜索(ITS)算法与模拟退火(SA)算法混合的M-ITS-SA算法.该算法包括构造初始解、禁忌搜索、SA算法优化与求解等.运用K-Medoids模型对学校分组后,采用M-ITS-SA算法对学区进行划分与优化,并从多个分区方案中求解最优分区方案.学区划分实验结果表明:该文提出的M-ITS-SA算法能够保证分区的空间连续性,适用于单校和多校划片,并在入学总距离上与混合元启发算法(M-ILS-SPP)保持相当的同时,大大降低了超额招生人数和总用时,具有良好的寻优能力和收敛性,优于M-ILS-SPP算法.