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

Stel je een vloot voertuigen voor die tegen de klok strijdt om een verspreide verzameling locaties te bezoeken, waarbij elke locatie een andere beloning biedt. Het doel is simpel: zoveel mogelijk waarde verzamelen voordat de tijd op is. Maar de wereld is geen spreadsheet. De tijd die nodig is om een taak op een bepaalde plek te voltooien, is onzeker; een plotselinge windvlaag kan een drone vertragen, of ruwe zeeën kunnen een boot afremmen. Bovendien is elke locatie alleen beschikbaar binnen een specifieke tijdvenster. Als een voertuig te vroeg arriveert, moet het wachten; als het te laat arriveert, verdwijnt de kans voor altijd. Dit is de essentie van een complexe logistieke uitdaging die bekend staat als het team orienteering problem met tijdvensters. In de echte wereld speelt dit scenario zich af wanneer brandweerkorpsen proberen een bosbrand te beheersen, oliebestrijdingsteams racen om een olievlek in te dammen voordat deze de kust bereikt, of medische teams patiënten moeten bezoeken binnen kritieke tijdskaders. De moeilijkheid ligt in het feit dat de volgende stap direct moet worden genomen, zonder precies te weten hoe lang de huidige taak zal duren, en zonder de luxe van een supercomputer om elke seconde het hele plan opnieuw te berekenen.

Jarenlang hebben onderzoekers geprobeerd dit op te lossen door computers te leren eenvoudige beslisregels te evolueren. Deze regels fungeren als een verkeersregelaar die naar de huidige situatie kijkt en onmiddellijk beslist welke klant als volgende bezocht moet worden. De meest succesvolle methode tot nu toe, bekend als NS-GP, vertrouwt op een vaste set van elf basiskenmerken—zoals hoe ver een klant verwijderd is of hoeveel tijd er nog over is—om deze keuzes te maken. Hoewel effectief, heeft deze aanpak een plafond. Het gebruikt een beperkte woordenschat om de wereld te beschreven, vergelijkbaar met het proberen te schrijven van een roman met slechts honderd woorden. De onderzoekers achter deze nieuwe studie, onder leiding van Augusto Mendonça en zijn team aan universiteiten in Brazilië, stelden een gedurfde vraag: wat als de computer een rijkere woordenschat zou kunnen leren door te kijken naar hoe een expert-planner het probleem offline oplost? Ze wilden zien of ze de verborgen logica van hoogwaardige oplossingen konden extraheren en die inzichten konden omzetten in eenvoudige, leesbare regels die in real-time werken.

Het team ontwikkelde een nieuwe methode genaamd SI-GP, wat staat voor Solver-Informed Genetic Programming. Het proces begint niet met de computer die gokt, maar met de computer die kijkt. Eerst gebruikten de onderzoekers krachtige, hogesnelheidssolvers om de beste mogelijke routes te vinden voor een reeks van veertig verschillende testproblemen, uitgaande van een perfect scenario. Vervolgens speelden ze deze perfecte routes af in een gesimuleerde wereld waar vertragingen willekeurig optraden, precies zoals in de werkelijkheid. Door de perfecte plannen te vergelijken met wat er daadwerkelijk gebeurde, identificeerde het team specifieke operaties die de perfecte plannen uitvoerden, maar die de standaardregels misten. Zo merkten ze bijvoorbeeld op dat de beste plannen vaak enkele stappen vooruit keken om te zien welke beloningen nog bereikbaar zouden zijn, of dat ze het risico berekenden om een toekomstige kans te verliezen als ze zich aan een huidige taak zouden committeren.

Vanuit deze observaties bouwden de onderzoekers een nieuwe bibliotheek van achttien beslissingskenmerken. Zestien hiervan waren gebaseerd op gevestigde concepten uit de planning, terwijl twee geheel nieuwe combinaties waren ontworpen om de kosten van een beslissing af te wegen tegen de potentiële winst. Deze nieuwe woordenschat gaf de computer een veel meer genuanceerde manier om het probleem te begrijpen. Het hebben van meer opties betekent echter niet automatisch betere resultaten; soms verwarren te veel keuzes het systeem. Om dit op te lossen, gebruikte het team een tweede laag intelligentie om de beste subset van deze kenmerken te selecteren voor elk specifiek probleem. Ze behandelden het selectieproces als een toernooi, waarbij ze verschillende combinaties van kenmerken evolueerden en deze rigoureus testten. Dit werd mogelijk gemaakt door een op maat gemaakte engine die draait op grafische kaarten, waardoor ze duizenden combinaties konden testen in de tijd die het vroeger kostte om er slechts één te testen.

De resultaten waren opmerkelijk. Op de veertig benchmark-problemen presteerde de nieuwe methode nooit slechter dan de oude standaard. In achtendertig van de gevallen ontwikkelde het systeem een nieuwe regel die de vorige beste methode overtrof. Gemiddeld verbeterden de nieuwe regels de totale verzamelde beloning met 1,0 procent over alle tests, en met 1,3 procent op de problemen waar nog ruimte was voor verbetering. In tien specifieke gevallen was de verbetering statistisch significant en groot genoeg om als een belangrijke doorbraak voor dat specifieke scenario te worden beschouwd. Misschien wel het belangrijkste: de nieuwe regels bleven eenvoudig en leesbaar. Het waren geen black-box algoritmen die niemand kon begrijpen; het waren compacte wiskundige expressies die een mens kon lezen en verifiëren. In veel gevallen waren de nieuwe regels ook stabieler, waarbij ze consistente resultaten produceerden zelfs wanneer de willekeurige vertragingen varieerden, terwijl de oude regels soms wild tussen goed en slecht uitschoten.

De studie onthulde ook waarom de verbeteringen plaatsvonden. De nieuwe regels waren bijzonder effectief in situaties waarin het basissysteem moeite had om alle mogelijke klanten te bezoeken. In deze "onverzadigde" scenario's stelde de nieuwe woordenschat het systeem in staat om complexe afwegingen te maken, zoals het bezoeken van een verre, hoogwaardige klant, zelfs als dat betekende dat een nabijgelegen, laagwaardige klant overgeslagen moest worden. De onderzoekers ontdekten dat de nieuwe kenmerken het systeem hielpen bij het reguleren van zijn zoektocht, wat betekende dat het minder waarschijnlijk was dat het vastliep in een lokale valstrik en eerder een robuust pad naar voren zou vinden. De methode werkte door te leren van de structuur van hoogwaardige oplossingen zonder deze simpelweg te kopiëren. Het probeerde niet de exacte route van de expert-planner na te bootsen; in plaats daarvan leerde het de principes die die routes succesvol maakten en paste het deze toe in een nieuwe, onzekere omgeving.

Dit werk demonstreert dat het mogelijk is om de kloof te overbruggen tussen complexe, offline optimalisatie en snelle, online besluitvorming. Door de inzichten van krachtige, offline solvers te gebruiken om een betere woordenschat op te bouwen, en vervolgens de juiste instrumenten zorgvuldig te selecteren voor elke specifieke taak, hebben de onderzoekers een systeem gecreëerd dat zowel krachtig als transparant is. Het eindproduct is een set beslisregels die direct in voertuigen of drones kan worden ingebed, waardoor ze in microseconden intelligente keuzes kunnen maken zonder een verbinding met een centrale computer nodig te hebben of complexe simulaties te draaien. De aanpak suggereert een nieuwe weg voor kunstmatige intelligentie in de logistiek: een weg die waarde hecht aan interpreteerbaarheid en aanpasbaarheid, en die ervoor zorgt dat de machines die kritieke beslissingen nemen, begrepen kunnen worden door de mensen die op hen vertrouwen. De onderzoekers hebben hun code, data en de specifieke ontdekte regels publiekelijk beschikbaar gesteld, in een uitnodiging aan anderen om voort te bouwen op dit fundament voor toekomstige uitdagingen in onzekere omgevingen.