Area aggregation in map generalisation by mixed-integer programming

Topographic databases normally contain areas of different land cover classes, commonly defining a planar partition, that is, gaps and overlaps are not allowed. When reducing the scale of such a database, some areas become too small for representation and need to be aggregated. This unintentionally but unavoidably results in changes of classes. In this article we present an optimisation method for the aggregation problem. This method aims to minimise changes of classes and to create compact shapes, subject to hard constraints ensuring aggregates of sufficient size for the target scale. To quantify class changes we apply a semantic distance measure. We give a graph theoretical problem formulation and prove that the problem is NP-hard, meaning that we cannot hope to find an efficient algorithm. Instead, we present a solution by mixed-integer programming that can be used to optimally solve small instances with existing optimisation software. In order to process large datasets, we introduce specialised heuristics that allow certain variables to be eliminated in advance and a problem instance to be decomposed into independent sub-instances. We tested our method for a dataset of the official German topographic database ATKIS with input scale 1:50,000 and output scale 1:250,000. For small instances, we compare results of this approach with optimal solutions that were obtained without heuristics. We compare results for large instances with those of an existing iterative algorithm and an alternative optimisation approach by simulated annealing. These tests allow us to conclude that, with the defined heuristics, our optimisation method yields high-quality results for large datasets in modest time.

地形数据库通常包含不同土地覆盖类别的区域，且通常构成平面划分（planar partition），即不允许存在间隙与重叠。当对这类数据库进行比例尺缩减时，部分区域会因尺寸过小而无法满足可视化表达要求，需要进行聚合处理。这一过程会无意但不可避免地引发土地覆盖类别的变更。
本文针对该聚合问题提出了一种优化方法：在确保聚合区域满足目标比例尺所需最小尺寸的硬约束（hard constraint）前提下，该方法旨在最小化土地覆盖类别的变更，并生成紧凑的聚合形状。为量化土地覆盖类别的变更幅度，本文采用了语义距离度量（semantic distance measure）方法。
本文给出了该问题的图论（graph theoretical）建模，并证明该问题属于NP难（NP-hard）问题，这意味着我们无法期望找到高效的精确求解算法。为此，本文提出了一种基于混合整数规划（mixed-integer programming）的求解方案，可借助现有优化软件对小规模问题实例进行最优求解。
为处理大规模数据集，本文引入了专用启发式（heuristics）算法，可预先消去部分变量，并将原问题实例分解为若干独立的子实例。本文以德国官方地形数据库ATKIS的数据集为测试对象，输入比例尺为1:50000，输出比例尺为1:250000。针对小规模问题实例，本文将该方法的求解结果与无启发式算法时得到的最优解进行了对比；针对大规模问题实例，本文将该方法的求解结果与现有迭代算法以及模拟退火（simulated annealing）这一替代优化方法的结果进行了对比。
通过上述测试，本文可得出结论：在采用所定义的启发式算法后，本文提出的优化方法可在合理耗时内为大规模数据集生成高质量的求解结果。