Onderzoek/Onderwijs

Computerprogramma berekent alternatieve
routes bij afsluitingen van netwerken

Foto: Bart van Overbeeke

Netwerken voor bijvoorbeeld autoverkeer, treinen of telecommunicatie zijn kwetsbaar als een deel ervan plat gaat. Bestemmingen worden niet meer direct gevonden, maar via een omweg. De vraag is dan: welke route is het meest voordelig en hoeveel tijdverlies treedt op? Maar ook: waar moet een extra verbinding worden aangelegd om maximaal voordeel te halen uit de investering? Dr. Joachim Gudmundsson kreeg van de Nederlandse organisatie voor Wetenschappelijk Onderzoek (NWO) een Veni-beurs om hier de komende drie jaar onderzoek naar te doen.

Netwerken moeten zó zijn opgebouwd dat ze ondanks het verlies van een deel van de routes toch blijven functioneren. Misschien met een kleine verlenging van de reistijd, maar alles moet vanaf elk punt binnen het netwerk bereikbaar blijven.
Het Nederlands spoorwegennet is een voorbeeld van een heel kwetsbaar netwerk. Uitval van bijvoorbeeld de verbinding Eindhoven-Amsterdam betekent dat een rit van Eindhoven naar Nijmegen (via Den Bosch) bijna onmogelijk is, of het moet via Tilburg of Venlo. Het spoorwegennet is zo kwetsbaar dat vaak onmiddellijk bussen worden ingezet. Het netwerk zelf kan in veel gevallen de uitval van verbindingen niet tegen acceptabele vertragingen opvangen.
Hoe kwetsbaar het Nederlandse wegennet is, blijkt wanneer ergens een ongeluk is gebeurd en de auto’s moeten worden omgeleid. Ook tijdens de BSE- en MKZ-crisis bleek hoe gevoelig het netwerk van wegen is.
Als de reistijd door de omweg toeneemt met enkele procenten zal niemand klagen. Zou een afgesloten weg tussen bijvoorbeeld Eindhoven en Helmond betekenen dat de reistijd toeneemt met zeventig procent, dan zal er worden nagedacht over de aanleg van een extra weg. Maar waar moet die weg komen? Welke verbinding zal de afsluiting tussen A en B het beste opvangen? Dat is de eerste vraag. Het antwoord is natuurlijk: een tweede verbinding tussen A en B. Maar daarmee is alleen de situatie tussen die punten verbeterd, terwijl er wellicht een weg tussen A en C kan worden aangelegd die de reistijd van A via C naar B doet in enkele procenten meer dan direct van A naar B, en die daarnaast ook de reistijd van A naar C bekort, en wellicht nog andere problemen oplost.

Algoritmen
Het zoeken naar deze meest functionele keuzes in het verbeteren van netwerken is erg moeilijk. Er bestaan momenteel nauwelijks computerprogramma’s die in staat zijn dit soort vragen goed te kunnen beantwoorden. Informaticus dr. Joachim Gudmundsson zal er de komende drie jaar onderzoek naar doen. De Zweed is werkzaam op het gebied van computationele geometrie in de Algoritmiek groep van de faculteit Wiskunde & Informatica van de TU/e. In het verleden werkte hij als onderzoeker in geometrische algoritmen bij het Instituut voor Informatica en Informatiekunde aan de Universiteit van Utrecht. Eerder was hij lid van de Geometrische-algoritmen groep van Computerwetenschappen in Lund, Zweden.
Gudmundsson: “Er is al wel onderzoek gedaan naar dit soort vragen, maar er is bijvoorbeeld nog helemaal niet gekeken naar wat er gebeurt als alle wegen in een bepaald gebied worden afgesloten, zoals bij de MKZ-crisis. Daar komen ontzettend interessante theoretische vragen uit, die naar ik hoop ook in de praktijk relevant zijn. Want bij de planning van nieuwe infrastructuur kan men dan al reknning houden met het minimaliseren van vertragingen in dat soort crisissituaties”.
Gudmundsson kreeg van de Nederlandse organisatie voor Wetenschappelijk Onderzoek (NWO) een Veni-subsidie van tweehonderdduizend euro. Deze subsidie biedt pas gepromoveerde onderzoekers de mogelijkheid om gedurende drie jaar hun ideeën verder te ontwikkelen. Gudmundsson werkt in zijn onderzoek samen met universiteiten in Lund (Zweden), Miami (Verenigde Staten), Kopenhagen (Denemarken) en Carleton (Canada)./.