Record-handelsreizigersprobleem; De kortste route langs 57.912 rijksmonumenten - VVSOR - VVSOR

Vereniging voor Statistiek en Operations Research
STAtOR Article

Record-handelsreizigersprobleem; De kortste route langs 57.912 rijksmonumenten

Nederland heeft tienduizenden rijksmonumenten die je op een mooie dag met de fiets kunt bezoeken. Maar heb je je al eens afgevraagd wat de kortste fietsroute langs al deze monumenten is? De oplossing, met een lengte van 20.253.062 meter is, op moment van schrijven, het grootste optimaal opgeloste handelsreizigersprobleem ter wereld. In dit artikel leggen we meer uit over de achtergrond en de technieken voor het oplossen van deze uitdaging.

STAtOR STAtOR

Frans de Ruiter

In het najaar vindt de jaarlijkse Open Monumentendag plaats. In het tweede weekend van september openen duizenden monumenten gratis hun deuren voor publiek. Een drukbezocht evenement dat natuurlijk de nodige voorbereiding vergt van deze bijzondere locaties. Een lange aanloop was er ook voor het team van CQM, Bill Cook (hoogleraar aan de Universiteit van Waterloo in Canada) en Keld Helsgaun (Universiteit van Roskilde in Denemarken). Samen zijn zij de uitdaging aangegaan om de kortste fietsroute te vinden waarmee je alle 57.912 locaties kunt bezoeken. Om dit te kunnen bepalen moet je alle paren te krijgen. Zelfs als je aanneemt dat van A naar B reizen dezelfde afstand is als andersom, van B naar A reizen, moet je tabel nog steeds duizenden afstanden bevatten. Enkele jaren geleden werden door een team onder leiding van Bill Cook wel weer grote problemen op wegenkaarten opgelost. In 2016 is de optimale route gevonden voor 49.603 Amerikaanse monumenten en in 2018 een ludieke kortste kroegentocht langs alle 49.687 pubs in het Verenigd Koninkrijk. Al deze routes maakten gebruik van loopafstanden uitgerekend door Google Maps. De Emder Kaap op Rottumeroog. Foto: Rijkswaterstaat | Rob Jungcurt CC eerst alle afstanden tussen de locaties weten en vervolgens nog een van de moeilijkste wiskundige problemen oplossen: het handelsreizigersprobleem.

GeĆÆnteresseerd in het volledige artikel? Lees het hier.

 

ARTIKEL INFORMATIE
STAtOR 2022 nr. 1Ā pagina 43-45

AUTEUR INFORMATIE

Frans de Ruiter is gepromoveerd op het gebied vanĀ robuuste optimalisatie bij Tilburg University. Sinds 2017 is hijĀ consultant bij CQM in Eindhoven. Hier werkt hij aan groteĀ optimalisatie en planningsprojecten. Een dag in de week isĀ hij als research scientist werkzaam bij de Universiteit vanĀ een fietspad liggen, twintig monumenten moet je van Wageningen.
E-mail: deruiter@cqm.nl

Gepubliceerd op: June 23, 2022