Wegeoptimierung

[Der-Dennis]

Hallo Linuchs,

Die Termine werden in mehreren Buchungsläufen ermittelt. Da gibt es die grünen, das sind Vorträge und Workshops nur zu bestimmten Zeiten. Die werden zuerst gebucht. Besucher sind nur zu bestimmten Zeiten anwesend (ein Tag oder beide Tage, später kommend, eher gehend). Buchungen für Besucher-Gruppen müssen berücksichtigen, dass alle Teilnehmer der Gruppe diesen Termin frei haben. Und, und, und.

Du sagst es: Und, und, und. Wenn Du Dich wirklich daran wagen möchtest, musst Du Dir darüber im Klaren sein, dass das eine äußerst komplexe und sehr schwierig zu lösende Problemstellung ist. Die Wegoptimierung ist wahrscheinlich das mit Abstand am einfachsten zu lösende Problem. Eigentlich hast Du aber ein klassisches Scheduling-Problem, bei welchem die Wegoptimierung nur einen kleinen Teil darstellt.

Du möchtest die Messestände und Veranstaltungen (resource) optimal ausnutzen, d.h. die Besucher (job) sollen optimal auf Ressourcen verteilt werden (task). Dabei muss eine Vielzahl von Restriktionen (constraints) beachtet werden. Du hast also eine NP-vollständige Problemstellung.

Exakte Verfahren, welche immer die gültige „beste Lösung“ finden (z.B. Brute Force oder Branch-and-Bound), scheiden daher aus zwei Gründen aus: Erstens benötigen sie viel zu viel Rechenzeit und zweitens kannst Du nicht garantieren, dass es überhaupt eine Lösung gibt, welche alle Restriktionen auflösen kann.

Das ist auch eigentlich der wichtigste Punkt: Du musst Dir bevor Du überhaupt anfangen kannst über alle möglichen Restriktionen im Klaren sein. Außerdem darüber, was passieren soll, wenn irgendeine Restriktion auf keinen Fall eingehalten werden kann (Beispiel: Ein Besucher kann zeitlich nicht an zwei Orten gleichzeitig sein).

Zuletzt musst Du Dir vorher Gedanken machen, mit welchem Optimierungsergebnis Du zufrieden wärst. Üblicherweise definiert man Zielgrößen (objectives bzw. targets oder goals), bei deren Erreichen Gewinne (rewards) vergeben werden. Ein Algorithmus versucht dann, diese Gewinne zu maximieren. Dass Du Dir vorher genau Gedanken über das alles machen und mögliche Szenarien entwickeln musst, ist u.a. im No-free-Lunch-Theorem beschrieben: Es existiert kein Algorithmus, der für alle Fälle am besten geeignet ist.

Was Du benötigst sind also Heuristiken, welche die Problemstellung optimieren. Unterscheiden musst Du zwischen Eröffnungs- und Verbesserungsheuristiken. Bei der Eröffnung wird überhaupt erstmal eine gültige Lösung erzeugt, die anschließend verbessert werden kann. Deine zufällige Terminvergabe wäre ein Beispiel dafür, würdest Du auch die Restriktionen beachten; i.Allg. ist dieses Vorgehen aber das denkbar schlechteste.

An anderer Stelle hattest Du gefragt, wie Navis das machen. @Gunnar Bittersmann hatte zudem das Problem des Handlungsreisenden ins Spiel gebracht. Navis haben üblicherweise einen vielstufigen Optimierungsprozess, d.h. sie verwenden mehrere Optimierungsstufen hintereinander. Grundlage dafür ist ein - von @Felix Riesterer angesprochnes - engmaschiges Netz von Wegpunkten. Diese Wegpunkte bilden Knoten und werden durch Kanten miteinander verbunden - @osm sprach den Dijkstra-Algorithmus an, bei welchem das recht anschaulich ist. Die insgesamt eingesetzten Algorithmen orientieren sich dann am Problem des Handlungsreisenden ohne Rückkehr. Zur Planung der Route sind die Straßen und Wegpunkte zusätzlich gewichtet, was den angesprochenen rewards entspricht.

So, nach dem ganzen allgemeinen Vorgeplänkel: Aus meiner eigenen Erfahrung heraus raus kann ich Dir empfehlen, Dich zuerst einmal mit dem Problem des Handlungsreisenden und den zugehörigen Algorithmen zu beschäftigen. Das Problem ist gut untersucht und man kann dabei sehr viel lernen. Alles andere ist für den Anfang viel zu viel und man wird nur mit großen Schwierigkeiten überhaupt etwas brauchbares produzieren.

Für den ersten Einstieg könntest Du Dir für die Eröffnung sowas wie den Sweep-Algorithmus oder die Nächster-Nachbar-Heuristik ansehen. Für die Verbesserung bspw. Simulierte Abkühlung, Evolutionäre und dabei insbes. Genetische Algorithmen oder die Ameisenkolonie (hier übrigens eine sehr schicke, weil anschauliche, Implementierung). Darüber hinaus gibt es noch unzählige andere Verfahren.

Wie gesagt halte ich persönlich das für einen guten Start um sich mit der Materie auseinanderzusetzen. Wenn Du konkrete Fragen hast, kann man Dir auch sicher einen Wink in die richtige Richtung geben. Ansonsten ist aus meiner Sicht die Problemstellung aber zu komplex, um allgemein hier im Forum besprochen werden zu können.

Gruß und viel Erfolg
Dennis