13 maart 2013: Lex Schrijver
Het handelsreizigersdilemma: hoe ontwerp je de NS-dienstregeling?

Terwijl in het Vaticaan de schoorsteen van de Sixtijnse Kapel de laatste restjes witte rook uitblies begon in Deventer prof.dr. Lex Schrijver aan zijn lezing voor het Science Café, over het handelsreizigersprobleem en het ontwerpen van de dienstregeling voor de NS. Om te beginnen kregen we een stukje geschiedenis voorgeschoteld over het Centrum voor Wiskunde en Informatica (CWI), waar Schrijver als onderzoeker werkzaam is, naast zijn hoogleraarschap Wiskunde aan de Universiteit van Amsterdam. Het CWI heeft zijn sporen verdiend met o.a. rekenwerk aan de Deltawerken, het huisvesten van de eerste computer in Nederland, en het verzenden van de eerste e-mail vanuit Europa naar Amerika.

Met zo’n staat van dienst is het niet zo verwonderlijk dat ze bij het CWI ook belangstelling hadden voor het zogenoemde handelsreizigersprobleem. Dat is niet het probleem van iemand die huis aan huis stofzuigers tracht te verkopen en steevast de deur voor zijn neus ziet dichtslaan. Nee, het gaat om een wiskundig probleem waar bij je de kortste route moet bepalen van een rondreis langs een aantal steden. Dat klinkt simpel, maar schijn bedriegt. Want bij een klein aantal steden – laten we zeggen elf – valt het nog wel te bepalen, zeker als er in de praktijk maar een beperkt aantal bevroren sloten en kanalen in overweging kunnen worden genomen. Maar als het aantal steden oploopt neemt het aantal mogelijk oplossingen exponentieel toe, en bij bijvoorbeeld dertig steden heb je, zelfs met de snelste computers ter wereld, al meer tijd nodig dan het heelal bestaat om alles door te rekenen en de kortste route te vinden. Niemand weet of er een snellere methode is en je kunt er een miljoen dollar (van het Clay Mathematics Institute – http://www.claymath.org/millennium/P_vs_NP/) mee winnen als je ‘m vindt. (Volgens Schrijver kun je je vondst overigens beter geheim houden, want dan kun je er wel een miljard dollar mee verdienen.)

Een praktisch voorbeeld van een vergelijkbaar probleem is het maken van de dienstregeling voor de NS. Het CWI heeft hiervoor een programma ontwikkeld genaamd “Combinatorisch-Algebraïsch DienstregelingsAlgoritme voor de Nederlandse Spoorwegen” wat zich, hoe toevallig, laat afkorten tot CADANS. Schrijver vertelde dat het probleem van de NS ook is te vergelijken met een ander wiskundig raadsel, nl. of je een landkaart kunt inkleuren met zo min mogelijk kleuren, zonder dat aangrenzende landen dezelfde kleur krijgen. Het blijkt dat vier het minimum aantal benodigde kleuren is. De techniek die hierbij gebruikt wordt is het uitdrukken van het probleem in de vorm van een zogenoemde graaf, een set punten die onderling verbonden zijn door lijnen. De punten stellen objecten voor, bijvoorbeeld spoorwegstations, en de lijnen geven relaties tussen die objecten weer, bijvoorbeeld rijtijden tussen deze stations. Door op een slimme manier aan deze graaf te rekenen kan CADANS een dienstregeling opstellen voor het complete spoorwegnet. In 2007 is voor het eerst het spoorboekje op deze manier tot stand gekomen.

Nadat Schrijver deze nogal ingewikkelde theorie had uitgelegd trakteerde hij het publiek op de “geheimen van het spoorboekje”. Het blijkt bijvoorbeeld dat je met behulp van symmetrie-assen in het spoorboekje makkelijk kunt beredeneren wanneer een trein vertrekt, als je aankomst van de trein in de tegenovergestelde richting weet. Sterker nog, omdat de symmetrie-assen zich voortplanten in het hele net, is er eigenlijk maar één symmetrie-as.

Veel van de vragen van het publiek na de pauze gingen over de wiskunde achter de dienstregeling, maar opvallend genoeg waren er ook een paar vragen van meer persoonlijke aard. Zo vroeg James van Lidth de Jeude, de gespreksleider, waar Schrijvers passie voor wiskunde vandaan kwam. Hij antwoordde dat hij vooral geïnspireerd was door zijn wiskundeleraar op de middelbare school. Lineke Tak, de voorzitter van het Science Café, wilde weten hoe een dag in het leven van een wiskundige eruit zag, waarop Schrijver zei dat hij eigenlijk de hele dag maar een beetje op de bank hing. Nu zullen sommigen onder ons waarschijnlijk moeten bekennen dat ze dat vroeger op school ook veel deden, hangen, vooral tijdens de wiskundeles, maar als we hadden geweten dat je er ook je beroep van kon maken, dan hadden we misschien iets beter opgelet.

De muziek werd verzorgd door Tim van Doorn.

Tekst Peter van Diest, fotografie Huub Eggen.

(Zie ook de aankondiging van deze lezing.)