Sensoreinsatzplanung

Wenn Naturkatastrophen passieren, ist schnelle Hilfe gefragt. Besonders nach Überschwemmungen oder Erdbeben ist es sehr wichtig, so schnell wie möglich Informationen über das betroffene Gebiet zu erhalten. Dazu befasst sich Kim Berude mit dem mathematischen Modell und Optimierung zur Einsatzplanung von Sensoren und Geräten am IOSB, dem Fraunhofer-Institut für Optronik, Systemtechnik und Bildauswertung, in Karlsruhe und spricht mit Sebastian Ritterbusch darüber. Ursprünglich hat Kim Berude in Freiberg an der Technischen Universität Bergakademie Freiberg Angewandte Mathematik studiert, um dann auf eine Stellenausschreibung des IOSB die Chance zu nutzen, im Bereich der Operations Research etwas Praxisluft zu schnuppern. Die Aufgabe der Sensoreinsatzplanung führt direkt auf ein Vehicle Routing Problem bzw. Tourenplanungsproblem, ähnlich wie es täglich Paketdienstleister erfüllen. Die Hauptaufgabe liegt darin die Sensoren oder Assets möglichst effizient an die verschiedenen Zielorte zu bringen, die Herausforderung liegt aber darin, gleichzeitig verschiedene Nebenbedingungen zu erfüllen. Im Falle der Sensoreinsatzplanung können die Nebenbedingungen durch Reihenfolgen der Abarbeitung, Zeitfenster oder in begrenzen Resourcen der Fahrzeuge liegen, alles das muss geeignet modelliert werden. Eine vereinfachte Fassung des Tourenplanungsproblems ist das Traveling Salesperson Problem, bei dem die Aufgabe besteht, für eine handelnde Person, eine optimale kürzeste Route durch eine festgelegte Anzahl von Städten zu finden und jede dieser Städe nur einmal anzufahren. Schon dieses Problem ist in der Klasse der NP-Probleme, die nicht deterministisch in polynomialer Zeit lösbar erscheinen. Das bedeutet, dass die erforderliche Rechenleistung oder Rechenzeit für eine Lösung sehr schnell sehr extrem ansteigt. Entsprechend ist auch das allgemeinere Tourenplanungsproblem ebenso rechenintensiv. In der Sensoreinsatzplanung gibt es gegenüber dem Tourenplanungsproblem zusätzlich die besondere Herausforderung, dass eine sehr heterogene Flotte, also sehr unterschiedliche Sensoren und zugehörige Fahrzeuge, zum Einsatz kommen soll. In der mathematischen Optimierungstheorie nehmen diskrete Probleme eine besondere Stellung ein. Zunächst einmal muss man sich bewusst werden, dass durch jedes Fahrzeug und jede Nebenbedingung weitere Variablen und Gleichungen entstehen, und damit eine höhere Detailtiefe der Modellierung sich unmittelbar auf die Dimension des zu lösenden Problems auswirkt. Ein Standardverfahren um lineare kontinuierliche Optimierungsprobleme zu lösen ist das Simplex-Verfahren. Das funktioniert aber nicht für diskrete Probleme, da es beliebige Zwischenwerte als Ergebnisse erhalten kann. Man könnte alle diskreten Möglichkeiten natürlich auch ausprobieren, das könnte aber sehr lange dauern. Eine Lösung sind hier die Branch-and-Bound-Verfahren, die das Problem zunächst kontinuierlich lösen, um eine untere Grenze des erwartbaren Ergebnisses zu erhalten. (...)