区划问题通用元启发框架及关键算法机制研究

The general regionalization problem has been proven to be NP-Hard. Due to its computational complexity, exact methods and clustering-based methods are difficult to solve the problem effectively, and thus the solution methods mainly rely on various heuristics. Nevertheless, the advanced algorithmic mechanisms developed in mainstream operations research have not been fully explored in the design of metaheuristic algorithms for the regionalization problem. This project aims to introduce a unified metaheuristic framework and explore several key algorithmic mechanisms in novel algorithm design. The research topics include: the solution strategies on solving regionalization problem; the design of a unified metaheuristic framework and the implementation of metaheuristic and hybrid algorithms; and the comprehensive testing and analysis of the proposed algorithmic mechanisms. First, based on the formal definition and classification of regionalization problems, a generic heuristic approach to solving homogeneous, functional and balanced regionalization problems will be deliberated in detail. Then, a unified metaheuristic framework including algorithmic components such as intensification strategies, diversification strategies, hybrid mechanisms, and online learning will be developed. The commonly used metaheuristic and hybrid algorithms will be implemented based on the framework. Finally, the proposed algorithmic mechanisms will be comprehensively tested on a set of typical regionalization instances. It is to evaluate the algorithms’ usability, complexity and performance, especially the effects of the key algorithmic mechanisms on the regionalization problem. The key research issues to be investigated in this project are the generic solution strategy for regionalization problem, and the advanced algorithmic mechanisms in algorithm design. The empirical and theoretical findings from this research will contribute to the design of novel algorithms for the regionalization problem. The proposed algorithms also have application potentials in geospatial analysis, planning and decision making in a wide range of areas.

区划问题是一类计算复杂度极高的数学难题。求解区划问题的算法众多，因精确方法和聚类方法性能有限，元启发算法成为主流算法。然而，现有元启发算法未充分利用组合优化领域较为成熟的算法机制。本项目提出区划问题通用元启发算法框架，并探索关键算法机制对算法性能的影响。研究内容：区划问题模型与求解策略；算法框架设计与算法实现；关键算法机制测试与分析。研究思路：在区划问题分类和数学建模的基础上，探讨均质性、功能性和均衡性区划问题的元启发求解策略；设计通用算法框架，引入集中性、多样性、算法混合、在线学习等机制，开发算法基本构件，实现常见元启发算法和混合算法；构造区划案例库，测试算法的适用性，分析关键算法机制对区划问题的有效性。重点解决区划问题通用求解策略和关键算法机制验证这两大关键问题。提升区划问题算法的通用性和优化性能具有重要的理论价值，相关算法在地理空间分析、规划与决策等方面具有巨大的应用潜力。

区划问题是地理学的一个基本问题，也是数学难题。本项目针对地理区划问题开展了模型、算法与应用研究。完成的研究工作及学术贡献概要如下：(1)分析了均衡性、均质性、功能性分区问题的基本特征，构建了设施服务分区问题(SAP)、选区划分问题(PDP)、均等分区问题(EDP)、区划问题(RP)、区位与分区问题(FLSAP)、公共服务区位问题(C-CFLP)等新的数学模型。主要贡献：将分区空间连续约束与引入多个优化问题；提出了面向城市15分钟生活圈的新区位模型；RP模型支持空间单元属性加权和面积加权。(2)设计了一个求解区划与区位问题的通用算法框架，包括数据管理、目标函数、数学建模、初始解生成、局部搜索算子、交叉与变异、空间连续判断与修复、解扰动等基本模块，支持常见元启发算法和混合算法设计(见github.com/yfkong)。主要贡献：算法框架支持元启发算法和混合算法，支持常见区划和区位问题算法设计。(3)针对PDP和EDP提出了两个高性能算法，即基于中心模型求解方法和混合ILS算法，并应用于应急划片管理。主要贡献：基于中心策略，借鉴区位问题算法求解区划问题，大幅提升计算效率。(4)针对RP整合空间采样、K-means算法、快速节点交换、多单元移动搜索、空间连续修复等，设计了混合ILS算法。主要贡献：算法考虑了属性权和面积权，性能显著优于SKATER、REDAP和ARISEL算法，且能够发现空间重复模式。(5)针对公共服务规划，提出最优供需可达性评估方法，设计了求解SAP的ILS和memetic算法，设计了求解SSCFLP、FLSAP和C-CFLP的数学启发算法。主要贡献：提出的数学启发算法性能显著优于分割求解方法(Gadegaard et al. 2018)、核搜索(Guastaroba & Speranza 2014) 和 廊道方法 (Caserta & Voß 2020)；提出的可达性评价方法接近现实、解释力强、计算简单且便于使用。总体上，本项目取得两个方面的创新：在区划领域提出了一系列新数学模型，SAP和FLSAP模型是首次提出，PDP和RP模型降低了计算复杂度，C-CFLP模型解决了生活圈公共设施规划难题；基于通用算法框架，设计了若干高性能算法，包括求解RP的混合ILS算法，求解SSCFLP、FLSAP的数学启发算法，算法性能均显著优于现有的最新算法。