Simultaneous selection and displacement of buildings and roads for map generalization via mixed-integer quadratic programming

Abstract

Research on map generalization has led to many algorithms for multiple elementary processes, such as object selection, aggregation, simplification, and displacement. Algorithms for different processes are usually combined to workflows or orchestrated using multi-agent systems. Here, we present a novel approach integrating object selection and displacement at an algorithmic level. We model both processes together as an optimization problem in the form of a mixed-integer quadratic program and demonstrate that it can be optimally solved using a mathematical problem solver. Moreover, we present an efficient heuristic. In experiments with roads and buildings from OpenStreetMap, our methods showed a good capability to unselect a small set of buildings whose inclusion in the output map would have caused large displacements or proximity conflicts. For a quantitative evaluation, we solved a benchmark instance once with our new model integrating selection and displacement and once with a variant of our model where the selection of objects was prescribed based on a solution found with an existing approach via simulated annealing. Comparing the two models, our integrated model yielded a solution of 33% less total cost. We conclude the article with a discussion of possible follow-up work.