Plannen 2.0: OptaPlanner

/ Blog / Plannen 2.0: OptaPlanner
Plannen 2.0: OptaPlanner

Bas Rutten

 

Wat is het?

OptaPlanner (www.optaplanner.org) is een “constraint satisfaction solver”, ofwel een optimalisatie-engine, die uitkomst kan bieden bij het oplossen van complexe planningsproblemen, waarbij er vaak ontelbaar veel mogelijke oplossingen zijn. Het oplossen van zulke problemen met “brute force” (één voor één alle mogelijkheden uitproberen) kan soms letterlijk jaren duren maar OptaPlanner gebruikt slimme algoritmes in combinatie met een business rule engine om binnen een veel kortere tijd tot een oplossing te komen.

Voor wie is het?

Voor elke organisatie met of zonder een specifieke planningsafdeling die te maken heeft met de uitdaging van het zo efficiënt mogelijk inzetten van een beperkte set aan resources (bijv personen, lokalen, voertuigen). Bekende voorbeelden hiervan zijn het inplannen van examens, het maken van roosters voor verplegend personeel of het berekenen van efficiënte routes voor vracht- of personenvervoer. De kans is dus groot dat u binnen uw organisatie met een dergelijk probleem te maken heeft.

Waarom OptaPlanner (en niet iets anders?)

Voor veel van deze problemen bestaan uiteraard reeds oplossingen, maar de aanschaf en het gebruik daarvan zijn vaak erg kostbaar. Daarnaast is het mogelijk om zelf een oplossing te implementeren maar dit kan erg complexe code opleveren en vraagt een behoorlijke wiskundige kennis. De oplossing “OptaPlanner” kan in veel gevallen een alternatief bieden: het is namelijk 100% Open Source en is daarnaast te integreren in iedere bestaande (Java) omgeving, waarbij indien gewenst bestaande code (bijv. het domeinmodel) hergebruikt kan worden. Merk wel op dat OptaPlanner geen volledig kant-en-klaar product is, maar een flexibele engine waarin u zelf uw planningsprobleem kunt modelleren – een ruime voorraad aan meegeleverde voorbeelden kan u daarbij op weg helpen.

Hoe werkt het?

Het realiseren van een oplossing in OptaPlanner bestaat grofweg uit drie stappen:

  • Het modelleren van het domein – dit bestaat uit het vaststellen van wat u in wilt plannen (de zogenaamde planning entities), de overige gegevens die van invloed zijn (de planning facts) en de attributen die u wilt variëren (de planning variables). In het voorbeeld van de examenplanning zijn de examens de planning entities, de overige zaken zoals lokalen en beschikbare surveillanten de planning facts, en de tijd en locatie van ieder examen de planning variables.
  • Het vastleggen van de regels waaraan voldaan moet worden. OptaPlanner onderscheidt hierbij harde regels die nooit verbroken mogen worden (bijv. een examen mag niet gepland worden in een lokaal dat niet voldoende capaciteit biedt) en zachte regels (regels die wel gebroken mogen worden, maar het liefst zo min mogelijk). Zachte regels kunnen bijv. gebruikt worden om examens gelijkmatig te spreiden over de dagen of om lokalen optimaal te gebruiken. De regels kunnen geïmplementeerd worden in Java, maar het is vaak veel eenvoudiger om deze vast te leggen als regels voor de Jboss Drools rules engine die door OptaPlanner gebruikt wordt.
  • De configuratie van de planner. Hierbij kunt u vastleggen hoe lang OptaPlanner moet rekenen (bijv. tot een bepaalde score bereikt is, totdat de oplossing gedurende een bepaalde tijd niet meer verandert of gewoon gedurende een bepaalde tijd) en welke heuristieken (slimme algoritmes) gebruikt moeten worden.

OptaPlanner gaat vervolgens aan de hand van het bovenstaande op zoek naar een goede oplossing. OptaPlanner probeert hierbij telkens nieuwe stappen uit, berekent voor elke stap de bijbehorende score aan de hand van de regels en kiest vervolgens op basis van de slimme algoritmes een stap die de planner dichter bij de gewenste oplossing brengt.

Speciale wiskundige kennis is niet nodig om een oplossing te implementeren (al is het natuurlijk altijd leuk om te kunnen zeggen dat je weet wat Simulated Annealing en Tabu Search inhouden) – kennis van Java en enige affiniteit met Jboss Drools en de bijbehorende rules language is voldoende.

En verder…

OptaPlanner wordt vaak gebruikt om a priori planning uit te voeren, d.w.z. de oplossing wordt enige tijd van tevoren (bijvoorbeeld in de nacht voordat deze nodig is) berekend. Het is echter ook mogelijk om OptaPlanner in “real time modus” te draaien, waarbij de plannings-engine continu draait en er op ieder moment planningsentiteiten en feiten toegevoegd en aangepast kunnen worden.

Daarnaast beschikt OptaPlanner over een eenvoudig te gebruiken benchmark-applicatie die gebruikt kan worden om verschillende regelsets en algoritmes los te laten op een probleem om zo te meten en inzichtelijk te maken welke aanpak voor dat specifieke probleem het beste werkt.

Conclusie

Veel bedrijven hebben te maken met (complexe) planningsproblemen – hiervoor helemaal zelf een oplossing implementeren is vaak te complex en bestaande pakketten kunnen duur, niet flexibel genoeg of lastig te integreren zijn. OptaPlanner is eenvoudig te integreren in je bestaande (Java) landschap, flexibel genoeg om voor ieder planningsprobleem ingezet te kunnen worden en volledig Open Source waardoor het in veel gevallen uitkomst biedt.

Bas Rutten is Senior Java Consultant met ruim 12 jaar ervaring en is vertrouwd met OptaPlanner.

 

 

×