Bij Bessy draait alles om het efficiënt inplannen van afspraken bij klanten thuis. Het is voor ons van groot belang dat de inzet van buitenwerkers steeds slimmer en effectiever wordt. Daarbij houden we niet alleen rekening met wie waarheen gaat, maar ook met reistijden, beschikbare werkuren en de prioriteiten van jullie, onze gebruikers.
Dit type probleem staat in de wiskunde bekend als het Vehicle Routing Problem with Time Windows (VRPTW). Het is een klassiek optimalisatieprobleem dat snel complex wordt naarmate er meer medewerkers en klanten bijkomen. AI biedt hier uitkomst. Met moderne technieken zoals metaheuristics en reinforcement learning kunnen we slimme strategieën ontwikkelen om optimale én snelle routes te vinden, zodat we niet handmatig alle mogelijke combinaties hoeven uit te proberen. Zo kunnen we tijd besparen, kosten verlagen en de planning van onze buitenwerkers flexibeler en efficiënter maken.
Om de best mogelijke routes te genereren, maken we gebruik van verschillende technieken en onderzoeken we continu nieuwe mogelijkheden om onze planning verder te verbeteren. Hieronder geven we een korte samenvatting van de AI-technieken die we momenteel reeds gebruiken en technieken die we op korte termijn gaan implementeren als benchmark, zodat jullie een beter beeld krijgen van ons proces. De AI-modellen die voor ons van belang zijn, zijn te verdelen in metaheuristics en machine learning gebaseerde modellen.
Om te begrijpen wat metaheuristics zijn, moeten we een duidelijk beeld hebben van wat ‘heuristics’ zijn. Heuristieken proberen een zo goed mogelijke oplossing te benaderen, zonder de exacte oplossing per definitie te vinden. Zoals je je kunt inbeelden, met meerdere buitenwerkers en meerdere klanten die bezocht moeten worden, is het aantal mogelijke opties heel groot! In de wiskunde wordt dit de ‘search space’ genoemd, en als die search space groot is, wil je een algoritme hebben dat een zo optimaal mogelijke benadering zoekt, maar op een gegeven moment ook wel stopt, en niet doorgaat totdat het alle mogelijke opties bekeken heeft.
Metaheuristics gebruiken heuristische technieken en voegen daar een extra laag sturing en algemene strategie aan toe. Heuristics versimpelen de zaak namelijk nogal; een heuristiek kan bijvoorbeeld zijn: voeg de dichtstbijzijnde node (klant) als volgende visite aan mijn route toe. Maar dit leidt zelden tot de beste oplossing als je rekening moet houden met de totale reistijd, andere beschikbare dagen, buitenwerkers die reeds onderweg zijn, enzovoort. Metaheuristics zorgen voor een betere balans tussen ‘exploratie’ en ‘exploitatie’ en voorkomen er daardoor voor dat je bij de eerste de beste ‘gunstige’ oplossing blijft steken.
Machine learning wordt gebruikt om patronen te leren uit data en om voorspellingen te doen op basis van nieuwe data. Grofweg kun je veel machine learning algoritmes scharen in deze twee categorieën:
● Modellen gebaseerd op het fitten van functies op trainingsdata, bijvoorbeeld met beslissingsbomen of lineaire algebra. Neurale netwerken zijn in essentie ook linaire algebra - een hoop lineaire verbanden tussen nodes (zogenaamde ‘neuronen’) in verschillende lagen in het netwerk, die niet-lineair worden gemaakt met activatiefuncties om complexere problemen te tackelen. Bij al deze technieken worden soms verschillende modellen gecombineerd om samen tot een potentere beslisser te komen of te komen tot een beslisser die kan worden ingezet voor verschillende doeleinden.
● Modellen gebaseerd op het genereren van eigen trainingsdata via (al dan niet gestuurde) trial-and-error in een gesimuleerde omgeving. Hierover dadelijk meer!
Het doel is dus fundamenteel anders dan bij metaheuristics; je probeert bij metaheuristics niet een ‘patroon’ te leren, je beschrijft gewoon een zoekstrategie die stap voor stap oplossingen verbetert totdat je een bijna optimale oplossing hebt, terwijl je bij machine learning een model bouwt dat de wiskundige verbanden die er bestaan tussen datapunten beschrijft. Maar beiden worden onder de overkoepelende term ‘AI’ geschaard! Maar hoe zetten wij metaheuristics en machine learning in om goede routes te berekenen?
Bij classical metaheuristics gaan we uit van een bestaande route, waarin we nodes gaan uitwisselen om dichter bij het globale minimum te komen. Zoals eerder gezegd, heuristieken zijn vaak te simpel: van de gehele ‘search space’ belanden ze vaak in een ‘lokaal minimum’: een oplossing die als eerste opzetje dient, maar vaak verre van ideaal is. Ons doel is om dichter bij het ‘globale minimum’ komen, en metaheuristicstechnieken zoals local guided search en tabu search voegen technieken toe die de heuristiek helpen om meer te exploreren en niet alleen te exploiteren. Tabu search bijvoorbeeld houdt een lijst bij van recente oplossingen of bewegingen die ‘tabu’ zijn, om te voorkomen dat het algoritme terugvalt op net bezochte (slechte of reeds uitgeprobeerde) oplossingen, terwijl local guided search een ‘penalty’ geeft (doet alsof de afstand groter is dan hij in werkelijkheid is) aan veel voorkomende stukjes route of nodes die de totale reistijd vaak vergroten, zodat het algoritme alternatieven gaat verkennen.
Hierbij kun je onder andere denken aan genetic algorithms. Dit is een groep algoritmes geïnspireerd door het concept van evolutie. In de basis, initialiseer je een aantal routes en voert daarover een crossover-operatie op uit: je maakt combinaties van twee routes in een zogenaamd ‘kind’. Die crossover-operatie kan bijvoorbeeld over een deel van de route zijn, of over de volgorde. Een voorbeeld: je hebt route 1 voor buitenwerker X die gaat van A > B >C > D > E > A, en route 2 die gaat van A > C > B > E > D > A. Hun ‘kinderen’ (het crossover-product) kunnen elk onderdelen van de route krijgen - uiteraard rekening houdend met het feit dat wel alle nodes bezocht moeten worden! Een mogelijk kind kan dus route A > B > C >E > D > A krijgen (B > C van route 1, en E > D van route 2). Hiermee zorg je ervoor dat de routes stap voor stap ‘evolueren’, ofwel veranderen met de tijd. Daarnaast is er nog een concept dat voor ‘evolutie’ zorgt: mutaties. Door die mutaties kan een ‘kind’ zelf bijvoorbeeld bepaalde stukjes van een route omwisselen. Hoe goed een route is, en daarmee hoeveel kans een ‘kind’ heeft om zelf een crossover-operatie te mogen uitvoeren, kun je zelf bepalen in je programmering d.m.v. een zogenoemde ‘fitness functie’, en die is in dit geval een zo kort mogelijke reistijd. Zo krijg je uiteindelijk meer buitenwerker / dag combinaties in je populatie die naar een kortere route gaan, en vanuit daar weer verder kunnen evolueren, totdat je populatie voornamelijk bestaatuit individuen met zo optimaal mogelijke routes.
Reinforcement learning valt onder de machine learning categorie, en is een techniek waarbij je werkt met agents, states, actions en een reward. De agents zijn in ons geval de buitenwerkers, die verschillende ‘states’ kunnen hebben (ze zijn op een bepaalde locatie), actions kunnen doen (ze kunnen naar locatie ‘X’ gaan, of naar locatie ‘Y’ gaan, of gewoon nog een tijdje werkzaam zijn op de huidige locatie), en een reward krijgen aan het einde van hun route (een ‘negatieve’ reistijd). In plaats van het creëren van hele routes die muteren, zoals in genetic algorithms, zijn routepunten (ofwel, nodes) hier gedefinieerd als verschillende ‘states’ en de actie om naar die node te gaan, heeft een reward (de zo kort mogelijke reistijd). Door simulaties uit te voeren, leert de agent een zogenaamde ‘policy’, die aangeeft welke ‘actie’ je in welke ‘state’ moet nemen om de cumulatieve (totale) reward te maximaliseren. En daarmee leert hij dus stap voor stap hoe hij een steeds kortere route kan nemen! Dit was een kort stukje over het bouwen van routes, maar uiteraard komt AI op veel andere plekken van pas in Bessy, zoals in het ‘voorwarmen’ van route-gebruiker combinaties, waardoor het leerproces sneller gaat, een naselectie doen op basis van de hoeveelheid taken die gemiddeld gezien door een bedrijf in een bepaald regio uitgevoerd worden (dit is as we speak in ontwikkeling!) en zelfs voor het leren van de fouten die ons route-algoritme zelf maakt!
We hebben nog veel ideeën om Planbot zo slim mogelijk, maar óók zo snél mogelijk te maken, dus stay tuned!
