De optimale planning in een oogwenk

In de reeks Data Stories zetten we verschillende Data Scientists van Capgemini Insights & Data in de spotlight om te vertellen over de toffe dataprojecten waar zij aan werken. In deze editie geven we je een kijkje in de werkzaamheden van Hans Kattouw.

Waar hou jij je dagelijks mee bezig?

“Ik hou me dagelijks mee bezig met Linear Programming bij ProRail en Defensie. Linear programming is een methode om een optimalisatieprobleem als een wiskundig model op te stellen en daar een zo goed mogelijke oplossing voor te vinden. Zo’n model bestaat vaak uit een (lineaire) doelfunctie die gemaximaliseerd (of geminimaliseerd) moet worden, waarbij dan ook moet worden voldaan aan een verzameling van lineaire constraints. Een voorbeeld hiervan is het knapzakprobleem, waarbij je een aantal voorwerpen mag kiezen om mee te nemen. Deze voorwerpen hebben een waarde en een gewicht. In dit geval wil je dan de waarde van de voorwerpen die je meeneemt maximaliseren, waarbij je als constraint bijvoorbeeld kan hebben dat je niet meer dan 20 kilo mee mag nemen. Een ander bekend optimalisatieprobleem is het handelsreizigersprobleem waarbij het doel is om, gegeven een aantal steden, de kortste weg te vinden die een keer langs iedere stad komt en eindigt bij de eerste stad.”

Dat klinkt interessant! Hoe maken klanten daar gebruik van?

ProRail: “Bij ProRail hebben we een planningstool gemaakt voor incidentbestrijders. Dit zijn mensen die moeten reageren op incidenten bij het spoor zoals bijvoorbeeld een storing, spoorlopers of aanrijdingen. Natuurlijk zitten deze mensen niet alleen maar te wachten tot er iets gebeurt. Ze doen ook preventieve taken, zoals surveillances langs het spoor. De taken van deze medewerkers moeten op zo’n manier worden ingepland dat je verwachte responsetijd laag blijft in het geval van een incident. Zo wil je bijvoorbeeld niet dat alle medewerkers in het zuiden zijn en dat er in het noorden een incident gebeurd, omdat het dan te lang duurt voordat je op de plaats van het incident bent.”

“Het Linear Programming model dat we voor dit probleem gemaakt hebben is behoorlijk complex. Er moeten variabelen worden aangemaakt die bijhouden op welke locatie iemand is en op welk tijdstip, of zij zich op een tijdstip tussen twee bepaalde locaties hebben bewogen en of ze aan een bepaalde taak zijn begonnen. Voor een dagplanning met 10 medewerkers en 15 mogelijke taken hebben we zo’n 18.000 variabelen en 47.000 constraints in ons model. Met behulp van een krachtige Linear Programming Solver zijn we in staat om in enkele minuten toch een goede planning te maken!”

Defensie: “Bij de luchtmacht maken we ook gebruik van linear programming. Er is hier een Data Science team opgericht om te helpen bij het over gaan naar de 5^de generatie van de luchtmacht. Bij deze transitie hoort onder andere het vervangen van F16’s door F35’s en het steeds meer gebruik maken van data.”

“Ook hier maken we een planningstool, niet voor een dagelijkse planning, maar om op jaarbasis de vluchten en onderhoud van vliegtuigen in te plannen. Voorheen waren mensen hier weken mee bezig en dit kan nu binnen enkele minuten.

Wat vind je zelf de grootste uitdaging bij linear programming?

“Omgaan met hoge rekentijden is altijd een grote uitdaging. Bij complexe modellen kun je hier al snel mee te maken krijgen. Dit kan deels opgevangen worden door gebruik te maken van krachtige (commerciële) Linear Programming solvers, maar ook daar zitten grenzen aan. Een groot deel van de werkzaamheden bestaat dan ook uit het kleiner/simpeler maken van het model. Bij ProRail doen we dit onder andere door niet alle locaties in het netwerk mee te geven, maar eerst het netwerk te versimpelen met een greedy covering waar alle belangrijke locaties in ieder geval in zitten. Ook kan het nuttig zijn om een probleem op te delen in deelproblemen en die apart op te lossen. Dit soort methodes zorgen vaak voor een flinke verbetering in de rekentijd. Vaak heeft het echter ook tot gevolg dat de gevonden oplossingen minder goed worden. Dit is een trade-off die je soms moet maken. Dit hangt ook af van de wensen van de klant. Als het een uur duurt om een jaarplanning te maken kan dat bijvoorbeeld wel acceptabelel zijn, maar bij dagplanningen die elke dag gemaakt moeten worden niet.”

Zijn er nog andere use cases waar linear programming gebruikt kan worden?

“Jazeker! Je kunt denken aan onderhoudsplanningen, supply chain management, task scheduling, maar ook bijvoorbeeld aan portfolio management of riskmanagement in finance. Eigenlijk alles waarbij je iets wilt optimaliseren en lineaire constraints hebt. Laatst moest ik een keer een aantal mensen verdelen in groepjes, waarbij het doel was om mensen bij elkaar in te delen die elkaar nog niet goed kenden. Hier heb ik toen een Linear Program model voor gemaakt die de beste indeling kon vinden.”