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

摘要：

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

关键词：学区划分、混合启发式算法、迭代禁忌搜索算法、模拟退火算法、全局优化

所属期刊栏目：45

分类号：P208(一般性问题)

资助基金：国家自然科学基金项目;广西自然科学基金项目;广西空间信息与测绘重点实验室基金项目;桂林理工大学博士基金项目

在线出版日期：2020-05-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：163-170