28/07/2021
Wiskundigen hebben dagelijks te maken met verschillende soorten puzzels. Het begint al op de basisschool, waar we met behulp van koekjes leren dat 1 + 1 gelijk is aan 2. Later in onze carrière helpt het verdelen van een vlaai ons bij het rekenen aan breuken. Spelenderwijs leren we steeds moeilijkere wiskundige problemen op te lossen. Heb je je ooit afgevraagd welke route die tafel uit Indonesië heeft afgelegd voordat deze een plekje in de woonkamer kreeg? Of hoe de strooiwagen zo snel de wegen vrij heeft kunnen maken zodat je in de ochtend zonder al te veel problemen naar je werk kunt? In dit artikel neem ik jullie mee naar het vakgebied Operations Research, ook wel Besliskunde genoemd. Hoe? Door even terug de collegebanken in te gaan: van de basisschool tot aan de academische toga. Waarom? Misschien heb je geen wiskundige achtergrond, toch zal je zien dat Besliskunde overal terugkomt. Zoals bij het bekende Chinese Postman Problem of het handelsreizigersprobleem. En zelfs wanneer je op vakantie bent en denkt nooit meer iets met de geleerde sommen van vroeger te doen… Deelnemen aan dit college? Lees snel verder!
Basisschool & routeplanning
‘Hoe weten we wie van jullie de kortste route heeft getekend?’ vraagt de lerares aan de kinderen in de klas. Terug naar een van de eerste momenten waar je de wiskundige wereld begon te ontdekken: de basisschool. De lerares geeft de kinderen een plattegrond, waarop twee punten zijn aangegeven. Eén punt laat de locatie van de school zien, de ander van een huis. Ze vraagt de kortste route te tekenen van huis naar school. De meesten vinden een kortste route van 650 meter. Een meisje zegt na even puzzelen een route van 630 meter te hebben gevonden. Maar is dit dan ook echt de kortste? Het was Dijkstra die hiervoor een algoritme heeft bedacht. De lerares begint met uitleggen. We starten bij het beginpunt, de school, en kijken naar de afstand tot ieder van de kruisingen. We nemen het kruispunt met het kleinste getal en kijken vanuit daar verder naar de omliggende kruispunten. Wanneer je op een kruispunt komt via meerdere routes schrijf je het kleinste getal op om daar te komen. De lerares doet het voor en vindt de oplossing in enkele minuten. Het meisje dat de route van 630 meter voorstelde, springt blij omhoog. Ze heeft de oplossing gevonden, wist jij het ook?
Het handelsreizigersprobleem
Dankzij Dijkstra kan de kortste route tussen twee punten eenvoudig worden berekend, maar wanneer het aantal locaties oploopt neemt het aantal mogelijke oplossingen exponentieel toe. ‘Het vak Operations Research is groot geworden met dit probleem’, vertelt de professor tijdens het eerste college aan de start van de academische carrière. Hij toont een dia waarop een groot aantal punten op de kaart van Nederland te zien is, met daartussen een wirwar van lijnen. Hij heeft het over het bekende handelsreizigersprobleem, beter bekend als The Travelling Salesman Problem. Wat is de kortste route die een handelsreiziger af moet leggen om een reeks steden te bezoeken om vervolgens weer terug te keren naar zijn vertrekpunt? Zo snel mogelijk, zonder punten dubbel te passeren? Tegenwoordig komt DHL het probleem tegen bij het bezorgen van post, de NS bij het ontwerpen van een dienstregeling, Sinterklaas wanneer hij zijn pakketjes op 5 December door Nederland bezorgt en jij zelf wanneer je op vakantie in Italië zo snel mogelijk alle bezienswaardigheden van je bucketlist af wilt strepen.
VB: netwerk van 4 bezienswaardigheden in Maastricht. De rode lijnen geven de snelste manier aan om alle attracties te bezoeken & weer terug te keren naar het startpunt.
Het klinkt simpel, toch ligt de complexiteit van het vinden van een oplossing mijlenver bij het vorige probleem van de basisschool vandaan. ‘Zien jullie al waarom dit zo is?’, vraagt de professor, enthousiast wijzend naar een kaart met bezienswaardigheden in Maastricht. Hij legt het uit aan de hand van een voorbeeld. Stel je wilt n bezienswaardigheden bezoeken. Hoeveel verschillende volgordes bestaan er om deze te bezichtigen? Als startpunt kun je natuurlijk een van de n bezienswaardigheden kiezen. Daarna zijn er nog n-1 over. Wanneer je doorrekent, kun je berekenen dat er in totaal n · (n-1) · (n-2) · … · 1 = n! verschillende routes zijn. Met een vijftiental bezienswaardigheden betekent dit dus al 2.40 · 1018 mogelijke oplossingen! Het doorrekenen kost zelfs de beste computer heel veel tijd. In de praktijk worden daarom benaderingsmethoden gebruikt waarmee je dichtbij de optimale oplossing komt.
The Chinese Postman Problem
Een week later is het tijd voor een nieuw college. ‘Vorige week hebben we het gehad over het handelsreizigersprobleem, waarbij je ieder van de knooppunten in een netwerk moet bezoeken’, begint de professor wanneer je een plekje in de collegezaal hebt gevonden. Maar kunnen we ook een (toeristische) route maken waarbij álle straten in Maastricht één keer worden doorlopen? Deze puzzel binnen de Besliskunde staat ook wel bekend als The Chinese Postman Problem. Waar we voorheen de snelste route probeerden te vinden om een viertal locaties te bezoeken, willen we nu ieder van de (witte) straten doorlopen. Je kunt je voorstellen dat tijdens een wandeling door de pittoreske straatjes van Maastricht het wellicht niet uitmaakt wanneer je meerdere keren langs het Vrijthof komt. Maar wat dacht je van de vuilniswagen en de sneeuwschuiver? Zij doen dit het liefste zo min mogelijk!
Award winning oplossing
Kortom: Besliskunde, Operations Research, Optimalisatie: het komt altijd overal terug. Optimalisatieproblemen als die van de handelsreiziger zijn zo moeilijk omdat we in een onvoorstelbaar grote verzameling aan mogelijkheden op zoek zijn naar de beste oplossing. Dit leidt tot onschaalbare algoritmen dat wiskundigen een NP-probleem noemen. De meeste NP-problemen zijn makkelijk op te lossen met een simpele benadering, het zal niet de perfecte route vinden voor de handelsreiziger maar komt aardig in de buurt. Hoe lastig deze vraagstukken ook zijn, soms is het is na hard werken mogelijk om toch een exacte oplossing te vinden.
In samenwerking met Bill Cook, hoogleraar combinatoriek en optimalisering aan de Universiteit van Waterloo, hebben we in ieder geval een kortste fietsroute tussen alle Rijksmonumenten in Nederland bepaald en bewezen dat de oplossing optimaal is. De moeilijkheid is dat optimaliteit niet bewezen is voor álle gevallen en dit probleem behoort dan ook nog steeds tot één van de zeven klassieke onopgeloste wiskundige raadsels. Wie ‘m oplost ontvangt zelfs een miljoen! Dus mocht je je tijdens de vakantie nog eens vervelen, een miljoen dollar is een goede motivatie. Al zou het DHL-pakketje dat snel aankomt al motivatie genoeg moeten zijn… Wij zijn in ieder geval trots op het feit dat we de grootste roadmap-afstand van het handelsreizigersprobleem in Nederland hebben opgelost! Gewoon zonder beloning ;-)
Meer weten over het oplossen van het handelsreizigersprobleem, the Chinese Postman Problem of een transportprobleem van jezelf? Neem contact met Frans. Wil je daarnaast op de hoogte blijven van het laatste nieuws van CQM, volg ons op LinkedIn of meld je aan voor onze digitale nieuwsbrief!
Fotocredits: Pixabay en Veronique de Jong.
