26/07/2021
Doorbraak: CQM doet het ‘onmogelijke’
Route-optimalisatie voor allergrootste handelsreizigersprobleem ooit
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. Naast de ultieme fietsvakantie ook een wereldprimeur op het gebied van optimalisatie. De mogelijkheden voor vergelijkbare vraagstukken zijn eindeloos!
Handelsreizigersprobleem
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. Dat kan slimmer!
Frans vertelt over de uitdaging van CQM:
“In Nederland zijn 57.912 unieke locaties met Rijksmonumenten. Om te kunnen kiezen tussen alle mogelijke routes heb je om te beginnen de afstanden tussen alle locaties nodig. Dat zijn er voor dit probleem meer dan een miljard. Wanneer je al deze afstanden van tevoren hebt, maakt dit het een stuk eenvoudiger om een algoritme te ontwikkelen om de oplossing te vinden. Volgens de rest van de wereld is dit een lastige opgave. Maar CQM bewijst met een state-of-the-art algoritme dat voor ons niets onmogelijk is, en dat in zeer korte rekentijd op een standaard server.”
CQMaps
CQM heeft een eigen routeplanningservice voor het zeer snel uitrekenen van onderlinge afstanden tussen grote verzamelingen adressen. CQMaps maakt automatische routeplanning mogelijk en wordt door CQM – op maat – aangeboden aan beroepsvervoerders met veel (intermodale) transportbewegingen naar een grote hoeveelheid locaties. Partnerorganisatie Geodan, leverancier van slimme kaarten, leverde voor deze uitdaging het fietskaartmateriaal. En met de ingenieuze optimalisatiesoftware van CQM lukte het om in twee uur tijd de 1.8 miljard afstanden tussen alle Rijksmonumenten in Nederland te berekenen.
Met deze informatie is Bill Cook, die zelf in 2016 de kortste kroegentocht door Engeland uitrekende, de volgende uitdaging aangegaan. Het vinden van de kortste route is al een lastige opgave, maar wiskundig bewijzen dat het inderdaad de aller kortste is, is ook een hele klus. Hij 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!
Klik op de afbeelding om naar de interactieve routekaart te gaan.
Route-optimalisatie en vergelijkbare vraagstukken
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.
Een trotse Frans:
“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. En 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.”
Route beschikbaar in GPX-file
Voor de échte fietsliefhebber hebben we overigens een GPX-file gemaakt van de - gegarandeerd kortste - fietsroute langs alle 57.912 locaties met Rijksmonumenten in Nederland. De route start en finisht bij onze buren: de Steentjeskerk in Eindhoven. Je bent dus van harte welkom voor een kop koffie bij CQM! ;-)
Als je even een berichtje stuurt, ontvang je een link naar de gratis GPX-file.
Heb je vragen of wil je meer weten over de mogelijkheden van route-optimalisatie voor jouw organisatie, neem dan even contact op met Frans. Hij kan je – gegarandeerd – verder helpen! Klik hier om nog meer te lezen over The Travelling Salesman Problem.
In het nieuws
Wat leuk, meerdere media in Nederland hebben verslag gedaan van deze doorbraak:
- Het kost tijd, maar er is een snelste fietsroute langs alle 57.912 monumenten in Nederland - Innovation Origins (14/7)
- It takes time, but the fastest cycling route past all 57,912 national monuments in the Netherlands exists - Innovation Origins (14/7)
- Hoe LDV’ers kunnen profiteren van oplossing handelsreizigersprobleem - Logistiek.nl (27/7)
- De kortste route van A naar B via heel veel tussenstops vind je in Brabant - Innovations Origins (3/8)
- 20.000 kilometer fietsen en je hebt ieder monument gezien - NRC (10/9)
- 20.000 kilometer fietsen en je hebt ieder monument gezien - NRC pdf-versie (10/9)
(Credits tekening: Kamagurka - NRC)
- Cycling to 57,912 National Monuments in the Netherlands - The Network Pages (1/10)
Wil je op de hoogte blijven van het laatste nieuws van CQM, volg ons op LinkedIn of meld je aan voor onze digitale nieuwsbrief.
