Genetisch algoritme voor roosteroptimalisatie: waarom we C gebruiken

Stel je hebt 200 open diensten en 80 medewerkers. Elke medewerker heeft een beschikbaarheid, een set skills, een woonplaats en collega's die hij of zij liever wel of niet naast zich ziet. Jij wilt dat zo veel mogelijk diensten bezet zijn, met de best mogelijke match op elk van die factoren.

Dit is een combinatorisch optimalisatieprobleem. Het exacte optimum vinden kost exponentieel veel tijd. In de praktijk wil je een goed genoeg resultaat in minder dan tien seconden. Wij hebben dat opgelost met een genetisch algoritme — en de kern daarvan staat in C.

Waarom niet gewoon Python?

We hadden al een greedy solver in Python. Die werkt snel en is goed genoeg voor kleine roosters: sorteer diensten op prioriteit, pak de best beschikbare medewerker, ga door. Probleem: bij grotere roosters of wanneer de kwaliteit echt telt, laat de greedy solver kansen liggen.

Een genetisch algoritme zoekt breder. Het werkt met een populatie van oplossingen — zeg 150 mogelijke roosters tegelijk — en laat die over generaties heen evolueren via crossover en mutatie. Elke generatie overleeft de beste set oplossingen. Na honderd generaties heb je iets dat significant beter scoort dan een greedy toewijzing.

In Python bleek dit te langzaam. Een generatie over een populatie van 150 itereren met scoring voor honderden shift-employee combinaties kostte tientallen milliseconden per generatie. 100 generaties × 50ms = 5 seconden alleen voor scoring, dan nog het eigenlijke algoritme. Onacceptabel voor een interactief product.

De oplossing: de kern schrijven in C.

De architectuur van de C solver

We hebben het algoritme opgebouwd uit 13 modules, elk met één verantwoordelijkheid:

src/c_solver/src/
  generetic.c        # Publieke API, orchestratie, lifecycle
  genetic_core.c     # Evolutielus, crossover, mutatie
  population.c       # Populatiegeneratie, toernooistandaard selectie
  scoringfactor.c    # Scorefactoren (5 modes)
  input_loader.c     # Geheugentoewijzing, invoernormalisatie
  postcodes.c        # Nederlandse postcodedistanties
  commute.c          # Reisafstandopzoekingen
  timeblocks.c       # 96-blokken-per-dag beschikbaarheid (uint128_t)
  constraints.c      # Uitvoerbaarheidscontroles
  analytics.c        # Per-generatie telemetrie
  error_handler.c    # Foutcodes en meldingen
  mutation_config.c  # Mutatiekansen

We begonnen met een monolithisch generetic.c van 1.200 regels. Dat werkte, maar was niet testbaar. Door het op te splitsen konden we elke module afzonderlijk testen met het Criterion framework — 33 unit tests, die we draaien in vier buildconfiguraties (debug, asan, ubsan, release).

Hoe het algoritme werkt

Het genetisch algoritme in de kern is klassiek, maar met een paar bewuste keuzes:

Populatie-initialisatie: We genereren een willekeurige startselectie van roosters. Elk rooster is een array van (dienst_id, medewerker_id) paren. Onuitvoerbare toewijzingen (medewerker niet beschikbaar, verkeerde skill) worden tijdens generatie al gefilterd.

Scorefactoren: Elke toewijzing krijgt een score op basis van vijf factoren, elk met een configureerbaar gewicht:

| Factor | Wat het meet | | --------------- | ---------------------------------------------------- | | COVERAGE | Hoeveel diensten zijn ingevuld (altijd actief) | | FRIENDSHIP | Medewerkers die graag samenwerken (bitpacked matrix) | | COMMUTE | Reisafstand op basis van Nederlandse postcode | | AGE | Leeftijdsvoorkeur per dienst of locatie | | DAYS_REGISTERED | Anciënniteit als tiebreaker |

Beschikbaarheid als 128-bit integer: Een dag is opgedeeld in 96 blokken van 15 minuten. De beschikbaarheid van een medewerker is een uint128_t. Controleren of een dienst past is één bitwise AND-operatie. Dit maakt het mogelijk om duizenden checks per generatie te doen zonder meetbare overhead.

Selectie en crossover: We gebruiken toernooiselectie — pak willekeurig twee kandidaten uit de populatie, neem de beste. Dat voorkomt dat het algoritme te snel convergeert naar een lokaal optimum. Crossover is two-point: neem twee "ouder"-roosters, snij ze op twee punten en recombineer.

Elitisme: De beste N% van een generatie overleeft altijd naar de volgende. Zo verlies je nooit een goede oplossing door pech in de selectie.

Configureerbare parameters

Alle parameters zijn runtime-configureerbaar:

{
  "population_size": 150,    # Aantal parallelle oplossingen (10–500)
  "max_generations": 100,    # Evolutielussen (10–1000)
  "mutation_rate": 0.05,     # Kans op willekeurige wijziging (0–1)
  "elitism_count": 10        # Top-N die altijd overleeft
}

In productie draaien we standaard 150 × 100. Dat levert een kwalitatief goed rooster op in 2–6 seconden, afhankelijk van het aantal diensten en medewerkers.

Release build vs. debug build

De release build is 440KB en geoptimaliseerd met -O2. De debug build is 3,6MB en bevat symbolen voor inspectie. We bouwen alle vier configuraties naast elkaar:

build/
  debug/lib/libgeneretic.so     # 3.6 MB — symbolen, geen optimalisaties
  asan/lib/libgeneretic.so      # 3.7 MB — AddressSanitizer
  ubsan/lib/libgeneretic.so     # 3.9 MB — UndefinedBehaviorSanitizer
  release/lib/libgeneretic.so   # 440 KB — productie

Tijdens CI draaien we de tests altijd in asan en ubsan. We hebben er vier memory leaks mee gevonden die in de release build nooit zichtbaar waren geweest.

Wat de solver teruggeeft

De output is bewust minimaal:

{
  "shift_assignments": [
    { "shift_id": "shift_001", "employee_id": "emp_042" },
    { "shift_id": "shift_002", "employee_id": "emp_017" }
  ],
  "solution_metrics": {
    "coverage_percentage": 94.5,
    "unassigned_shifts": 3,
    "solve_time_ms": 2840
  },
  "feasible": true
}

De Python-laag bovenop vertaalt dit naar het formaat dat de monolith verwacht. De C solver weet niets van Redis of BullMQ — hij krijgt een struct in, en geeft een struct terug.

Wat het oplevert

Ten opzichte van de greedy solver zien we in productie gemiddeld 12–18% hogere dekking op secundaire factoren (friendship, commute) bij vergelijkbare of betere primaire dekking (coverage). Dat klinkt abstract, maar concreet: medewerkers werken vaker met collega's die ze kennen, reizen korter, en roosters kloppen vaker in één keer zonder handmatige aanpassingen.

De greedy solver staat er nog steeds als fallback. Als de C solver crasht of een onverwachte input krijgt, valt het systeem automatisch terug op Python. Dat is een bewuste keuze: een iets minder optimaal rooster is beter dan een foutmelding voor de eindgebruiker.