边界约束最大p区域问题及其启发式算法

Boundary-Constrained Max-p-Regions Problem and Its Heuristic Algorithm

针对城市空间内的自动化分区,顾及空间域边界对于分区结果的约束效应,提出一种边界约束最大p区域问题。在最大化区域个数p前提下,针对单元与多个边界交叉产生的单元从属不确定性,设计一种顾及空间单元从属不确定度的单元差异性加权目标函数。并在满足阈值约束等最大p区域问题原有约束下,增加若干边界约束,保证形成的区域一般在某个边界之内,若需跨越多个边界,则需涵盖整个边界。针对该非确定性多项式难题设计并实现一种基于禁忌搜索的启发式算法,并在模拟数据和实际数据集上进行实验。实验结果表明,该方法可以使科研和实验人员能够将现实世界中的边界约束灵活地加入到分区问题的模型中,以对最大p区域问题的求解结果进行更为实际的控制。

The boundary-constrained max-p-regions problem is proposed to tackle the automatic regionalization problem in urban space with respect to constraining regions by boundaries. On the premise of maximized the number of regions p, a weighted objective function considering the subordinate uncertainfy of spatial elements is designed to deal with the subordinat uncertainty caused by the intersectiou of elements and multiple boundaries. Besides a threshold constraint and other constraints in the max-p-regions problem, several boundary constraints are incorporated as well. A region would normally be within a certain boundary. If a region crosses boundaries, these boundaries must be encompassed by the region. A Tabu-search based heuristic algorithm is designed and implemented to solve this NP-hard problem. The effectiveness are evaluated through a simulation dataset and a real-world dataset. The results show that the proposed model allows researchers and practitioners flexibly incorporate boundary constraints in real-world problems into the model specification, thus exerts more practical control over the regionalization results.