Hoe bezoek je achtereenvolgens een groot aantal verschillende locaties met zo min mogelijk kilometers? Dit lijkt een simpele vraag, maar is eigenlijk een van de moeilijkste wiskundige problemen en bekend als het Travelling Salesman Problem (Handelsreizigersprobleem). Toch lukt het CQM om – samen met professor Bill Cook en professor Keld Helsgaun – het grootste handelsreizigersprobleem op een landkaart óóit op te lossen en voor een route langs alle 57.912 locaties met rijksmonumenten in Nederland de kortste fietsroute te bepalen. De mogelijkheden voor vergelijkbare vraagstukken zijn eindeloos,
Het Travelling Salesman Problem kan als volgt worden geformuleerd: vind de kortste route die precies één keer langs iedere locatie komt en eindigt bij het eerste locatie. Je zou natuurlijk alle mogelijke routes kunnen uitrekenen en die dan met elkaar vergelijken. Maar om op deze manier de optimale route vinden zou een computer bij slechts 22 locaties al minstens 1000 jaar rekentijd kosten, zo meldde de Washington Post in 2018.
Kroegentocht
Bill Cook, die zelf in 2016 de kortste kroegentocht door Engeland uitrekende, gebruikte 320 computerprocessoren in 10 serverclusters, voor bij elkaar opgeteld 90 jaar aan rekentijd. En jawel hoor, de kortste fietsroute – oftewel de optimale afstand – werd bewezen: het is 20.253.062 meter fietsen om alle Rijksmonumenten in Nederland te bezoeken. En hiermee is het grootste wiskundige probleem van deze soort (op een echte routekaart) óóit opgelost!
Route-optimalisatie
Hoe sportief liefhebbers van Nederlandse monumenten ook zijn, er zal waarschijnlijk niemand meer dan 20 duizend kilometer gaan fietsen om de hele route af te leggen, ook al is het dus gegarandeerd de kortste. Het gaat in dit geval dan ook niet om de praktische toepasbaarheid maar om het bewijs dat het Travelling Salesmen Problem (TSP) met meer dan 25 objecten rekenkundig niet onmogelijk is.
Frans de Ruiter: “Het is CQM, samen met Bill Cook en Keld Helsgaun gelukt om het grootste handelsreizigersprobleem op een landkaart óóit (met bijna 60.000 objecten) op te lossen. Deze doorbraak betekent veel voor de mogelijkheden in route-optimalisatie voor de zakelijke markt. Denk bijvoorbeeld aan de planning van (beroeps)vervoer, zoals taxiritten, en intermodale transporten.”
Ook interessant: Barcelona stelt met app voetgangers in de schaduw
Geselecteerd voor jou!
Innovation Origins is het Europese platform voor innovatienieuws. Naast de vele berichten van onze eigen redactie in 15 Europese landen, selecteren wij voor jou de belangrijkste persberichten van betrouwbare bronnen. Zo blijf je op de hoogte van alles wat er gebeurt in de wereld van innovatie. Ben jij of ken jij een organisatie die niet in onze lijst met geselecteerde bronnen mag ontbreken? Meld je dan bij onze redactie.