Onderzoekers van het Max Planck Instituut für Informatik in het snelwegenrijke Duitse Karlsruhe hebben een nieuw algoritme ontworpen, waarmee gegarandeerd de kortste routes in heel Europa in microseconden opgezocht kunnen worden.

De routeplanner kraakt een klassiek computerprobleem: vind de kortste route tussen twee punten in een wegennetwerk. De domste methode is gewoon alle mogelijke wegen tussen de twee steden nagaan, en kijken welke route het kortste is. Werkt gegarandeerd, maar de rekentijd verdubbelt bij ieder extra knooppunt (een afslag of kruispunt), waardoor het al gauw veel te lang duurt. Vergelijkbare problemen duiken niet alleen op in routeplanners, maar in allerlei logistieke situaties, van postdistributienetwerken tot internetrouters. Er is dus geld mee te verdienen.

In 1959 al vond de Nederlandse wiskundige Edsger Dijkstra een betere aanpak, die gegarandeerd de snelste route vindt, en een stuk sneller, grofweg door bij ieder knooppunt de minimumafstand naar het beginpunt te berekenen en die vervolgens door te berekenen naar de buurknooppunten. Toch duurt ook Dijkstra's algoritme vaak nog te lang. Dus gebruiken commerciële routeplanners zogeheten heuristische methoden. Die maken gebruik van redelijke aannames over het wegennetwerk (voor Amsterdam-Rotterdam hoef je niet over Finland), maar ze vinden niet gegarandeerd de kortste route. En zo snel zijn ze ook weer niet.

De Duitsers komen nu met een snellere aanpak, gebaseerd op veel voorwerk, die wél gegarandeerd de kortste route vindt, en snel. Het idee sluit goed aan bij de intuïtie van de automobilist: voor stukjes in de buurt gebruik je straten, iets verder rijd je over provinciale wegen, en voor langere stukken ga je de snelweg op. Het aanbrengen van een hiërarchie van soorten wegen voor verschillende schalen maakt het vinden van een kortste route dus gemakkelijker.

Van tevoren categoriseert het Duitse algoritme het wegennetwerk op verschillende schalen. Op een lokale schaal worden alle kortste routes tussen alle knooppunten berekend met Dijkstra's methode, en in een tabel gezet. Op een grotere schaal wordt het wegennetwerk uitgedund tot de hoofdwegen, door alleen stukken weg mee te nemen die -let u even op- onderdeel zijn van een kortste route tussen twee ver weg gelegen knooppunten. In de praktijk wil dat zeggen dat steegjes in Utrecht niet meegenomen worden in de berekeningen op snelwegschaal. Dat scheelt veel knooppunten, want het snelwegnetwerk is grofmaziger dan de Utrechtse binnenstad. Eventueel kan het procédé op nog hogere schalen (nog belangrijker hoofdaders) herhaald worden.

Uiteindelijk levert al het rekenwerk een enorme tabel op van kortste routes op verschillende schalen, waarin de kortste route tussen twee willekeurige punten razendsnel op te zoeken is. Door een strakke wiskundige definitie van de verschillende schalen is dat bovendien gegarandeerd de allerkortste route.

Voor Europa (18.010.173 knooppunten) kost het rekenwerk vantevoren zo'n drie uur rekenen op een gewone PC, becijferen de onderzoekers. Dat levert een tabel op van zo'n 4,5 gigabyte, die op de harde schijf van een navigatie-apparaat past. Maar dan kun je ook je route plannen in 20 microseconden, in plaats van tien tot twintig seconden. Dus kun je nog weer een paar tellen later vertrekken.

Bruno van Wayenburg

Holger Bast, Stefan Funke, Peter Sanders, Dominik Schultes, 'Fast Routing in Road Networks with Transit Nodes', Science, 27 april 2007

http://eddiepoppe.cambridgelaan.nl/scrip...