Lex Schrijver

Handelsreizigersprobleem

‘Stel je wilt langs alle twaalf Nederlandse hoofdsteden via een zo kort mogelijke route. Voor vier steden heb je drie mogelijke routes, voor vijf steden heb je al twaalf mogelijkheden. Twaalf provinciehoofdsteden leveren al bijna twintig miljoen routes. Er zijn dus heel veel mogelijkheden. Hoe weet je dan op een snelle manier welke de beste is? Deze vraag speelt al eeuwen en wordt het handelsreizigersprobleem genoemd.’

‘De methode die ik gebruik om dit soort problemen op te lossen is een meetkundige. Ik ga niet elke mogelijkheid afzonderlijk na, maar ik zie elke route als een punt in een bepaalde ruimte met heel veel dimensies. Als je de coördinaten van alle routes omhult, ontstaat een vorm: een polytoop (zie figuur 1). In die ruimte kun je sneller zoeken naar de kortste route.’

Treinen koppelen

Een polytoop

‘In de jaren negentig benaderde de NS mij. Ze hadden een probleem met het inzetten van de treinen. De treinstellen hebben een verschillende lengte, van drie of vier “bakken”. Wil je de trein langer of korter maken, dan kun je alleen het voorste of achterste treinstel loskoppelen. Je kunt er niet eentje uit het midden plukken. Bij de roostering moet je dus niet alleen rekening houden met hoe veel passagiers er op een bepaald moment mee willen, en dus met de lengte van de trein. Je moet er ook voor zorgen dat het treinstel dat je wilt afkoppelen voor- of achteraan zit. Al deze factoren maken het probleem een stuk lastiger dan je in eerste instantie zou denken.’

‘Het vraagstuk van de NS was één onderdeel van mijn werk als onderzoeker. Ik richtte me daarnaast natuurlijk ook op andere problemen. Maar de treinstellen bleven me fascineren en ik bleef er over nadenken. Bijvoorbeeld tussen kerst en nieuwjaar, in de avonduren tijdens het luisteren naar muziek of onderweg op de fiets. Of ‘s middags na een kort middagdutje waarin ik even mijn gedachten kan ‘resetten’. Na jaren nadenken en discussiëren met collega’s bedacht ik een oplossing. Ik verhoogde het aantal dimensies van de zoekruimte. En in tegenstelling tot wat je zou verwachten, werd het vinden van de oplossing hierdoor makkelijker. Ik ontving de Spinozaprijs onder andere voor het bedenken van deze methode.’

Optimaal boodschappen doen

‘Veel wiskundigen vinden de wiskunde achter hun ideeën interessanter dan een uiteindelijke toepassing. Ook ik kan genieten van pure wiskunde, maar ik vind toepassingen ervan wel mooi meegenomen. Die maken het makkelijker om met niet-wiskundigen over mijn werk te praten. Optimaal combineren is een vraagstuk uit de dagelijkse praktijk. Iedereen die op vakantie verschillende bezienswaardigheden wil bezichtigen, stippelt een route uit. De bezorgers van post willen niet verder dan noodzakelijk lopen. En de vuilniswagens hebben ook een optimale route voor het ophalen van afval. Zelf houd ik rekening met de volgorde van de producten in de schappen als ik een boodschappenlijstje maak.’

Uitdagingen

‘Je concentreren, diep nadenken over moeilijke problemen, dat is waar ik gelukkig van word. Een te makkelijke puzzel is niet leuk. En het fijne van wiskunde is dat je vaak weet wat het probleem is. Gelukkig zijn er in mijn vak nog genoeg uitdagingen over. Zo is er een stichting die zeven grote wiskundige problemen heeft geformuleerd. Vind je daar het antwoord op, dan kun je per oplossing een miljoen dollar verdienen. Soms werk ik aan een van die vragen. Ik zoek nu naar het wiskundig bewijs dat bepaalde wiskundige problemen niet snel kunnen worden opgelost. Weer iets
nieuws om over na te denken op de fiets.’

Zelf ook een miljoen verdienen met een antwoord op een van de grote vragen in de wiskunde?
Kijk op www.claymath.org/millennium

• www.claymath.org/millennium