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

Stel je voor dat je de dispatcher bent van een vloot bestelwagens in een bruisende stad. Je doel is simpel: pakketjes naar klanten brengen en de chauffeurs zo snel mogelijk weer naar huis krijgen om bespaart te maken op loonkosten. Maar er is een addertje onder het gras: de stad is in beweging. Een weg die tien minuten duurt om af te leggen om 8:00 uur, kan veertig minuten duren om 9:00 uur vanwege de ochtendspits. Dit is de wereld van Time-Dependent Vehicle Routing (tijdafhankelijke voertuigrouteplanning). Het is een klassieke puzzel in het vakgebied Operations Research, wat in feite de wetenschap is van het nemen van de beste beslissingen wanneer je te maken hebt met beperkte middelen en complexe regels.

Decennialang waren computers geweldig in het oplossen van deze puzzels, maar meestal met een grote vereenvoudiging: ze doen alsof het verkeer statisch is, als een kaart waarbij wegen nooit veranderen. Het echte leven is echter een stromende rivier, geen stilstaande vijver. Om de puzzel perfect op te lossen, moet je precies weten wanneer een vrachtwagen het depot verlaat, want vijf minuten later vertrekken kan betekenen dat je in een file terechtkomt die de rit met een uur verlengt, of het kan betekenen dat je een rood licht vermijdt dat je tien minuten bespaart. De uitdaging is dat de wiskunde om de "perfecte" vertrektijd voor elke enkele vrachtwagen te berekenen, terwijl je rekening houdt met de tijdvensters van klanten en verkeerspatronen, ontzettend moeilijk is. Het is alsof je een Rubiks kubus probeert op te lossen waarbij de kleuren blijven verschuiven terwijl je de zijden draait.

Hier komt een nieuwe tool genaamd KAYROS om de hoek kijken. Zie KAYROS als een superintelligente, onvermoeibare verkeerswizard die niet alleen gokt, maar de absoluut beste planning berekent. Maar hier is de truc: het geeft je niet alleen een "goed genoeg" antwoord nadat je een uur hebt gewacht; het begint vanaf de eerste seconde dat het begint na te denken steeds betere antwoorden te geven, en als je het stopt, vertelt het je de beste oplossing die het tot dan toe heeft gevonden. Nog cooler: het kan bewijzen dat een oplossing wiskundig perfect is, en niet slechts een gelukkige gok. Het artikel introduceert ook een enorme nieuwe set oefenpuzzels genaamd Poryos2026, gebouwd op basis van echte stadskaarten, om te testen of deze wizards ook echt goed zijn in hun werk.

De Magie van KAYROS: Een Solver die Nooit Slaapt

Het artikel introduceert KAYROS, een open-source softwaretool die is ontworpen om het "Time-Dependent Vehicle Routing Problem" op te lossen. Stel je voor dat je een roadtrip plant voor een vloot bezorgers. Je hebt een lijst met stops, en elke stop heeft een specifiek tijdvenster waarin de klant thuis is (bijv. "U kunt het pakketje alleen afleveren tussen 14:00 en 16:00 uur"). Het lastige deel is dat de tijd die nodig is om tussen de stops te rijden verandert, afhankelijk van hoe laat je vertrekt.

KAYROS is speciaal omdat het twee dingen tegelijk doet, wat een zeldzame combinatie is in de wereld van computer-solvers:

1. Het is "Anytime": Wanneer je KAYROS draait, blijft het niet urenlang stilzwijgend zitten. Het begint onmiddellijk oplossingen uit te spugen. De eerste is misschien oké, maar de volgende is beter, en de volgende weer nog beter. Het is als een chef die een soep proeft en continu kruiden toevoegt; je kunt het koken op elk gewenst moment stoppen, en je hebt dan de best mogelijke soep voor die hoeveelheid tijd.
2. Het is "Exact": Als je het lang genoeg laat draaien, raadt het niet alleen het beste antwoord, maar het bewijst dat het het beste antwoord is. Het genereert een "certificaat", wat een soort wiskundig bonnetje is dat iedereen kan controleren om te verifiëren dat er geen andere route mogelijk is die sneller is.

De auteurs hebben deze tool gebouwd om volledig gratis en open te zijn. Je kunt het met één commando op je computer installeren, en het vereist geen dure, geheime software van grote bedrijven. Het gebruikt een slimme engine die de reistijd niet behandelt als een enkel getal, maar als een vloeiende functie — een lijn die op en neer gaat afhankelijk van het tijdstip van de dag. Hierdoor kan het complexe, realistische verkeerspatronen aan waarbij een weg op een specifiek minuut plotseling verstopt raakt.

Het "Zelfweerleggingsverhaal": Hoe Ze Hun Eigen Fout Betrapten

Een van de meest fascinerende delen van het artikel is een verhaal over eerlijkheid. De auteurs wilden ervoor zorgen dat hun "perfecte" certificaten ook echt perfect waren. Ze stelden een strikte regel op: om te beweren dat een oplossing de beste is, moeten vier verschillende computerruns allemaal op exact hetzelfde antwoord uitkomen.

Tijdens een test ontdekten ze een probleem. KAYROS had 160 "certificaten" uitgegeven die beweerden dat bepaalde routes de best mogelijke waren. Maar toen vond hun eigen "anytime" solver (de solver die blijft verbeteren) routes die eigenlijk sneller waren dan die "perfecte" certificaten! Dit was een schok. Het bleek dat KAYROS een "smoothing"-truc had gebruikt om plotselinge sprongen in verkeersgegevens (zoals een weg die plotseling verandert in een parkeerplaats) af te handelen. Deze truc was net niet helemaal juist, waardoor de computer de tijd verkeerd berekende.

De auteurs verzwegen dit niet. Ze trokken publiekelijk alle 160 certificaten in, herstelden de code om deze "sprongen" exact af te handelen, en draaiden de tests opnieuw. Dit verhaal is opgenomen om te laten zien dat hun systeem robuust is: zelfs wanneer de AI een fout maakt, vangen de verificatieregels het op, en wint de waarheid.

De Nieuwe Speeltuin: Poryos2026

Om te testen of KAYROS echt werkt, hadden de auteurs een speeltuin nodig die eruitzag als de echte wereld. Ze creëerden Poryos2026, een familie van 1.080 nieuwe testpuzzels. In plaats van nep, verzonnen kaarten te gebruiken, haalden ze echte wegennetwerken uit vijf grote steden: Lyon, Parijs, San Francisco, Hongkong en Tokio, met behulp van data van OpenStreetMap (een gratis, door de gemeenschap gebouwde kaart).

Vervolgens voegden ze synthetische (nep maar realistische) verkeerssituaties, klantvraag en tijdvensters toe aan deze echte kaarten. Dit creëerde een enorme set uitdagingen die echte geografie combineren met gecontroleerde verkeersscenario's. Voor elke van deze 1.080 puzzels genereerden ze een "best-known solution" met behulp van hun eigen solver. Dit geeft andere onderzoekers een eerlijke en realistische manier om hun eigen tools te testen tegen een standaard die de werkelijke stedelijke rijomstandigheden weerspiegelt, in plaats van alleen abstracte wiskundige problemen.

Het Mens-AI Teamwerk

Misschien wel het meest unieke deel van dit artikel is hoe het geschreven is. De auteur, een PhD-student, werkte gedurende ongeveer twee weken in een intensieve samenwerking met een AI-agent (een large language model). De mens stelde de doelen, nam de grote beslissingen en controleerde het werk, terwijl de AI het zware werk deed: code schrijven, duizenden computerexperimenten uitvoeren en fouten opsporen.

De auteur schat dat deze tweeweekse samenwerking het werk heeft verricht dat hem normaal twee of meer jaar alleen zou hebben gekost. De auteur benadrukt echter dat dit niet simpelweg "sneller typen" was. De mens moest veel tijd besteden aan het voorbereiden van de AI met de juiste context, het controleren van het werk en het waarborgen dat de resultaten wetenschappelijk verantwoord waren. Het artikel betoogt dat deze vorm van partnerschap de toekomst van onderzoek is, maar alleen als er strikte regels zijn (zoals het "certificaat"-systeem) om te verifiëren dat de AI geen feiten verzint of resultaten hallucineert.

Wat Dit Betekent voor de Toekomst

Het artikel beweert niet dat KAYROS de snelste solver ter wereld is (ze hebben het nog niet head-to-head vergeleken met alle andere tools) en het beweert ook niet dat het alle mogelijke routingsproblemen heeft opgelost. In plaats daarvan biedt het een solide, geverifieerde en gratis tool die eindelijk "exact" en "anytime" oplossen naar complexe, tijdafhankelijke verkeersproblemen brengt.

Door een krachtige nieuwe solver, een enorme nieuwe set realistische testgevallen en een transparant verhaal over hoe mensen en AI verantwoordelijk kunnen samenwerken te combineren, hebben de auteurs een nieuw fundament gelegd voor logistiek. Of het nu gaat om het bezorgen van pizza, het beheren van vuilniswagens of het plannen van routes voor hulpdiensten, het vermogen om de perfecte tijd te berekenen om te vertrekken, terwijl je weet dat je op elk moment kunt stoppen en een goed antwoord krijgt, is een belangrijke stap voorwaarts in de wetenschap van het verplaatsen van zaken in onze drukke wereld.