Informatik, Andor und Python – Teil 3

Mit den „Legenden von Andor“ kann man auch ein paar spaßige Probleme der Theoretischen Informatik untersuchen. Im ersten Teil hatte ich dazu was zum Dijkstra-Algorithmus geschrieben, im zweiten Teil dann zum Traveling Salesman Problem. Geht es noch schwieriger? Es geht 🙂

Vier Helden gleichzeitig

Beim TSP sucht man die kürzeste Route, um verschiedene Punkte auf der Karte aufzusuchen. Aber was wäre, wenn man mehr als einen Akteur gleichzeitig zur Verfügung hätte? Dann landet man beim Vehicle Routing Problem (VRP). Praktischerweise hat der Solver aus den Google OR-Tools auch dafür schon Funktionen eingebaut. Genau genommen muss man nur den Parameter num_vehicles auf >1 einstellen 🙂 Der restliche Code muss dann ein bisschen angepasst werden, um mit den Routen für die unterschiedlichen Vehicles umgehen zu können, das hatte ich aber im Code aus dem zweiten Teil schon mal vorweg genommen.

Eine interessante Frage ist nun aber, wonach eigentlich optimiert werden soll: Standardmäßig wird die Summe der Längen aller Routen minimiert. Das führt aber eher selten zum gewünschten Ergebnis: Damit fährt einfach ein Fahrzeug die komplette Route ab, und alle anderen bleiben zu Hause. In unserem Fall kann jeder Held pro Zeitschritt („eine Stunde“ im Spiel) ein Feld weit laufen. Alle Helden laufen dabei natürlich gleichzeitig. Ausschlaggebend für die Gesamtzeit ist damit also die Länge der längsten Route. Auch das kann der Solver berechnen, dafür muss aber etwas Code hinzugefügt werden:

num_heros = 4
#[...]
routing.AddDimension(transit_callback_index, 0, 500, True, 'Distance')
distance_dimenstion = routing.GetDimensionOrDie('Distance')
distance_dimenstion.SetGlobalSpanCostCoefficient(100)

Ehrlich gesagt weiß ich auch nicht so genau, was hier passiert, der Code ist aus dem Demo-Code entnommen. Der Solver kann irgendwie mit verschiedenen Dimensionen umgehen, die gleichzeitig optimiert werden. Der Faktor 100 sorgt dafür, dass die maximale Länge der dominante Faktor ist.

Mit diesen Änderungen kriegen wir dann auch eine Lösung für vier Helden, die gleichzeitig unterwegs sind:

Found solution with score 1140
[57, 6, 2, 0, 5, 24]
[57, 64, 71, 40]
[57, 32, 28, 18, 19, 72]
[57, 84]
Number of hours of this route: 11

Der „Score“ ist dann auch nicht mehr einfach die Länge der Route, sondern wohl die Länge mal 100 plus etwas, oder so 🙂

Andere Suchstrategie

Aktuell findet das Programm noch sehr schnell eine Lösung, allerdings kann es sich dabei wohl theoretisch in einem lokalen Minimum verfangen. Wenn man etwas mehr Zeit hat, kann man die auch nutzen, um weitere Optionen zu explorieren. Dazu ändern wir die „Metaheuristik“ auf „Guided Local Search“ (Doku):

search_parameters.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = 3

Da der Solver jetzt potenziell alle Möglichkeiten untersucht, sollte man tunlichst ein Zeitlimit angeben, hier 3 Sekunden. Ich habe das Programm auch testweise mal für 30 Sekunden laufen lassen, ein besseren Ergebnis wird allerdings nicht gefunden. Vermutlich ist die Lösung also schon optimal 🙂

Ausblick

Damit sind alle drei Rätsel, die ich mir überlegt hatte gelöst. Ich muss gestehen, dass ich nicht gedacht hätte, dass das mit so wenig Aufwand geht, die passende Python-Bibliothek hat hier auf jeden Fall sehr geholfen. Damit ist übrigens noch deutlich mehr möglich, unter anderem kann man Zeitslots vorgeben, also bestimmte Felder nur zu bestimmten Zeiten besuchbar machen. Falls es keine Lösung gibt, kann man auch noch Strafen vergeben, um die „unwichtigsten“ Stops fallen zu lassen, und vieles mehr. Das ganze zielt also sehr in Richtung Tourenplanung bei Paketdiensten. Mal schauen wann/ob meine drei Rätsel gelöst werden 🙂

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.