| Résumé : |
(auteur) The aggregation of spatial data is a recurring problem in geoinformation science. Aggregating data means subsuming multiple pieces of information into a less complex representation. It is pursued for various reasons, like having a less complex data structure to apply further processing algorithms or a simpler visual representation as targeted in map generalization. In this thesis, we identify aggregation problems dealing with spatial data and formalize themas optimization problems. That means we set up a function that is capable of evaluating valid solutions to the considered problem, like a cost function for minimization problems. To each problem introduced, we present an algorithm that finds a valid solution that optimizes this objective function. In general, this superiority with respect to the quality of the solution comes at the cost of computation efficiency, a reason why non-exact approaches like heuristics are widely used for optimization. Nevertheless, the higher quality of solutions yielded by exact approaches is undoubtedly important. On the one hand, “good” solutions are sometimes not sufficient. On the other hand, exact approaches yield solutions that maybe used as benchmarks for the evaluation of non-exact approaches. This kind of application is of particular interest since heuristic approaches, for example, give no guarantee on the quality of solutions found. Furthermore, algorithms that provide exact solutions to optimization problems reveal weak spots of underlying models. A result that does not satisfy the user cannot be excused with a mediocre performance of an applied heuristic. With this motivation, we developed several exact approaches for aggregation problems, which we present in this thesis. Since we deal with spatial data, for all problems considered, the aggregation is based on both geometric and semantic aspects although the focus varies. The first problem we discuss is about visualizing a road network in the context of navigation. Given a fixed location in the network, we aim for a clear representation of the surroundings. For this purpose, we introduce an equivalence relation for destinations in the network based on which we perform the aggregation. We succeed in designing an efficient algorithm that aggregates as many equivalent destinations as possible. Furthermore, we tackle a class of similar and frequently discussed problems concerning the aggregation of areal units into larger, connected regions. Since these problems are NP-complete, i.e. extraordinarily complex, we do not aim for an efficient exact algorithm (which is suspected not to exist) but present a strong improvement to existing exact approaches. In another setup, we present an efficient algorithm for the analysis of urban green-space supply. Performing a hypothetical assignment of citizens to available green spaces, it detects local shortages and patterns in the accessibility of green space within a city. Finally, we introduce and demonstrate a tool for detecting route preferences of cyclists based on a selection of given trajectories. Examining a set of criteria forming suitable candidates, we aggregate them efficiently to the best-fitting derivable criterion. Overall, we present exact approaches to various aggregation problems. In particular, the NP-complete problem we deal with firmly underscores, as expected, the need for heuristic approaches. For applications asking for an immediate solution, it may be reasonable to apply a heuristic approach. This holds in particular due to easy and generally applicable meta-heuristics being available. However, with this thesis, we argue for applying exact approaches if possible. The guaranteed superior quality of solutions speaks for itself. Besides, we give additional examples which show that exact approaches can be applied efficiently as well. |
Exact optimization algorithms for the aggregation of spatial data (2020)
