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. 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