一个基于迭代局部搜索的区划问题算法

摘要: 区划问题是将特定地理区域划分为若干空间连续的分区，满足分区内差异最小和分区间差异最大这一基本原则，广泛应用于地理、环境、生态、经济、农业、城市等领域。60余年来，学者尝试建立各种区划问题数学模型，设计了一系列的求解算法，包括精确算法、基于聚类的算法、启发式算法和基于树图的算法。针对现有算法计算效率与求解质量难以兼顾这一局限，本文提出了一个基于迭代局部搜索(ILS)的区划问题算法。该算法主要机制包括：通过邻域单元移动改进分区质量；参照中心单元快速计算分区方差提升算法速度；使用扰动机制跳出局部最优状态；更新分区中心点提升分区方案目标值；以及使用群搜索探索更大的解空间；算法各步骤中通过分区修复保持分区空间连续。55个基准案例测试表明：ILS算法求解质量优于ARISEL算法和SKATER算法，计算时间大幅低于ARISEL算法。一个多指标气候分区实验也验证了ILS算法的实用性。本文ILS算法兼顾分区质量和计算效率，并允许一个分区包含多个空间连续且面积较大的区域，具有灵活性和实用性。