Er bestaat een lijst van beroemde wiskundige problemen. Eén daarvan is het Travelling Salesman Problem. Op dit wiskundige vraagstuk wist CQM in samenwerking met professoren William Cook en Keld Heisgaun een antwoord te vinden. Het feit dat een bedrijf uit Eindhoven meewerkte aan deze doorbraak was voor Innovation Origins reden om Arjen Vestjens (managing partner, links) en Peter Hulsen (partner) van CQM hier nog eens uitgebreid over te spreken.
Arjen Vestjens, managing partner bij CQM. 
Peter Hulsen, partner bij CQM.
Travelling Salesman Problem
Arjen, kun je ons allereerst nog een keer uitleggen wat het Travelling Salesman Problem precies inhoudt?
“Bij het handelsreizigersprobleem wil je de kortste route tussen een willekeurig aantal locaties berekenen, waarbij je weer uitkomt bij het beginpunt. In eerste instantie klinkt dat wellicht niet heel ingewikkeld. Toch heeft een computer bijna duizend jaar rekentijd nodig om de kortste route langs twintig bestemmingen te berekenen. Het is dan ook een van de meest intensief bestudeerde problemen in de wiskunde.”
En jullie dachten: we doen er een schepje bovenop en we gaan voor een kleine zestigduizend bestemmingen?
Peter: “Haha, als we een wiskundig probleem van dit kaliber wilden oplossen, wilden we dat wel met volle overtuiging doen. In Nederland staan 57.912 rijksmonumenten, dus dat leek ons wel een leuke uitdaging.”
Routeplanningssoftware: 1.8 miljard afstanden
Arjen, wat was precies de bijdrage van CQM?
“Om te kunnen kiezen tussen alle mogelijke routes, heb je om te beginnen de afstanden tussen alle locaties nodig. CQM heeft een eigen routeplanningsservice die razendsnel onderlinge afstanden tussen een groot aantal adressen kan uitrekenen. Met deze software lukt het ons om binnen twee uur tijd de 1.8 miljard afstanden tussen de rijksmonumenten in Nederland te berekenen. Die berekening kunnen wij inmiddels gewoon op een simpele computer maken.”
Vervolgens zijn William Cook en Keld Heisgaun met die 1.8 miljard afstanden aan de haal gegaan…
Arjen: “Met onze afstandenmatrix hebben Cook en Heisgaun een eenvoudiger én sneller algoritme kunnen ontwikkelen. Vervolgens hebben ze het algoritme succesvol gekoppeld aan een enorme hoeveelheid rekenkracht. Het algoritme is uitgerold naar 320 computerprocessoren. De processoren zijn verdeeld over tien serverclusters met één server per cluster. Ter illustratie: de 320 computers zijn samen goed voor negentig jaar aan rekentijd. Die rekenkracht heeft z’n werk gedaan: de kortste route langs alle 57.912 rijksmonumenten bleek 20.253.062 meter.”
De route langs alle 57.912 rijksmonumenten in Nederland. 
Ingezoomd: de route langs alle rijksmonumenten die in Eindhoven staan.
Wat is er nu anders gegaan dan voorheen, waardoor jullie het vraagstuk wél konden oplossen?
Arjen: “Er was een volledige afstandenmatrix voor handen. Cook heeft eerder al eens de kortste route berekend langs alle pubs in het Verenigd Koninkrijk. Toen had hij echter geen beschikking over een matrix met alle onafhankelijke afstanden tussen de kroegen. Met de afstandenmatrix van CQM hadden de professoren ditmaal direct toegang tot alle mogelijke afstanden tussen de 57.912 rijksmonumenten die vereist waren voor de ontwikkeling van het algoritme.”
“In Nederland staan 57.912 rijksmonumenten, dat leek ons wel een leuke uitdaging.”
Peter Hulsen
In de praktijk heeft snelheid prioriteit
Hoe vaak zijn jullie in de praktijk bezig met dit vraagstuk?
Peter: “Wij rekenen op bijna dagelijkse basis voor onze klanten uit hoe ze zo efficiënt mogelijk van A naar B kunnen komen. Dat is ook waarom we die software in huis hebben. We lossen dus dagelijks varianten van dit probleem op, maar we garanderen niet dat we de beste oplossing hebben. Dat vragen onze klanten ook niet van ons. Ze willen in een zo kort mogelijke tijd, een zo goed mogelijke oplossing die voldoet aan alle voorwaarden.”
Arjen: “Wetenschappers zoeken één ding vaak uit tot op het naadje. Wij daarentegen, moeten vaak snel een berekening maken. Het hoeft niet tot op het naadje, het moet vooral heel goed gebeuren. Een groot verschil, maar dat neemt niet weg dat het voor ons heel belangrijk is om de wetenschap te volgen en op de hoogte te blijven.”
Kansen voor route-optimalisatie
Wat betekent deze doorbraak voor jullie?
Peter: “Het biedt veel kansen voor route-optimalisatie, maar voor ons is het handelsreizigersprobleem een onderdeel van een groter geheel. Neem bijvoorbeeld een taxibedrijf dat wil weten hoe hun taxi’s een route het meest efficiënt kunnen rijden. Dan wil je weten wat de kortste route is langs alle ophaalpunten – het TSP. Maar het is ook belangrijk dat alle klanten op tijd worden opgehaald. Of dat ze niet te lang hoeven te wachten en dat er niet te veel mensen tegelijkertijd in de taxi zitten. Het TSP is dus een subonderdeel van de routeplanning.”
Arjen: “Daarnaast laat de doorbraak goed zien dat niet alleen computers steeds sneller en slimmer worden. Tuurlijk, snellere en sterkere processoren zijn superbelangrijk, maar de wiskundige technieken die ermee gepaard gaan, zijn dat evenzo. Die twee moeten elkaar wel blijven bijbenen, anders hebben we er in de praktijk niets aan.”
Peter, staat er voor het volgende bedrijfsuitje van CQM nu een ruim twintigduizend kilometerlange fietstocht langs de rijksmonumenten op het programma?
“Haha, nee. We houden van uitdagingen, maar 20.000 kilometer is ook ons net te ver.”
Ook interessant: Hoe weeg je een kalkoen? Wiskunde als oplosser van dagelijkse vraagstukken
Wetenschapper wil wiskundeknobbel elektrisch stimuleren
Als je dit artikel leuk vindt, lees dan ook:
