Sensoreinsatzplanung
Wenn Naturkatastrophen passieren, ist schnelle Hilfe gefragt. Besonders nach \xdcberschwemmungen oder Erdbeben ist es sehr wichtig, so schnell wie m\xf6glich Informationen \xfcber das betroffene Gebiet zu erhalten. Dazu befasst sich Kim Berude mit dem mathematischen Modell und Optimierung zur Einsatzplanung von Sensoren und Ger\xe4ten am IOSB, dem Fraunhofer-Institut f\xfcr Optronik, Systemtechnik und Bildauswertung, in Karlsruhe und spricht mit Sebastian Ritterbusch dar\xfcber. Urspr\xfcnglich hat Kim Berude in Freiberg an der Technischen Universit\xe4t 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\xfchrt direkt auf ein Vehicle Routing Problem bzw. Tourenplanungsproblem, \xe4hnlich wie es t\xe4glich Paketdienstleister erf\xfcllen. Die Hauptaufgabe liegt darin die Sensoren oder Assets m\xf6glichst effizient an die verschiedenen Zielorte zu bringen, die Herausforderung liegt aber darin, gleichzeitig verschiedene Nebenbedingungen zu erf\xfcllen. Im Falle der Sensoreinsatzplanung k\xf6nnen 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\xfcr eine handelnde Person, eine optimale k\xfcrzeste Route durch eine festgelegte Anzahl von St\xe4dten zu finden und jede dieser St\xe4de nur einmal anzufahren. Schon dieses Problem ist in der Klasse der NP-Probleme, die nicht deterministisch in polynomialer Zeit l\xf6sbar erscheinen. Das bedeutet, dass die erforderliche Rechenleistung oder Rechenzeit f\xfcr eine L\xf6sung sehr schnell sehr extrem ansteigt. Entsprechend ist auch das allgemeinere Tourenplanungsproblem ebenso rechenintensiv. In der Sensoreinsatzplanung gibt es gegen\xfcber dem Tourenplanungsproblem zus\xe4tzlich die besondere Herausforderung, dass eine sehr heterogene Flotte, also sehr unterschiedliche Sensoren und zugeh\xf6rige Fahrzeuge, zum Einsatz kommen soll. In der mathematischen Optimierungstheorie nehmen diskrete Probleme eine besondere Stellung ein. Zun\xe4chst einmal muss man sich bewusst werden, dass durch jedes Fahrzeug und jede Nebenbedingung weitere Variablen und Gleichungen entstehen, und damit eine h\xf6here Detailtiefe der Modellierung sich unmittelbar auf die Dimension des zu l\xf6senden Problems auswirkt. Ein Standardverfahren um lineare kontinuierliche Optimierungsprobleme zu l\xf6sen ist das Simplex-Verfahren. Das funktioniert aber nicht f\xfcr diskrete Probleme, da es beliebige Zwischenwerte als Ergebnisse erhalten kann. Man k\xf6nnte alle diskreten M\xf6glichkeiten nat\xfcrlich auch ausprobieren, das k\xf6nnte aber sehr lange dauern. Eine L\xf6sung sind hier die Branch-and-Bound-Verfahren, die das Problem zun\xe4chst kontinuierlich l\xf6sen, um eine untere Grenze des erwartbaren Ergebnisses zu erhalten. (...)