Algorithmische Optimierung von Routenberechnungen für Behörden und Organisationen mit Sicherheitsaufgaben

Die Grundlage der vorliegenden Masterarbeit ist das am Fraunhofer-Institut für Verkehrs- und Infrastruktursysteme IVI entwickelte Einsatzführungssystem MobiKat und insbesondere der darin integrierte Routingdienst, der für die Anwendung im zivilen Katastrophenschutz konzipiert wurde. Ziel der Arbeit war die Untersuchung, inwiefern der vorhandene Algorithmus optimiert werden kann. Dabei sollte der Fokus primär auf der Laufzeit der Berechnung einer Routingabfrage mit großer räumlicher Distanz liegen.
Aus der Zielsetzung wurden zwei Forschungsfragen abgeleitet. Die erste sollte grundsätzlich untersuchen, welche Optimierungsansätze im Umfeld von Routinganwendungen existieren. Die dafür aufgestellte Methodik bestand aus zwei aufeinander aufbauenden Schritten: In einer systematischen Literaturrecherche wurden Optimierungsalgorithmen, die den aktuellen Stand der Forschung ausmachen, herausgearbeitet und anschließend einer umfassenden Bewertung unterzogen, um sie bezüglich ihrer Eignung für MobiKat zu untersuchen. Als Bewertungsgrundlage diente eine dafür aufgestellte Metrik, die sich aus der Zielsetzung und den Anforderungen des bestehenden Systems ergab.
Die zweite Forschungsfrage sollte ermitteln, wie eine prototypische Implementierung eines Ansatzes in MobiKat aussehen könnte. Das Ergebnis der Bewertung führte zur Auswahl eines Algorithmus für die Umsetzung namens Customizable Route Planning. Die methodische Vorgehensweise der zweiten Forschungsfrage bestand in der schrittweisen Implementierung des Ansatzes, um ihn anschließend umfassend testen zu können.
Als Ergebnis konnte aus dem durchgeführten Systemtest ermittelt werden, dass die Laufzeit der Berechnung einer Routingabfrage im neuen Algorithmus verbessert wurde. Die Routingpfade weisen jedoch gegenüber der Referenz bisweilen Abweichungen auf, daraus kann geschlossen werden, dass der Ansatz keine Garantie bietet, immer optimale Lösungen zu bestimmen.