20.000 kilometer fietsen en je hebt ieder monument gezien

Wiskunde Dit weekend is het Open Monumentendag. Wat is de kortste route tussen alle rijksmonumenten? Dat wiskundige probleem is nu opgelost.

De Van Nellefabriek in Rotterdam is een van de locaties die tijdens Open Monumentendag de deuren opent voor het publiek.
De Van Nellefabriek in Rotterdam is een van de locaties die tijdens Open Monumentendag de deuren opent voor het publiek. Foto Jerry Lampen/ANP

Fietsen langs de Van Nellefabriek in Rotterdam, de provinciegrenspaal op de Afsluitdijk, de Sint-Stephanuskerk in Bornerbroek en alle overige 57.909 rijksmonumenten in Nederland: wie dat zonder omwegen wil doen, legt 20.253.062 meter af. Het is dus zaak om op tijd van huis te vertrekken als je dit weekend tijdens de Open Monumentendagen al dit moois wilt bekijken.

De rondrit langs alle monumenten is een voorbeeld van het beruchte ‘handelsreizigersprobleem’. Dat probleem vraagt naar de kortste weg die een reiziger langs diverse locaties moet afleggen, waarbij hij elke locatie precies één keer bezoekt en moet terugkeren bij de plek waar hij vertrok. Het is een van de meest bestudeerde problemen in de computationele wiskunde. Toepassingen zijn er volop, zoals de beweging van robotarmen die gaten boren op printplaten.

De route langs de monumenten is berekend door wiskundige William Cook (Universiteit van Waterloo, Canada) en informaticus Keld Helsgaun (Universiteit van Roskilde, Denemarken) . Ze maakten daarbij gebruik van data die werden geleverd door CQM, een adviesbureau in Eindhoven dat is gespecialiseerd in het oplossen van logistieke vraagstukken.

Logistieke vraagstukken

Op de lijst van miljoen-dollar-problemen van het Clay Mathematics Institute staat deze vraag: bestaat er voor het handelsreizigersprobleem een snel algoritme? In deze context betekent ‘snel’ dat de lengte van de berekening evenredig is met een macht (bijvoorbeeld kwadraat of derdemacht) van de omvang van de input. Men denkt dat het antwoord nee is, maar de wiskunde lijkt nog niet rijp voor een bewijs. Daarentegen worden de grenzen om specifieke grote gevallen te berekenen, zoals nu met de Nederlandse monumentenroute is gedaan, stukje bij beetje verschoven.

Met het werk van CQM en de twee wetenschappers is een nieuw record gevestigd: nooit eerder werd zo’n groot handelsreizigersprobleem op een landkaart opgelost. Dat is bijzonder, want om zo’n kortste rondrit langs duizenden locaties te berekenen, moeten allerlei trucs uit de optimaliseringstheorie worden toegepast. Eerder berekende Cook onder meer de kortste route langs 24.727 pubs in het Verenigd Koninkrijk. Een voorbeeld met maar liefst 85.900 locaties is er ook, maar die bevinden zich niet op een landkaart: de locaties zijn daarbij transistoren, de minuscule bouwstenen van chips.

De optimale monumentenroute werd gevonden door 320 computerprocessoren tegelijk te laten werken.

Voor efficiënte routebepaling heeft CQM state-of-the-artsoftware in huis. Het plannen van taxiritten en goederenvervoer, met bijvoorbeeld trein en vrachtwagen, is voor dit bedrijf dagelijkse kost.

Voor de Nederlandse monumentenfietsroute berekende CQM met behulp van speciaal fietskaartmateriaal alle 1,8 miljard afstanden tussen de rijksmonumenten in Nederland. Dankzij een slim algoritme, waarvan de basis al in 1956 werd ontwikkeld door de Nederlandse informaticus Edsger Dijkstra, had een doorsneecomputer niet meer dan twee uur nodig om al die afstanden te berekenen.

Eenmaal de beschikking over die afstanden, is de volgende taak om de kortste rondrit te berekenen. Eind vorige eeuw ontwierp Cook met een aantal collega’s een algoritme, Concorde genaamd, dat elk handelsreizigersprobleem in theorie kan oplossen. In theorie, want aan Concorde kleeft een extreem hoge complexiteit: neemt het aantal locaties lineair toe, stijgt de rekenduur exponentieel. Zelfs bij een kleine input kan de berekening in de praktijk heel lang duren.

Lees ook: Een monument hoeft niet altijd van steen te zijn

De optimale monumentenroute – 20.253.062 meter fietsen om ze alle 57.912 te bezoeken – werd gevonden door 320 computerprocessoren tegelijk te laten werken. Op een enkele computer zou de berekening negentig jaar hebben geduurd. Gezien de moeilijkheid van het probleem kan dit gerust ‘snel’ worden genoemd, al is het niet iets wat je elke dag voor een steeds weer nieuw voorliggend probleem zou kunnen doen.