Paper Info
Title
Area aggregation in map generalisation by mixed-integer programming
Abstract
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.
Year
DOI
Venue
2010
10.1080/13658810903401008
International Journal of Geographical Information Science
Keywords
Field
DocType
mixed-integer programming,graph theoretical problem formulation,optimisation software,alternative optimisation approach,aggregation problem,map generalisation,area aggregation,small instance,large datasets,optimisation method yield,input scale,optimisation method,output scale,mixed integer programming,simulated annealing,aggregation,iterative algorithm
Semantic similarity,Simulated annealing,Aggregation problem,Mathematical optimization,Computer science,Iterative method,Generalization,Heuristics,Software,Integer programming,Artificial intelligence,Machine learning
Journal
Volume
Issue
ISSN
24
12
1365-8816
Citations 
PageRank 
References 
12
0.90
13
Authors
2
Name
Order
Citations
PageRank
Jan-Henrik Haunert117919.32
Alexander Wolff222222.66