KAYROS: An Anytime and Exact Open-Source Solver for Duration-Minimization Time-Dependent Vehicle Routing. A Technical Report and a Case Study in Human-AI Engineering

Stellen Sie sich vor, Sie sind der Disponent für eine Flotte von Lieferwagen in einer geschäftigen Stadt. Ihr Ziel ist einfach: Pakete zu Kunden bringen und die Fahrer so schnell wie möglich nach Hause bringen, um Kosten bei den Löhnen zu sparen. Aber es gibt einen Haken: Die Stadt ist lebendig. Eine Straße, die um 8:00 Uhr morgens zehn Minuten dauert, kann um 9:00 Uhr wegen des Berufsverkehrs schon vierzig Minuten dauern. Das ist die Welt des zeitabhängigen Fahrzeug-Routing (Time-Dependent Vehicle Routing). Es ist ein klassisches Rätsel auf dem Gebiet der Operations Research, was im Grunde die Wissenschaft davon ist, die bestmöglichen Entscheidungen zu treffen, wenn man über begrenzte Ressourcen und komplexe Regeln verfügt.

Seit Jahrzehnten sind Computer großartig darin, diese Rätsel zu lösen, aber meistens mit einer großen Vereinfachung: Sie tun so, als wäre der Verkehr statisch, wie eine Karte, auf der Straßen sich niemals verändern. Das echte Leben ist jedoch ein fließender Fluss, kein stiller Teich. Um das Rätsel perfekt zu lösen, muss man genau wissen, wann ein Lkw das Depot verlässt, denn fünf Minuten später loszufahren, könnte bedeuten, in einen Stau zu geraten, der die Fahrt um eine Stunde verlängert, oder es könnte bedeuten, eine rote Ampel zu umgehen, die zehn Minuten spart. Die Herausforderung besteht darin, die Mathematik zu finden, um die „perfekte“ Abfahrtszeit für jeden einzelnen Lkw unter Einhaltung der Zeitfenster der Kunden und der Verkehrsmuster zu berechnen, was unglaublich schwierig ist. Es ist, als versuche man, einen Rubik's Cube zu lösen, bei dem sich die Farben ständig verschieben, während man die Seiten dreht.

Hier kommt ein neues Werkzeug namens KAYROS ins Spiel. Stellen Sie sich KAYROS als einen superintelligenten, unermüdlichen Verkehrswizard vor, der nicht nur rät, sondern den absolut besten Zeitplan berechnet. Aber hier ist der magische Trick: Er liefert nicht nur eine „gut genug“ Antwort nach einer Stunde Wartezeit. Er beginnt bereits in der ersten Sekunde, in der er anfängt zu denken, immer bessere Antworten zu liefern, und wenn man ihn stoppt, nennt er einem die bisher beste Lösung. Noch cooler ist: Er kann beweisen, dass eine Lösung mathematisch perfekt ist und nicht nur ein Glückstreffer. Die Arbeit stellt auch einen massiven neuen Satz von Übungsrätseln namens Poryos2026 vor, die aus echten Stadtkarten erstellt wurden, um zu testen, ob diese Wizards tatsächlich ihren Job gut machen.

Die Magie von KAYROS: Ein Solver, der niemals schläft

Die Arbeit stellt KAYROS vor, ein Open-Source-Softwaretool, das entwickelt wurde, um das „zeitabhängige Fahrzeug-Routing-Problem“ zu lösen. Stellen Sie sich vor, Sie planen eine Autoreise für eine Flotte von Lieferfahrern. Sie haben eine Liste von Stopps, und jeder Stopp hat ein spezifisches Zeitfenster, in dem der Kunde zu Hause ist (z. B. „Paketzustellung nur zwischen 14:00 und 16:00 Uhr möglich“). Der knifflige Teil ist, dass die Zeit, die man zwischen den Stopps benötigt, davon abhängt, zu welcher Tageszeit man losfährt.

KAYROS ist besonders, weil es zwei Dinge gleichzeitig tut, was in der Welt der Computer-Solver eine seltene Kombination ist:

1. Es ist „Anytime“: Wenn Sie KAYROS ausführen, sitzt es nicht stundenlang still. Es spuckt sofort Lösungen aus. Die erste mag noch okay sein, aber die nächste ist besser, und die nächste noch besser. Es ist wie ein Koch, der eine Suppe probiert und kontinuierlich Gewürze hinzufügt; man kann das Kochen jederzeit stoppen und hat die bestmögliche Suppe für diese investierte Zeit.
2. Es ist „Exakt“: Wenn man es lange genug laufen lässt, rät es nicht nur die beste Antwort, sondern beweist, dass sie die bestmögliche ist. Es generiert ein „Zertifikat“, das wie ein mathematischer Beleg ist, den jeder überprüfen kann, um zu verifizieren, dass keine andere Route schneller sein könnte.

Die Autoren haben dieses Tool entwickelt, um völlig kostenlos und offen zu sein. Sie können es mit einem einzigen Befehl auf Ihrem Computer installieren, und es erfordert keine teure Spezialsoftware von großen Unternehmen. Es verwendet eine clevere Engine, die die Fahrzeit nicht als eine einzige Zahl behandelt, sondern als eine fließende Funktion – eine Linie, die je nach Tageszeit steigt und fällt. Dies ermöglicht es, komplexe, realitätsnahe Verkehrsmuster zu handhaben, bei denen eine Straße zu einer ganz bestimmten Minute plötzlich verstopft sein kann.

Die Geschichte der „Selbst-Refutation“: Wie sie ihren eigenen Fehler entdeckten

Einer der faszinierendsten Teile der Arbeit ist eine Geschichte über Ehrlichkeit. Die Autoren wollten sicherstellen, dass ihre „perfekten“ Zertifikate auch wirklich perfekt sind. Sie legten eine strenge Regel fest: Um zu behaupten, eine Lösung sei die beste, müssen vier verschiedene Computerläufe alle exakt dieselbe Antwort liefern.

Während eines Tests stießen sie auf ein Problem. KAYROS hatte 160 „Zertifikate“ ausgestellt, die behaupteten, bestimmte Routen seien die bestmöglichen. Doch dann fand ihr eigener „Anytime“-Solver (derjenige, der sich kontinuierlich verbessert) Routen, die tatsächlich schneller waren als jene „perfekten“ Zertifikate! Das war ein Schock. Es stellte sich heraus, dass KAYROS einen „Glättungstrick“ angewendet hatte, um plötzliche Sprünge in den Verkehrsdaten (wie eine Straße, die augenblicklich zum Parkplatz wird) zu handhaben. Dieser Trick war leicht fehlerhaft, was dazu führte, dass der Computer die Zeit falsch berechnete.

Die Autoren haben dies nicht versteckt. Sie haben alle 160 Zertifikate öffentlich zurückgezogen, den Code korrigiert, um diese „Sprünge“ exakt zu handhaben, und die Tests erneut durchgeführt. Diese Geschichte ist enthalten, um zu zeigen, dass ihr System robust ist: Selbst wenn die KI einen Fehler macht, fangen die Verifizierungsregeln ihn ab, und die Wahrheit siegt.

Der neue Spielplatz: Poryos2026

Um zu testen, ob KAYROS wirklich funktioniert, brauchten die Autoren einen Spielplatz, der wie die reale Welt aussieht. Sie erschufen Poryos2026, eine Familie von 1.080 neuen Testrätseln. Anstatt künstliche, ausgedachte Karten zu verwenden, entnahmen sie echte Straßennetzwerke aus fünf Großstädten: Lyon, Paris, San Francisco, Hongkong und Tokio, unter Verwendung von OpenStreetMap (einer kostenlosen, gemeinschaftsbasierten Karte).

Anschließend fügten sie synthetische (künstliche, aber realistische) Verkehrsdaten, Kundenanforderungen und Zeitfenster zu diesen echten Karten hinzu. Dadurch entstand ein massiver Satz an Herausforderungen, die reale Geografie mit kontrollierten Verkehrsszenarien mischen. Für jedes dieser 1.080 Rätsel generierten sie eine „beste bekannte Lösung“ mit ihrem eigenen Solver. Dies bietet anderen Forschern eine faire und realistische Möglichkeit, ihre eigenen Werkzeuge gegen einen Standard zu testen, der die tatsächliche Stadtfahrt widerspiegelt und nicht nur abstrakte mathematische Probleme.

Das Team aus Mensch und KI

Vielleicht ist der einzigartigste Teil dieser Arbeit die Art und Weise, wie sie geschrieben wurde. Der Autor, ein Doktorand, arbeitete etwa zwei Wochen lang in einer intensiven Kollaboration mit einem KI-Agenten (einem Large Language Model). Der Mensch setzte die Ziele, traf die großen Entscheidungen und überprüfte die Arbeit, während die KI die Schwerstarbeit leistete: Code schreiben, tausende von Computerexperimenten durchführen und Fehler debuggen.

Der Autor schätzt, dass diese zweiwöchige Zusammenarbeit die Arbeit geleistet hat, die ihm allein zwei oder mehr Jahre gekostet hätte. Die Arbeit betont jedoch sehr sorgfältig, dass dies nicht bloß „schnelleres Tippen“ war. Der Mensch musste viel Zeit investieren, um die KI mit dem richtigen Kontext vorzubereiten, ihre Arbeit zu prüfen und sicherzustellen, dass die Ergebnisse wissenschaftlich fundiert sind. Die Arbeit argumentt, dass diese Art der Partnerschaft die Zukunft der Forschung ist, aber nur, wenn es strenge Regeln (wie das „Zertifikatssystem“) gibt, um zu verifizieren, dass die KI keine Fakten erfunden oder Ergebnisse halluziniert hat.

Was dies für die Zukunft bedeutet

Die Arbeit behauptet nicht, dass KAYROS der schnellste Solver der Welt ist (sie haben ihn noch nicht im direkten Vergleich mit allen anderen Tools getestet), noch behauptet sie, dass sie jedes mögliche Routing-Problem gelöst hat. Stattdessen bietet sie ein solides, verifiziertes und kostenloses Werkzeug, das endlich „exaktes“ und „Anytime“-Solving für komplexe, zeitabhängige Verkehrsprobleme ermöglicht.

Durch die Kombination eines leistungsstarken neuen Solvers, eines massiven neuen Satzes an realen Testfällen und einer transparenten Geschichte darüber, wie Menschen und KI verantwortungsbewusst zusammenarbeiten können, haben die Autoren ein neues Fundament für die Logistik geschaffen. Ob es darum geht, Pizza auszuliefern, Müllwagen zu verwalten oder Einsatzrouten für Notfallreaktionen zu planen – die Fähigkeit, die perfekte Abfahrtszeit zu berechnen und gleichzeitig zu wissen, dass man jederzeit anhalten und eine gute Antwort erhalten kann, ist ein bedeutender Schritt nach vorn für die Wissenschaft der Bewegung in unserer geschäftigen Welt.