Exact Optimization Algorithms for the Aggregation of Spatial Data

Abstract

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. <br /> In this thesis, we identify aggregation problems dealing with spatial data and formalize them as 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 may be 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. <br /> 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. <br /> 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. <br /> 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. <br /> 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. <br /> 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. <br /> 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.

<strong>Exakte Optimierungsverfahren zur Aggregation räumlicher Daten</strong> <br /> Die Aggregation räumlicher Daten ist ein verbreitetes Problem in der Geoinformatik. Dahinter verbirgt sich das Zusammenfassen von Objekten oder Funktionen zur Gewinnung einer weniger komplexen Repräsentation. Dazu gibt es verschiedene Anlässe: Weniger komplexe Daten ermöglichen oft eine einfachere Verarbeitung durch Algorithmen. Zudem erlauben sie eine vereinfachte Darstellung, wie sie im Bereich der Kartengeneralisierung Ziel ist. <br /> In dieser Arbeit werden Probleme der Aggregation räumlicher Daten untersucht. Diese werden zunächst als Optimierungsprobleme formalisiert. Dazu wird jeweils eine Funktion definiert, die die Qualität gültiger Lösungen bewertet. Anschließend wird ein Algorithmus präsentiert, der stets eine Lösung mit bestmöglicher Bewertung findet. Diese Gütegarantie geht im Allgemeinen auf Kosten der Berechnungsdauer, was ein Grund für die weit verbreitete Anwendung von Heuristiken ist. Jedoch liegen die Vorteile einer optimalen Lösung auf der Hand: Manchmal ist eine "gute" Lösung nicht ausreichend. Darüber hinaus können exakte Lösungen zum Vergleich herangezogen werden, um nicht-exakte Verfahren hinsichtlich ihrer Qualität zu bewerten. Dies ist besonders für Heuristiken interessant, deren Lösungsqualität nur empirisch ermittelbar ist. Eine weitere Stärke exakter Verfahren ist, dass sie zur Überprüfung zugrunde liegender Modelle herangezogen werden können. <br /> In dieser Arbeit werden aus dieser Motivation heraus entstandene Aggregationsverfahren vorgestellt. Durch den räumlichen Charakter der untersuchten Daten spielen dabei neben semantischen auch geometrische Aspekte eine Rolle, wenn auch in unterschiedlichen Maßen. <br /> Das erste vorgestellte Problem betrifft die Visualisierung von Straßennetzen in Navigationskarten. Bei gegebenem Standort wird eine übersichtliche Darstellung der Umgebung gesucht. Zu diesem Zweck wird eine Äquivalenzrelation auf möglichen Navigationszielen eingeführt, die die Grundlage der Aggregation bildet. Der vorgestellte Algorithmus aggregiert effizient die größtmögliche Anzahl äquivalenter Ziele. <br /> Des Weiteren wird eine Klasse aus der Literatur bekannter Problemen behandelt, welche die Aggregation von Flächen in größere, zusammenhängende Regionen betreffen. Diese Probleme sind NP-vollständig, d.h. effiziente Algorithmen existieren vermutlich nicht. Es gelingt jedoch, bestehende exakte Verfahren um circa eine Größenordnung zu beschleunigen. <br /> Ein weiteres betrachtetes Problem betrifft die Analyse der Verfügbarkeit von Grünflächen im urbanen Raum. Dazu werden, hypothetisch, mittels Flussnetzwerk Bewohner Grünflächen zugewiesen. Dadurch werden lokale Defizite sowie Muster in der Zugänglichkeit sichtbar. <br /> Abschließend wird ein Mittel zum Erlernen von Präferenzen bei der Routenplanung vorgestellt. Basierend auf einer Auswahl an Trajektorien werden zwei mögliche Kriterien untersucht. Diese werden anschließend durch Linearkombination effizient zum bestmöglichen, ableitbaren Kriterium aggregiert. <br /> Zusammenfassend werden in dieser Arbeit exakte Algorithmen als Antwort auf verschiedene Aggregationsprobleme in der Geoinformatik präsentiert. Insbesondere das betrachtete NP-vollständige Problem untermauert, wie erwartet, die Notwendigkeit heuristischer Verfahren. Diese sind gerade bei zeitkritischen Anwendungen von großer Bedeutung und insbesondere dank universell anwendbarer Metaheuristiken sehr beliebt. Die Ergebnisse dieser Arbeit sind jedoch ein weiterer Grund, bei der Suche nach Lösungsverfahren für Aggregationsprobleme mit exakten Verfahren zu beginnen. Die Gütegarantie spricht für sich. In einigen Fällen wurden sogar neue Algorithmen, die effizient und exakt sind, gefunden.