Solver-Informed Evolution of Interpretable Dispatching Rules for the Stochastic Team Orienteering Problem with Time Windows

Stellen Sie sich eine Flotte von Fahrzeugen vor, die gegen die Uhr rennt, um eine verstreute Sammlung von Standorten zu besuchen, von denen jeder eine andere Belohnung bietet. Das Ziel ist einfach: So viel Wert wie möglich sammeln, bevor die Zeit abläuft. Doch die Welt ist kein Tabellenkalkulationsprogramm. Die Zeit, die benötigt wird, um eine Aufgabe an einem bestimmten Ort abzuschließen, ist ungewiss; eine plötzliche Windböe könnte eine Drohne verzögern, oder raue See könnte ein Boot verlangsamen. Zudem ist jeder Standort nur für ein bestimmtes Zeitfenster verfügbar. Wenn ein Fahrzeug zu früh ankommt, muss es warten; wenn es zu spät ankommt, ist die Gelegenheit für immer verloren. Dies ist das Wesen einer komplexen logistischen Herausforderung, die als Team-Orienteering-Problem mit Zeitfenstern bekannt ist. In der realen Welt spielt sich dieses Szenario ab, wenn Feuerwehrleute versuchen, einen Waldbrand einzudämmen, Ölbekämpfungsteams versuchen, einen Ölteppich einzudämmen, bevor er das Ufer erreicht, oder medizinische Teams Patienten innerhalb kritischer Zeitrahmen besuchen müssen. Die Schwierigkeit besteht darin, den nächsten Schritt sofort zu tätigen, ohne genau zu wissen, wie lange die aktuelle Aufgabe dauern wird, und ohne den Luxus eines Supercomputers, den gesamten Plan jede Sekunde neu zu berechnen.

Jahrelang versuchten Forscher, dies zu lösen, indem sie Computer lehrten, einfache Entscheidungsregeln zu entwickeln. Diese Regeln fungieren wie ein Verkehrsleiter, der die aktuelle Situation betrachtet und sofort entscheidet, welchen Kunden als Nächstes besucht werden soll. Die bisher erfolgreichste Methode, bekannt als NS-GP, stützt sich auf einen festen Satz von elf Basisfunktionen – wie etwa die Entfernung zu einem Kunden oder die verbleibende Zeit –, um diese Entscheidungen zu treffen. Obwohl dieser Ansatz effektiv ist, hat er eine Obergrenze. Er verwendet einen begrenzten Wortschatz, um die Welt zu beschreiben, ganz so, als würde man versuchen, einen Roman mit nur hundert Wörtern zu schreiben. Die Forscher hinter dieser neuen Studie, angeführt von Augusto Mendonça und seinem Team an Universitäten in Brasilien, stellten eine kühne Frage: Was wäre, wenn der Computer einen reicheren Wortschatz erlernen könnte, indem er beobachtet, wie ein Experte das Problem offline löst? Sie wollten sehen, ob sie die verborgene Logik hochwertiger Lösungen extrahieren und diese Erkenntnisse in einfache, lesbare Regeln verwandeln könnten, die in Echtzeit funktionieren.

Das Team entwickelte eine neue Methode namens SI-GP, was für Solver-Informed Genetic Programming steht. Der Prozess beginnt nicht mit dem Raten des Computers, sondern mit dem Beobachten durch den Computer. Zuerst nutzten die Forscher leistungsstarke, Hochgeschwindigkeits-Solver, um die besten möglichen Routen für eine Reihe von vierzig verschiedenen Testproblemen zu finden, unter der Annahme, dass alles perfekt ablaufen würde. Dann spielten sie diese perfekten Routen in einer simulierten Welt nach, in der Verzögerungen zufällig auftraten, genau wie sie in der Realität vorkommen. Durch den Vergleich der perfekten Pläne mit dem, was tatsächlich geschah, identifizierte das Team spezifische Operationen, die die perfekten Pläne ausführten, aber die Standardregeln übersahen. Zum Beispiel bemerkten sie, dass die besten Pläne oft mehrere Schritte vorausblickten, um zu sehen, welche Belohnungen noch erreichbar wären, oder dass sie das Risiko berechneten, eine zukünftige Gelegenheit zu verlieren, wenn sie sich auf eine aktuelle Entscheidung einließen.

Aus diesen Beobachtungen bauten die Forscher eine neue Bibliothek aus achtzehn Entscheidungsmerkmalen auf. Sechzehn davon basierten auf etablierten Konzepten aus der Terminplanung, während zwei völlig neue Kombinationen waren, die darauf ausgelegt waren, die Kosten einer Entscheidung gegen den potenziellen Gewinn abzuwägen. Dieser neue Wortschatz gab dem Computer eine viel nuanciertere Möglichkeit, das Problem zu verstehen. Doch mehr Optionen zu haben bedeutet nicht automatisch bessere Ergebnisse; manchmal verwirren zu viele Auswahlmöglichkeiten das System. Um dies zu lösen, setzte das Team eine zweite Ebene der Intelligenz ein, um die beste Teilmenge dieser Merkmale für jedes spezifische Problem auszuwählen. Sie behandelten den Auswahlprozess wie ein Turnier, bei dem verschiedene Kombinationen von Merkmalen entwickelt und streng getestet wurden. Dies wurde durch eine eigens entwickelte Engine ermöglicht, die auf Grafikkarten läuft und es ihnen erlaubt, tausende Kombinationen in der Zeit zu testen, die es früher brauchte, um nur eine einzige zu testen.

Die Ergebnisse waren beeindruckend. Bei den vierzig Benchmark-Problemen war die neue Methode nie schlechter als der alte Standard. In achtunddreißig der Fälle entwickelte das System eine neue Regel, die den bisherigen Bestwert übertraf. Im Durchschnitt verbesserten die neuen Regeln die insgesamt gesammelte Belohnung um 1,0 Prozent über alle Tests hinweg und um 1,3 Prozent in den Problemen, bei denen es noch Raum für Verbesserungen gab. In zehn spezifischen Fällen war die Verbesserung statistisch signifikant und groß genug, um als bedeutender Durchbruch für dieses spezifische Szenario zu gelten. Vielleicht am wichtigsten ist, dass die neuen Regeln einfach und lesbar blieben. Es waren keine Black-Box-Algorithmen, die niemand verstehen konnte; es waren kompakte mathematische Ausdrücke, die ein Mensch lesen und verifizieren konnte. In vielen Fällen waren die neuen Regeln auch stabiler und lieferten konsistente Ergebnisse, selbst wenn die zufälligen Verzögerungen variierten, während die alten Regeln manchmal wild zwischen gut und schlecht schwankten.

Die Studie zeigte auch auf, warum die Verbesserungen stattfanden. Die neuen Regeln waren besonders effektiv in Situationen, in denen das Basissystem Schwierigkeiten hatte, jeden möglichen Kunden zu besuchen. In diesen „ungesättigten“ Szenarien ermöglichte der neue Wortschatz dem System, komplexe Abwägungen zu navigieren, wie etwa einen fernen, hochwertigen Kunden zu besuchen, selbst wenn dies bedeutete, einen nahe gelegenen, minderwertigen Kunden auszulassen. Die Forscher fanden heraus, dass die neuen Merkmale dem System halfen, seine Suche zu regularisieren, was bedeutete, dass es weniger wahrscheinlich in einer lokalen Falle stecken blieb und mit größerer Wahrscheinlichkeit einen robusten Pfad vorschritt. Die Methode arbeitete dadurch, dass sie aus der Struktur hochwertiger Lösungen lernte, ohne sie einfach zu kopieren. Sie versuchte nicht, die exakte Route des Expertenplaners nachzuahmen; stattdessen lernte sie die Prinzipien, die jene Routen erfolgreich machten, und wandte sie auf eine neue, unsichere Umgebung an.

Diese Arbeit zeigt, dass es möglich ist, die Lücke zwischen komplexer Offline-Optimierung und schneller Online-Entscheidungsfindung zu schließen. Indem sie die Erkenntnisse aus hochwertigen Solvern nutzten, um einen besseren Wortschatz aufzubauen, und indem sie sorgfältig die richtigen Werkzeuge für jede spezifische Aufgabe auswählten, schufen die Forscher ein System, das sowohl leistungsstark als auch transparent ist. Das Endprodukt ist ein Satz von Entscheidungsregeln, die direkt in Fahrzeuge oder Drohnen eingebettet werden können, sodass diese in Mikrosekunden intelligente Entscheidungen treffen können, ohne eine Verbindung zu einem zentralen Computer herstellen oder komplexe Simulationen durchführen zu müssen. Der Ansatz deutet einen neuen Weg für künstliche Intelligenz in der Logistik an: einen, der Interpretierbarkeit und Anpassungsfähigkeit schätzt und sicherstellt, dass die Maschinen, die kritische Entscheidungen treffen, von den Menschen, die auf sie angewiesen sind, auch verstanden werden können. Die Forscher haben ihren Code, ihre Daten und die spezifischen entdeckten Regeln öffentlich zugänglich gemacht und laden dazu ein, auf diesem Fundament für zukünftige Herausforderungen in unsicheren Umgebungen aufzubauen.