Dit jaar wil Sinterklaas het slimmer aanpakken. Daarom bezoekt Sinterklaas in de serie Sinteressant onderzoekers van de Universiteit Twente. Voor zijn routeprobleem klopt hij aan bij Clara Stegehuis, universitair hoofddocent toegepaste wiskunde.
Een herkenbaar wiskundig probleem
Wanneer Sinterklaas vertelt hoe hij vorig jaar door het land trok, hoeft Clara niet lang na te denken: "Sinterklaas, alfabetische volgorde is misschien overzichtelijk, maar dat is toch helemaal niet efficiënt? Zo reist u steeds heen en weer terwijl dat niet hoeft."
Ze legt uit dat zijn uitdaging sterk lijkt op het handelsreizigersprobleem, vaak TSP genoemd, een afkorting van de Engelse benaming traveling salesman problem. Dit is een bekend vraagstuk in de wiskunde waarin je probeert de kortste route te vinden die langs een reeks steden loopt.
"Stel dat u twintig steden wilt bezoeken", begint Clara met haar uitleg. "Omdat u altijd vanaf hetzelfde punt vertrekt, de stoomboot, ligt het beginpunt al vast. Voor de overige negentien steden kun je alle mogelijke volgordes doorrekenen: negentien keer achttien keer zeventien… helemaal tot één. Dat noemen we negentien faculteit. En dat zijn er ongelófelijk veel. Om precies te zijn 121.645.100.408.832.000 – dus meer dan 120 biljard mogelijke routes."
Waarom slimmer rekenen nodig is
Maar volgens Clara hoeven we gelukkig niet alle mogelijkheden door te rekenen, want daar is een slimmere methode voor: Branch and Bound. Deze aanpak werkt eigenlijk als slim vooruitkijken. Je schat steeds in wat een route minimaal zal kosten. Zie je dat een route sowieso langer wordt dan een route die je al hebt gevonden? Dan laat je die optie je meteen vallen en ga je door met een route die wél kans maakt de kortste te zijn.
Clara schetst de situatie als een soort grote boomstructuur. "In de wiskunde noemen we dat een beslisboom," legt ze uit. “Elke keer dat u een nieuwe stad kiest, ontstaat er een tak," legt ze uit. "Maar in plaats van al die takken helemaal uit te rekenen, bepalen we eerst een ondergrens. Als die al slechter is dan een route die we eerder hebben gevonden, dan snijden we die tak af. Dan hoeven we hem niet verder uit te werken.
Om het tastbaar te maken geeft Clara een voorbeeld: "Stel dat u vanaf de stoomboot drie steden moet bezoeken: Enschede, Amsterdam en Maastricht. Dan heeft u drie mogelijke takken. Volgen we eerst de tak naar Enschede, dan blijven Amsterdam en Maastricht over. Voor elke tak berekenen we een minimale afstand. Als die al te lang is, dan stoppen we meteen."
"Dus Rekenpiet hoeft niet alles uit te rekenen?" vraagt Sinterklaas opgelucht. "Precies," zegt Clara. "We rekenen alleen de routes door die nog kans maken om de beste te zijn."
Veel sneller klaar met bezorgen
Met deze slimme manier van rekenen kan Sinterklaas zijn route aanzienlijk verkorten. En als hij in grote steden een paar Pieten uitstuurt naar omliggende dorpen, hoeft hij zelf niet meer overal langs. "Als u het zo aanpakt," vervolgt Clara, "dan komt u dit jaar vast niet meer in de knel met de tijd."
Technologie die dichterbij komt dan je denkt
Clara’s uitleg laat zien hoe toegepaste wiskunde kan helpen om slimme keuzes te maken in complexe situaties. Dat geldt in de logistiek, maar net zo goed in een verhaal over pakjes en pieten. Theorie wordt pas interessant wanneer je ziet hoe praktisch het kan zijn. Handig voor Sinterklaas – en misschien ook voor pakketdiensten die elk jaar met dezelfde decemberdrukte worstelen.
Bekijk de video waarin Clara en Sinterklaas samen ontdekken hoe slimme wiskunde helpt om op tijd alle pakjes bezorgd te krijgen.
