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. Aus einer nicht ganzzahligen Lösungsvariable werden nun zunächst die nächsten ganzzahligen Varianten in einer Fallunterscheidung untersucht und das Problem in der reduzierten Fassung gelöst. Gibt es eine erste ganzzahlige Lösung, so gibt es nun Grenzen in beide Richtungen, die ermöglichen die Zahl der noch auszuprobierenden Varianten stark einzugrenzen. Sind alle Varianten probiert, bzw. durch die Abschätzungen ausgeschlossen, so erhält man deutlich effizienter eine Lösung als wenn man alle Varianten durchprobiert.

Der A*-Algorithmus ist sehr verwandt zum Branch-and-Bound-Verfahren und wird zum Routing auf Wegenetzen verwendet, beispielsweise im Terrain Projekt. Hier werden Grenzen durch Luftlinie und ebenso gefundene erste Lösungen bestimmt und ebenso recht schnell zum kürzesten Weg zwischen zwei Punkten zu gelangen. Eine Verfeinerung des Branch-and-Bound Verfahrens ist das Branch-and-Cut Verfahren, wo das durch lineare Ungleichungen entstehende Polyeder durch zusätzliche ganzzahlige Lösungen präferierende Einschränkungen weiter einschränkt, und damit das effiziente Simplex-Verfahren noch zielgerichteter einsetzt. Dieses Verfahren und weitere Verfeinerungen wurden im Podcast zu Operations Research mit Marco Lübbecke weiter erklärt.

Die bisher betrachteten Verfahren liefern immer exakt die optimale Lösung, sie sparen nur Zeit, in dem sie unnötige Berechnungen für schlechtere Varianten einsparen. Ist das Problem jedoch so komplex, dass die exakten Verfahren nicht in annehmbarer Zeit eine Lösung liefern, so können Heuristiken helfen, das Problem im Vorfeld in der Komplexität deutlich zu reduzieren. Ein Ansatz ist hier die Neighborhood Search, wo gerade in der Umgebung gefundener regulärer Lösungen nach besseren Varianten gesucht wird. Die spannende Frage ist hier, mit welchen Akzeptanzkriterien zielgerichtet nach passenden Lösungen in der Nachbarschaft gesucht werden.

Die Verfahren wurden an realitätsnahen Testfällen erprobt und evaluiert, wo Kim Berude in ihrer Diplomarbeit den Aspekt des Mehrfacheinsatzes gegenüber schon vorhandenen Optimierungslösungen hinzugefügt hat. Die Fragestellungen kommen keineswegs aus rein wissenschaftlichem Interesse, sondern werden am IOSB direkt benötigt. Die Messeinrichtungen kommen überall auf der Welt zum Einsatz, selbst bei Großveranstaltungen wie 'Das Fest' in Karlsruhe. Die Verfahren der Tourenplanung haben sehr viele Einsatzmöglichkeiten und ein berühmtes Beispiel ist, dass Speditionen durch Vermeiden von Linksabbiegen Zeit und Geld sparen.

Literatur und weiterführende Informationen

• P. Toth, D. Vigo: The vehicle routing problem, Society for Industrial and Applied Mathematics, 2002.
• I. H. Osman: Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Annals of operations research 41.4: 421-451, 1993.
• P. Shaw: Using constraint programming and local search methods to solve vehicle routing problems, International Conference on Principles and Practice of Constraint Programming. Springer, Berlin, Heidelberg, 1998.
• D. Pisinger, S. Ropke: Large neighborhood search, Handbook of metaheuristics. Springer US, 399-419, 2010.
• S. Ropke, D. Pisinger: An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation science 40.4: 455-472, 2006.
• Z. Wang, W. Liang, X. Hu: A metaheuristic based on a pool of routes for the vehicle routing problem with multiple trips and time windows, Journal of the Operational Research Society 65.1: 37-48, 2014.
• D. Cattaruzza, N. Absi, D. Feillet: Vehicle routing problems with multiple trips, 4OR 14.3: 223-259, 2016.
• Studiengang Angewandte Mathematik an der TU Freiberg

Podcasts

• M. Lübbecke: Operations Research, Gespräch mit S. Ritterbusch im Modellansatz Podcast, Folge 110, Fakultät für Mathematik, Karlsruher Institut für Technologie (KIT), 2016. http://modellansatz.de/operations-research
• S. Müller: Schulwegoptimierung, Gespräch mit G. Thäter im Modellansatz Podcast, Folge 101, Fakultät für Mathematik, Karlsruher Institut für Technologie (KIT), 2016. http://modellansatz.de/schulwegoptimierung
• U.Leyn: Verkehrswesen, Gespräch mit G. Thäter im Modellansatz Podcast, Folge 88, Fakultät für Mathematik, Karlsruher Institut für Technologie (KIT), 2016. http://modellansatz.de/verkehrswesen
• L. Osovtsova: Logistik, Gespräch mit G. Thäter im Modellansatz Podcast, Folge 33, Fakultät für Mathematik, Karlsruher Institut für Technologie (KIT), 2014. http://modellansatz.de/logistik