OPTIMIZATION METHODS FOR AREA AGGREGATION IN LAND COVER MAPS
J.-H. Haunert
Institute of Cartography and Geoinformatics, Leibniz
Universitaet Hannover, Germany
jan.haunert@ikg.uni-hannover.de
Given a polygonal subdivision in which each polygon is assigned to a land cover class, we consider the problem of aggregating polygons such that a defined area threshold is satisfied. The aggregation is directed at two objectives: Classes of polygons shall change as little as possible and compact shapes are preferred. In this paper, the problem is formalized and two different approaches are compared, namely mixed integer programming and simulated annealing.
The problem can be formulated as Mixed Integer Program (MIP) in different ways. These options are discussed with respect to the applicability of standard branch and cut techniques that are implemented in commercial software packages. Heuristics are defined to speed up the processing; their effects on the obtained result are shown.
Simulated annealing generally requires the definition of a neighborhood structure that defines possible changes of a feasible solution during one iteration. It turned out that it is not trivial to find a neighborhood structure that ensures the connectivity of the solution space for the discussed problem. Thus, the optimal solution can not be reached from all possible start solutions via a feasible path. The problem is solved by relaxing the hard threshold constraints and penalizing solutions with small areas by definition of an additional term in the objective function. The method starts then with a solution that can be obtained with a simple greedy algorithm. An annealing schedule is defined for the simulation. In order to end up with a feasible solution, a method is proposed to repair solutions with violated threshold constraints.
First tests showed that the solutions of both methods are of high quality and very similar. The MIPs resulted in slightly better solutions, while the simulated annealing method turned out to be faster.
Finally, it is discussed how the presented methods can be integrated in a more comprehensive generalization framework that comprises also polygon decomposition, collapse and line simplification. A complete workflow for the generalization of land cover maps based on these operators is introduced.