routeberekening

Routeberekening is het proces van het bepalen van een optimale of geschikte route tussen twee of meer locaties in een netwerk, meestal een wegennetwerk, op basis van een kostenfunctie zoals afstand, reistijd of brandstofverbruik. Het vormt de kern van moderne navigatiesystemen, logistieke planning en geografische informatiesystemen (GIS).

Netwerken worden doorgaans gemodelleerd als gerichte, gewogen grafen: knopen zijn kruispunten of haltes, randen zijn wegsegmenten; gewichten geven de kost van een rijstuk weer. Realtime factoren zoals verkeersdrukte, vertragingen en wegafsluitingen kunnen als tijd-afhankelijke of adaptieve gewichten worden weergegeven.

Er bestaan verschillende routing-algoritmes, afhankelijk van het doel en de dataset. Dijkstra’s algoritme levert gegarandeerd de kortste route in grafen met positieve gewichten. Bellman-Ford kan ook met negatieve gewichten omgaan maar is trager. A* versnelt de zoek met een heuristiek, meestal een afstandsgerelateerde maat. Floyd–Warshall berekent routes tussen alle knoopparen, handig in kleine netwerken. Voor grote netwerken gebruiken systemen geavanceerde technieken zoals Contraction Hierarchies, ALT, of highway-node routing. Bij multi-criteria routeplanning moeten meerdere criteria tegelijk worden afgewogen en kan de uitkomst een set pareto-optimale routes zijn.

Data zoals OpenStreetMap, commerciële kaartbestanden en live verkeersfeeds vormen de basis. Routeberekening streeft naar zowel snelheid als betrouwbaarheid; in logistiek wordt vaak rekening gehouden met tijdvensters, leveringsprioriteit en voertuigbeperkingen. Uitdagingen zijn nauwkeurige data, dynamische veranderingen, schaalbaarheid en privacy.